[Héctor Manuel]

Hola amigos.  Estoy llevando un seminario sobre matemáticas discretas.  Estuvimos estudiando un poco sobre identidades de los coeficientes combinatorios.

Una de ellas dice lo siguiente:

\( n2^{n-1}=\displaystyle\binom{n}{1}+2\displaystyle\binom{n}{2}+3\displaystyle\binom{n}{3}+\cdots+n\displaystyle\binom{n}{n} \)

Primero nos pidieron demostrarla algebraicamente, por lo cual tomé la función \( f(x)=(1+x)^n=\displaystyle\binom{n}{0}+\displaystyle\binom{n}{1}x+\cdots+\displaystyle\binom{n}{n}x^n \), y calculando \( f^\prime(1) \) se tiene lo pedido.  Así gané un punto para mi equipo.

Sin embargo nos pidieron una demostración combinatoria, para lo cual argumenté:

Supongamos que tenemos un conjunto de \( n \) elementos.  Queremos saber cuántos subconjuntos de \( k \) elementos, con \( k=1,\cdots,n \), se pueden formar de manera que de cada uno de ellos se escoja un elemento representativo. 

Entonces esto se puede hacer de \( \displaystyle\binom{n}{1}\displaystyle\binom{1}{1}+\displaystyle\binom{n}{2}\displaystyle\binom{2}{1}+\cdots+\displaystyle\binom{n}{n}\displaystyle\binom{n}{1} \) formas, que es lado derecho de la identidad pedida.

Por otra parte, otra manera de contar eso es escogiendo primero a un representante y luego escoger su "equipo":

\( \displaystyle\binom{n}{1}\displaystyle\binom{n-1}{0}+\displaystyle\binom{n}{1}\displaystyle\binom{n-1}{1}+\cdots+\displaystyle\binom{n}{1}\displaystyle\binom{n-1}{n-1} \), lo cual es igual al lado izquierdo de la identidad.

Sin embargo, el profesor del seminario es "duro" y no me ha aceptado el argumento por "falta de rigurosidad".  Según él, debo definir un conjunto y después contar sus elementos de dos formas distintas (acaso no fue eso lo que hice?)

Por eso quiero preguntarles si hay una manera más formal de demostrar la identidad usando únicamente argumentos combinatorios.

Saludos y gracias.

[pepito]

Se me ocurre que él habrá querido ver esto escrito:

\( \displaystyle\bigsqcup_{k=1}^n\left\big(\left\{x\subseteq\{1,\ldots,n\}:Card(x)=k\right\}\times\left\{1,\ldots,k\right\}\right\big) \)

La forma más natural de calcular el cardinal de este conjunto es la primera que describís: fijar un \( k_0 \) y calcular el cardinal de \( \left\{x\subseteq\{1,\ldots,n\}:Card(x)=k_0\right\}\times\left\{1,\ldots,k_0\right\} \), y como la unión es disjunta, entonces sumar los números obtenidos para todos los posibles \( 1\le k_0\le n \). Esto da el lado derecho de la igualdad.

Y otra forma sería fijar un \( j_0 \) y contar cuántos elementos de esta unión tienen por segunda coordenada a ese valor. Como (obviamente) el que las segundas coordenadas sean distintas implica que los elementos son distintos, entonces no se está contando más de una vez a ningún elemento. Y como considerando a todos los \( 1\le j_0\le n \) se está abarcando a todos los elementos de la unión (porque todos tienen alguna segunda coordenada), entonces la suma de los números obtenidos para los distintos \( 1\le j_0\le n \) es el cardinal de la unión. Pero esto también da el lado derecho de la igualdad.

Pero bueno, siguiendo tu razonamiento, uno puede fijar \( 1\le j_0\le n \) y preguntarse cuántos de los pares ordenados de esta unión cumplen que, si \( r \) es su segunda coordenada, si uno ordena de menor a mayor los números que conforman el conjunto que es su primera coordenada, el \( r \)-ésimo sea \( j_0 \). De vuelta, se verifica que sumando las cantidades obtenidas para todos los posibles \( 1\le j_0\le n \) se está contando cada par ordenado de la unión, y una sola vez cada uno. Y esto da el lado izquierdo de la igualdad.

