Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

Question

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

desigualdad
Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

Martín Sleziak

Podemos mostrar fácilmente que los coeficientes binomiales centrales en una fila del triángulo de Pascal, es decir $\binom{2n}n$ en filas pares y $\binom{2n+1}n=\binom{2n+1}{n+1}$ en filas impares, tienen los valores más grandes, más o menos mediante un cálculo sencillo.

Básicamente basta con comprobar que las siguientes desigualdades son equivalentes entre sí:

\begin{aligned} (\binom{norte}{k}) & < (\binom{norte}{k + 1}) \\ \frac{norte!}{k! (norte - k)!} & < \frac{norte!}{(k + 1)! (norte - k - 1)!} \\ \frac{(k + 1)!}{k!} & < \frac{(norte - k)!}{(norte - k - 1)!} \\ k + 1 & < norte - k \\ 2 k + 1 & < norte \end{aligned}

$\begin{align*} \binom nk &< \binom n{k+1} \\ \frac{n!}{k!(n-k)!} &< \frac{n!}{(k+1)!{(n-k-1)!}} \\ \frac{(k+1)!}{k!} &< \frac{(n-k)!}{(n-k-1)!}\\ k+1 &< n-k \\ 2k+1 &< n \end{align*}$ Y funciona de la misma manera para

(\binom{n}{k}) \leq (\binom{n}{k + 1})

$\binom nk \le \binom n{k+1}$ ,

(\binom{n}{k}) > (\binom{n}{k + 1})

$\binom nk \gt \binom n{k+1}$ y

(\binom{n}{k}) \geq (\binom{n}{k + 1})

$\binom nk \ge \binom n{k+1}$ o incluso

(\binom{n}{k}) = (\binom{n}{k + 1})

$\binom nk = \binom n{k+1}$ . De esto podemos ver que esta secuencia es primero creciente y luego decreciente. (Estas secuencias a veces se denominan unimodulares.) Y también vemos que el máximo se alcanza en el medio.

Algunas pruebas más de esto se pueden encontrar aquí: ¿Cómo se prueba ${n \choose k}$ es máximo cuando k es $\lceil \frac n2 \rceil$ o $\lfloor \frac n2\rfloor$ ?

Me gustaría preguntar específicamente sobre las pruebas combinatorias que muestran que tenemos los valores más grandes en el medio de una fila del triángulo de Pascal.

EDITAR: Como se señaló en el comentario de Michael Lugo , de hecho, hay una prueba combinatoria en una de las respuestas a la pregunta vinculada. Aún así, me gustaría ver algunos otros enfoques combinatorios, si son posibles.

Miguel Lugo

La respuesta en math.stackexchange.com/a/880528/173 parece ser una prueba combinatoria de este hecho: ahí está la equivalencia de las desigualdades

(\binom{n}{k}) < (\binom{n}{k + 1})

${n \choose k} < {n \choose k+1}$ y

k + 1 < n - k

$k+1 < n-k$ se obtiene contando subconjuntos. Quizás esto responda a su pregunta; si no es así, ¿de qué manera no es una respuesta? (En mi experiencia, "prueba combinatoria" no significa lo mismo para todos).

Martín Sleziak

@MichaelLugo Sí, hay una prueba que es combinatoria. Tal vez debería haberlo señalado explícitamente en la pregunta. Aún así, me gustaría ver algunos otros enfoques combinatorios. (Por ejemplo, recuerdo vagamente que vi una prueba de esto usando caminos de celosía).

Nate

Notaré que la prueba que di que @MichaelLugo mencionó puede fortalecerse (usando el teorema de coincidencia de Hall) para mostrar algo un poco más fuerte: si

k + 1 < n - k

$k+1 < n-k$ existe una función inyectiva

f

$f$ de

k

$k$ subconjuntos de elementos para

k + 1

$k+1$ subconjuntos tales que

S \subset f (S)

$S \subset f(S)$ para todos

S

$S$ . Si alguien tiene otra buena prueba de este fortalecimiento, me encantaría verla.

Miguel Lugo

@Nate: ese fortalecimiento me parece "más combinatorio" que la prueba original, aunque es difícil precisar exactamente por qué.

Respuestas (2)

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

La respuesta en math.stackexchange.com/a/880528/173 parece ser una prueba combinatoria de este hecho: ahí está la equivalencia de las desigualdades ${n \choose k} < {n \choose k+1}$ y $k+1 < n-k$ se obtiene contando subconjuntos. Quizás esto responda a su pregunta; si no es así, ¿de qué manera no es una respuesta? (En mi experiencia, "prueba combinatoria" no significa lo mismo para todos).
@MichaelLugo Sí, hay una prueba que es combinatoria. Tal vez debería haberlo señalado explícitamente en la pregunta. Aún así, me gustaría ver algunos otros enfoques combinatorios. (Por ejemplo, recuerdo vagamente que vi una prueba de esto usando caminos de celosía).
Notaré que la prueba que di que @MichaelLugo mencionó puede fortalecerse (usando el teorema de coincidencia de Hall) para mostrar algo un poco más fuerte: si $k+1 < n-k$ existe una función inyectiva $f$ de $k$ subconjuntos de elementos para $k+1$ subconjuntos tales que $S \subset f(S)$ para todos $S$ . Si alguien tiene otra buena prueba de este fortalecimiento, me encantaría verla.
@Nate: ese fortalecimiento me parece "más combinatorio" que la prueba original, aunque es difícil precisar exactamente por qué.

daniel pescador · Answer 1

