7 Numeros combinatorios

Definition 7.1.

Se amplia la definicion de numero combinatorio al caso k=0k=0 como

(m0)≔1.\binom{m}{0}\coloneqq 1.

Triangulo de Pascal. El numero de una fila es la suma de los dos numeros superiores.

Theorem 7.2 (Simetria del triangulo de Pascal).

Sean m∈ℕm\in\mathbb{N}, k∈ℕ∪{0},k≤mk\in\mathbb{N}\cup\left\{0\right\},k\leq m. Entonces:

(mk)=(mm−k).\binom{m}{k}=\binom{m}{m-k}.
Proof 7.3.

Demostracion analitica con la formula.

(mk)=m!(m−k)!⁢k!\binom{m}{k}=\frac{m!}{(m-k)!k!}
(mm−k)=m!(m−(m−k))!⁢(m−k)!=m!(m−k)!⁢k!.\binom{m}{m-k}=\frac{m!}{(m-(m-k))!(m-k)!}=\frac{m!}{(m-k)!k!}.
Proof 7.4.

Demostracion con combinatoria.

(mk)= las formas de elegir ⁢k⁢ elementos de entre ⁢m⁢ posibles.\binom{m}{k}=\text{ las formas de elegir }k\text{ elementos de entre }m\text{ % posibles.}
(mm−k)= las formas de elegir ⁢m−k⁢ elementos de entre ⁢m⁢ posibles.\binom{m}{m-k}=\text{ las formas de elegir }m-k\text{ elementos de entre }m% \text{ posibles.}

Cada eleccion de kk elementos lleva implicita una eleccion de m−km-k elementos (el complementario del conjunto elegido). Por tanto, hay las mismas formas de elegir kk elementos que de m−km-k. Luego

(mk)=(mm−k).\binom{m}{k}=\binom{m}{m-k}.
Theorem 7.5 (Calculo iterativo de los numeros combinatorios).

Sean m∈ℕm\in\mathbb{N}, k∈ℕ∪{0},k<mk\in\mathbb{N}\cup\left\{0\right\},k<m. Entonces:

(m+1k+1)=(mk)+(mk+1)\binom{m+1}{k+1}=\binom{m}{k}+\binom{m}{k+1}
Proof 7.6.

Demostracion analitica.

(mk)+(mk+1)=m!(m−k)!⁢k!+m!(m−k−1)!⁢(k+1)!==m!⁢(k+1)(m−k)!⁢k!⁢(k+1)+m!⁢(m−k)(m−k)⁢(m−k−1)!⁢(k+1)!==m!⁢(k+1)(m−k)!⁢(k+1)!+m!⁢(m−k)(m−k)!⁢(k+1)!=m!⁢(m+1)(m−k)!⁢(k+1)!==(m+1)!(m−k)!⁢(k+1)!.{}\binom{m}{k}+\binom{m}{k+1}=\frac{m!}{(m-k)!k!}+\frac{m!}{(m-k-1)!(k+1)!}=\\ {}=\frac{m!(k+1)}{(m-k)!k!(k+1)}+\frac{m!(m-k)}{(m-k)(m-k-1)!(k+1)!}=\\ {}=\frac{m!(k+1)}{(m-k)!(k+1)!}+\frac{m!(m-k)}{(m-k)!(k+1)!}=\frac{m!(m+1)}{(m% -k)!(k+1)!}=\\ {}=\boxed{\frac{(m+1)!}{(m-k)!(k+1)!}}.
Proof 7.7.

Demostracion combinatoria. Hecha en clase.

Theorem 7.8 (Binomio de Newton).

Sean a,b∈ℝa,b\in\mathbb{R}, n∈ℕn\in\mathbb{N}. Entonces:

(a+b)n=∑j=0n(nj)⁢aj⁢bn−j.(a+b)^{n}=\sum_{j=0}^{n}\binom{n}{j}a^{j}b^{n-j}.
Proof 7.9.

Lo demostraremos por induccion sobre nn. En primer lugar, comprobamos si se cumple para n=1n=1:

∑j=01(1j)⁢aj⁢b1−j=(10)⁢a0⁢b1+(11)⁢a1⁢b0=b+a=(a+b)1\sum_{j=0}^{1}\binom{1}{j}a^{j}b^{1-j}=\binom{1}{0}a^{0}b^{1}+\binom{1}{1}a^{1% }b^{0}=b+a=(a+b)^{1}

Suponemos que se cumple para nn y veamos si tambien para n+1n+1. Es decir, (a+b)n+1=∑j=0n+1(n+1j)⁢aj⁢bn+1−j(a+b)^{n+1}=\sum_{j=0}^{n+1}\binom{n+1}{j}a^{j}b^{n+1-j} (tesis de induccion).

