7 Numeros combinatorios

Definición 7.1.

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

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

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

Teorema 7.1 (Simetria del triangulo de Pascal).

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

(mk)=(mm−k).\displaystyle\binom{m}{k}=\binom{m}{m-k}.
Demostración.

Demostracion analitica con la formula.

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

∎

Demostración.

Demostracion con combinatoria.

(mk)= las formas de elegir ⁢k⁢ elementos de entre ⁢m⁢ posibles.\displaystyle\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.\displaystyle\binom{m}{m-k}=\text{ las formas de elegir }m-k\text{ elementos % de entre }m\text{ posibles.}

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

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

∎

Teorema 7.2 (Calculo iterativo de los numeros combinatorios).

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

(m+1k+1)=(mk)+(mk+1)\displaystyle\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)!}}.

∎

Demostración.

Demostracion combinatoria. Hecha en clase. ∎

Teorema 7.3 (Binomio de Newton).

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

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

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

∑j=01(1j)⁢aj⁢b1−j=(10)⁢a0⁢b1+(11)⁢a1⁢b0=b+a=(a+b)1\displaystyle\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 n\displaystyle n y veamos si tambien para n+1\displaystyle n+1. Es decir, (a+b)n+1=∑j=0n+1(n+1j)⁢aj⁢bn+1−j\displaystyle(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}}.

∎

Teorema 7.4 (Suma de una fila del triangulo de Pascal).

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

∑j=0n(nj)=2n.\displaystyle\sum_{j=0}^{n}\binom{n}{j}=2^{n}.
Demostración.

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

(1+1)n=∑j=0n(nj)⁢1j⁢1n−j=∑j=0n(nj).\displaystyle(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 A\displaystyle A es un conjunto con n\displaystyle n elementos. Si pensamos en todos los subconjuntos posibles de A\displaystyle A, sabemos que hay 2n\displaystyle 2^{n} (demostrado en Logica). Lo divido en casos:

  1. 1.
    ​

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

  2. 2.
    ​

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

  3. 3.
    ​

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

  4. n.
    ​

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

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