7 Numeros combinatorios

Definición II.8.

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

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

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

Teorema II.8 (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}\mathchar 46\relax
Demostración.

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!}\mathchar 46\relax

∎

Demostración.

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}\mathchar 46\relax

∎

Teorema II.9 (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}
Demostración.

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)!}}\mathchar 46\relax

∎

Demostración.

Demostracion combinatoria. Hecha en clase. ∎

Teorema II.10 (Binomio de Newton).

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

(a+b)n=∑j=0n(nj)ajbn−j.(a+b)^{n}=\sum_{j=0}^{n}\binom{n}{j}a^{j}b^{n-j}\mathchar 46\relax
Demostración.

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

∑j=01(1j)ajb1−j=(10)a0b1+(11)a1b0=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)ajbn+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)ajbn−j⋅(a+b)==a∑j=0najbn−j+b∑j=0najbn−j=∑j=0n(nj)aj+1bn−j+∑j=0n(nj)ajbn−j+1==(nn)an+1b0+∑j=0n−1(nj)aj+1bn−j+∑j=1n(nj)ajbn−j+1+(n0)a0bn+1==(nn)an+1b0+∑j=1n(nj−1)ajbn−(j−1)+∑j=1n(nj)ajbn−j+1+(n0)a0bn+1==(nn)an+1b0+∑j=1n((nj−1)ajbn−(j−1)+(nj)ajbn−j+1)+(n0)a0bn+1==(nn)an+1b0+∑j=1n(((nj)+(nj−1))ajbn+1−j)+(n0)a0bn+1==∑j=0n+1(n+1j)ajnn+1−j.{}(a+b)^{n+1}=(a+b)^{n}\cdot(a+b)\overset{H\mathchar 46\relax I\mathchar 46% \relax}{=}\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}}\mathchar 46\relax

∎

Teorema II.11 (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}\mathchar 46\relax
Demostración.

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

(1+1)n=∑j=0n(nj)1j1n−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}% \mathchar 46\relax

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} ∎