(a+b)n+1=(a+b)n⋅(a+b)⁢=H.I.⁢∑j=0n(nj)⁢aj⁢bn−j⋅(a+b)==a⁢∑j=0naj⁢bn−j+b⁢∑j=0naj⁢bn−j=∑j=0n(nj)⁢aj+1⁢bn−j+∑j=0n(nj)⁢aj⁢bn−j+1==(nn)⁢an+1⁢b0+∑j=0n−1(nj)⁢aj+1⁢bn−j+∑j=1n(nj)⁢aj⁢bn−j+1+(n0)⁢a0⁢bn+1==(nn)⁢an+1⁢b0+∑j=1n(nj−1)⁢aj⁢bn−(j−1)+∑j=1n(nj)⁢aj⁢bn−j+1+(n0)⁢a0⁢bn+1==(nn)⁢an+1⁢b0+∑j=1n((nj−1)⁢aj⁢bn−(j−1)+(nj)⁢aj⁢bn−j+1)+(n0)⁢a0⁢bn+1==(nn)⁢an+1⁢b0+∑j=1n(((nj)+(nj−1))⁢aj⁢bn+1−j)+(n0)⁢a0⁢bn+1==∑j=0n+1(n+1j)⁢aj⁢nn+1−j.{}(a+b)^{n+1}=(a+b)^{n}\cdot(a+b)\overset{H.I.}{=}\sum_{j=0}^{n}\binom{n}{j}a^% {j}b^{n-j}\cdot(a+b)=\\ {}=a\sum_{j=0}^{n}a^{j}b^{n-j}+b\sum_{j=0}^{n}a^{j}b^{n-j}=\sum_{j=0}^{n}% \binom{n}{j}a^{j+1}b^{n-j}+\sum_{j=0}^{n}\binom{n}{j}a^{j}b^{n-j+1}=\\ {}=\binom{n}{n}a^{n+1}b^{0}+\sum_{j=0}^{n-1}\binom{n}{j}a^{j+1}b^{n-j}+\sum_{j% =1}^{n}\binom{n}{j}a^{j}b^{n-j+1}+\binom{n}{0}a^{0}b^{n+1}=\\ {}=\binom{n}{n}a^{n+1}b^{0}+\sum_{j=1}^{n}\binom{n}{j-1}a^{j}b^{n-(j-1)}+\sum_% {j=1}^{n}\binom{n}{j}a^{j}b^{n-j+1}+\binom{n}{0}a^{0}b^{n+1}=\\ {}=\binom{n}{n}a^{n+1}b^{0}+\sum_{j=1}^{n}\left(\binom{n}{j-1}a^{j}b^{n-(j-1)}% +\binom{n}{j}a^{j}b^{n-j+1}\right)+\binom{n}{0}a^{0}b^{n+1}=\\ {}=\binom{n}{n}a^{n+1}b^{0}+\sum_{j=1}^{n}\left(\left(\binom{n}{j}+\binom{n}{j% -1}\right)a^{j}b^{n+1-j}\right)+\binom{n}{0}a^{0}b^{n+1}=\\ {}=\boxed{\sum_{j=0}^{n+1}\binom{n+1}{j}a^{j}n^{n+1-j}}.
Theorem 7.10 (Suma de una fila del triangulo de Pascal).

Sea n∈ℕn\in\mathbb{N}. Entonces:

∑j=0n(nj)=2n.\sum_{j=0}^{n}\binom{n}{j}=2^{n}.
Proof 7.11.

Lo demostramos con el binomio de Newton con a=1a=1 y b=1b=1.

(1+1)n=∑j=0n(nj)⁢1j⁢1n−j=∑j=0n(nj).(1+1)^{n}=\sum_{j=0}^{n}\binom{n}{j}1^{j}1^{n-j}=\sum_{j=0}^{n}\binom{n}{j}.

Existe una demostracion alternativa al teorema usando combinatoria.

Supongamos que AA es un conjunto con nn elementos. Si pensamos en todos los subconjuntos posibles de AA, sabemos que hay 2n2^{n} (demostrado en Logica).

Lo divido en casos:

  1. 1.
    ​

    Conjuntos con 0 elementos. 1=(n0)1=\binom{n}{0}

  2. 2.
    ​

    Conjuntos con 1 elemento. (n1)\binom{n}{1}

  3. 3.
    ​

    Conjunto con 2 elementos. (n2)\binom{n}{2}

  4. n.
    ​

    Conjunto con n elementos. (nn)\binom{n}{n}

Luego 2n=(n0)+(n1)+(n2)+⋯+(nn)2^{n}=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}