Dejar $A$ ser un conjunto con $n$ elementos. la involución $S \mapsto A\setminus S$ muestra que $\binom{n}{k} = \binom{n}{n-k}$ para $0 \leqslant k \leqslant n$ , por lo que podemos restringir nuestra atención a $k \leqslant m := \bigl\lfloor \frac{n}{2}\bigr\rfloor$ .

Supongamos que queremos seleccionar un comité de $m$ personas, entre las cuales $k$ representará al comité ante el mundo exterior de un grupo de $n$ gente. Podemos

Selecciona el $m$ primero los miembros del comité y luego elegir a los $k$ representantes de los miembros del comité después. Eso es posible en $\binom{n}{m}\cdot \binom{m}{k}$ maneras.
Primero elige el $k$ representantes de todo el grupo y, a continuación, seleccione el resto $m-k$ miembros del comité de los restantes $n-k$ miembros del grupo. Eso es posible en $\binom{n}{k}\cdot \binom{n-k}{m-k}$ maneras.

Usando la simetría de los coeficientes binomiales, se sigue que

\begin{matrix} (1) & (\binom{norte}{metro}) = \frac{(\binom{norte - k}{metro - k})}{(\binom{metro}{metro - k})} \cdot (\binom{norte}{k}) . \end{matrix}

$\binom{n}{m} = \frac{\binom{n-k}{m-k}}{\binom{m}{m-k}}\cdot \binom{n}{k}.\tag{1}$

Ahora notamos que para $0 \leqslant r \leqslant s \leqslant t$ tenemos

\begin{matrix} (2) & (\binom{s}{r}) ⩽ (\binom{t}{r}), \end{matrix}

$\binom{s}{r} \leqslant \binom{t}{r},\tag{2}$

con igualdad si y solo si $s = t$ o $r = 0$ .

Desde $n-k \geqslant n-m \geqslant m$ , usando la desigualdad $(2)$ en $(1)$ muestra lo deseado

(\binom{norte}{metro}) ⩾ (\binom{norte}{k}),

$\binom{n}{m} \geqslant \binom{n}{k},$

con igualdad si y solo si $k = m$ .

Mike Earnest · Answer 2

Alquiler $S_k$ Sea el conjunto de subconjuntos de $\{1,2,\dots,n\}$ de tamaño $k$ , definiré una inyección de $S_k$ a $S_{k+1}$ cuando sea $2k\le n$ , y de $S_{k+1}\to S_k$ cuando sea $2k\ge n$ . Esto prueba que $|S_k|$ se maximiza cuando $k=\lfloor n/2 \rfloor$ .

Dado un conjunto en $X\in S_k$ , hacer una cadena de $n$ Paranatheses abiertas y cerradas, donde el $i^{th}$ el símbolo es un ")" si $i\in S$ , y es un "(" de lo contrario. Por ejemplo, cuando $n=18$ , $k=7$ ,

X = {1,5,6,8,12,14,15}

)  (  (  (  )  )  (  )  (  (  (  )  (  )  )  (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18

Ahora, elimine cualquier paréntesis que coincida, lo que significa un (seguido de un ). Continúe eliminando pares coincidentes, ya que eliminar un par puede crear nuevos pares, hasta que no quede ninguno. El resultado en el ejemplo es

)  (                    (                    (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18

Tenga en cuenta que hay más (s que )s en lo que queda; esto se debe a que comenzamos con un conjunto cuyo tamaño era más pequeño que $n/2$ , y el desequilibrio se mantiene cuando eliminamos pares coincidentes. En particular, siempre habrá al menos uno (. El mapeo se logra volteando el extremo izquierdo (a ), luego agregando nuevamente los mismos pares eliminados para recuperar un conjunto.

)  )  (  (  )  )  (  )  (  (  (  )  (  )  )  (  (  (  
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 

f(X) = {1,2,5,6,8,12,14,15}

Si en cambio hubiéramos comenzado con un conjunto grande, habríamos volteado el extremo derecho )a un (.

Esta es una inyección porque el proceso es reversible; hacer el volteo no afecta ninguno de los pares coincidentes, por lo que siempre podemos saber qué símbolo se volteó eliminando todos los pares coincidentes y encontrando el más a la derecha )o el más a la izquierda (.

Un tecnicismo menor es todo, pero creo que deberíamos estar usando $<$ y $>$ en vez de $\leq$ y $\geq$ para la inyección

Prueba combinatoria de que los coeficientes binomiales centrales son los más grandes

Martín Sleziak

Miguel Lugo

Martín Sleziak

Nate

Miguel Lugo

Respuestas (2)

daniel pescador

Mike Earnest

Colm Bandal

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Prueba combinatoria para series de números de Stirling y coeficientes binomiales

Interpretación combinatoria de la identidad: ∑j=0b(bj)2(n+j2b)=(nb)2∑j=0b(bj)2(n+j2b)=(nb)2\sum\limits_{j=0} ^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2

Cómo probar que (nr)(nr)n \choose r = n+1−rrn+1−rr\frac{n+1-r}{r} (nr−1)(nr−1)n \choose r -1 sin usar la expansión factorial de (nr)(nr)n \choose r? [cerrado]

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Prueba combinatoria de identidad de tipo binomial

Verificación de la solución: Demuestre que ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an− i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} para n ≥1n≥1n\geq 1

Prueba combinatoria de ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Prueba combinatoria y algebraica de una identidad que implica números de Stirling de segunda clase {n+1k+1}=∑i(ni){ik}{n+1k+1}=∑i(ni){ik}{n+1 \brace k+1}=\sum_i \binom{n}{i}{i\brace k}

Explicación combinatoria de por qué n2=(n2)+(n+12)n2=(n2)+(n+12)n^2 = {n \elegir 2} + {n+1 \elegir 2}