Te repito, esto es lo que me parece que el profe tenía ganas de leer, pero no sé qué tanto más riguroso será. Es que de hecho, habría que ver cómo se define con rigor a la propia palabra "rigor" .

[Luis Fuentes]

Hola

 Lo mismo de pepito todavía un poco más pedante: 

 Sea \( A_n=\{1,2,\ldots,n\} \) y consideramos:

 \( X_n=\{(B,k)\in P(A_n)\times A_n|k\in B\} \)

 Se cumple que:

 \( X_n=\displaystyle\bigsqcup_{m=1}^nY_m \)  con \( Y_m=\{(B,k)\in X_n|card(B)=m\} \)

 y también:

 \( X_n=\displaystyle\bigsqcup_{m=1}^nZ_m \)  con \( Z_m=\{(B,m)\in X_n\}\color{red}\simeq\color{black}P(A_n-\{m\})\times \{m\} \)

 Cada una de las dos expresiones corresponde a cada una de las dos formas de "contar".

Saludos.

CORREGIDO (gracias pepito)

[pepito]

Y sí. Cuando uno divide a tu conjunto según la segunda coordenada, eso lleva a contar de una forma distinta que si se lo divide según el cardinal de la primera. En mi conjunto en cambio, ambas divisiones llevan a la misma forma de contar (que es, el lado derecho de la igualdad). Por eso a fin de cuentas, lo que hago en el último intento es considerar la biyección canónica entre ellos.

Una sutileza nomás:

\( \{(B,m)\in X_n\}=P(A_n-\{m\})\times \{m\} \)

Estos dos conjuntos no son iguales, sino que están en biyección. Para completar la "pedancia", sólo curvemos una línea:

\( \{(B,m)\in X_n\}\simeq P(A_n-\{m\})\times \{m\} \)

[Luis Fuentes]

Hola

Estos dos conjuntos no son iguales, sino que están en biyección. Para completar la "pedancia", sólo curvemos una línea:

\( \{(B,m)\in X_n\}\simeq P(A_n-\{m\})\times \{m\} \)

Cierto. Por mantener la igualdad podemos escribir así:

\( Z_m=\{(B,m)\in X_n\}=\{C\cup \{m\}|C\in P(A_n-\{m\})\}\times \{m\} \)

Saludos.

[luchoferronir]

Perdón por revivir este post tan viejo.

Lo único necesario para demostrar lo que dice hector manuel es el hecho de que \( \displaystyle\sum_{i=0}^n \binom{n}{i}=2^n \)

La justificación de este hecho es bastante sencilla. Consideremos n elementos, la cantidad de formas de formar un subconjunto de estos \( n \) elementos es \( 2^n \) (un elemento puede estar o no, luego hay dos posibles subconjuntos por cada elemento, y entonces hay \( 2^n \) subconjuntos). La suma \( \displaystyle\sum_{i=0}^n \binom{n}{i} \) está sumando la cantidad de subconjuntos de 0 elementos (vacío), la cantidad de subconjuntos de 1 elementos, ..., la cantidad de subconjuntos de n elementos, con lo cual tenemos \( 2^n \) (la suma de todos los subconjuntos posibles), y entonces \( \displaystyle\sum_{i=0}^n \binom{n}{i}=2^n \) como queríamos ver.

Ahora, la suma de hector manuel es:

\( \displaystyle\sum_{i=1}^n i\cdot \binom{n}{i}=\displaystyle\sum_{i=1}^n i \cdot \dfrac{n!}{i!(n-i)!}=n \cdot \displaystyle\sum_{i=1}^n \dfrac{(n-1)!}{(i-1)!(n-i)!}=n\cdot\displaystyle\sum_{i=1}^n \binom{n-1}{i-1} \)

La suma \( \displaystyle\sum_{i=1}^n \binom{n-1}{i-1} \), por lo dicho al comienzo es \( 2^{n-1} \), y entonces se sigue lo que queríamos:

\( \displaystyle\sum_{i=1}^n i\cdot \binom{n}{i}=n\cdot 2^{n-1} \).

Saludos!