Extraña desigualdad que involucra coeficientes binomiales *anidados* e interpretación combinatoria

Hay un lindo argumento para$b=c+1$aunque no sé cómo sacarlo adelante en el caso general.

Dejar$U$Sea el conjunto de ordenados $c+1$-tuplas de conjuntos de cardinalidad$c$en el que no se repite ningún conjunto. Entonces, obviamente,$|U|=(c+1)!{{n\choose c}\choose c+1}$. Dejar$V$Sea el conjunto de ordenados$c$-tuplas de conjuntos de cardinalidad$c+1$en el que no se repite ningún conjunto. Entonces$|V|=c!{{n\choose c+1}\choose c}$. Ahora toma cualquier elemento de$V$, es decir, una familia ordenada de conjuntos$A_1,\dots,A_{c}$. Tomar cualquiera$a_1\in A_1$($c+1$opciones). Suponer que$a_1\in A_1,\dots,a_k\in A_k$ya están elegidos. Entonces queremos elegir$a_{k+1}\in A_{k+1}$de modo que$a_{k+1}\ne a_j$y$A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$para todos$j=1,\dots,k$. Supongamos que tenemos$\ell$prohibiciones del primer tipo. Entonces, si las cumplimos, las prohibiciones del segundo tipo para los conjuntos correspondientes se cumplirán automáticamente (si$a_j\in A_{k+1}$y no lo quitamos, entonces seguramente$A_{k+1}\setminus \{a_{k+1}\}\ne A_j\setminus\{a_j\}$. El restante$k-\ell$conjuntos introducen como máximo una prohibición del segundo tipo cada uno, por lo que tenemos$\le k$prohibiciones totales. Así tenemos$\ge c+1-k$opciones para$a_{k+1}$. Una vez que ejecutamos todo el procedimiento, los conjuntos reducidos$A_j$enumerados en el mismo orden y el conjunto$\{a_1,\dots,a_c\}$enumerados en último lugar constituirán un elemento de$U$y cada elemento de$V$Generará$\ge(c+1)!$diferentes elementos de$U$(por diferentes opciones de$a_1,\dots,a_c$. Por otra parte, cada elemento de$U$se puede obtener como máximo$c!$elementos de$V$(esa es la cantidad de formas de distribuir los elementos de la última$c+1$-st puesto entre los primeros$c$. Esto da inmediatamente una desigualdad no estricta que desea. Para hacerlo estricto, debe asumir$c>1$y$n\ge c+1$(de lo contrario, tienes igualdad), en cuyo caso la secuencia ordenada de conjuntos$A_j=\{1,2,\dots,c+1\}\setminus\{j\}$tiene menos de$c!$opciones de distribución (ninguna en absoluto, en realidad) que dan como resultado un elemento legítimo de$V$.

Editar (el caso general)

En este caso será conveniente definir$U$como el conjunto de todos los ordenados$b$-tuplas de conjuntos de cardinalidad$c$tal que los conjuntos son pares diferentes (como conjuntos), el primero$c$los conjuntos están desordenados, y el último$b-c$se ordenan los conjuntos. Entonces$|U|=b!(c!)^{b-c}{{n\choose c}\choose b}$. Dejar$V$ser el mismo que antes (ordenado$c$-tuplas de subconjuntos desordenados de cardinalidad$b$en el que los conjuntos son diferentes por pares), por lo que$|V|=c!{{n\choose b}\choose c}$.

Ahora deja$\langle A_1,\dots, A_c\rangle$ser un elemento de$V$. queremos eliminar$b-c$elementos$a_{j,1},a_{j,2},\dots,a_{j,b-c}$de$A_j$y forma$b-c$nuevos conjuntos ordenados$B_k=\langle a_{1,k},a_{2,k},\dots, a_{c,k}\rangle$($k=1,\dots,b-c$) para obtener un elemento de$U$.

Con este fin, comience con la elección$a_{1,1},\dots,a_{1,b-c}\in A_1$de manera arbitraria, lo que da$b(b-1)\dots(b-c+1)$opciones Ahora bien, al elegir$a_{k+1,1}\in A_{k+1}$para$k\ge 1$, añadir a las prohibiciones estándar$a_{k+1,1}\ne a_{j,1}$,$A_{k+1}\setminus\{a_{k+1,1}\}\ne A_j\setminus\{a_{j,1}\}$($j\le k$), que excluyen como máximo$k$elementos como antes, las prohibiciones$a_{k+1,1}\ne a_{1,m}$($m>1$), que excluyen$b-c-1$elementos como máximo, dejando$c+1-k$opciones como antes. Estas prohibiciones adicionales garantizan que el conjunto$B_1=\{a_{1,1},a_{2,1},\dots, a_{c,1}\}$no contiene ninguno de los elementos$a_{1,m}$($m>1$) y, por lo tanto, será diferente de cada conjunto$B_m$($m>1$) como un conjunto desordenado y todavía tenemos$c!$opciones

Habiendo construido$B_1$, construimos$B_2$con las restricciones estándar$a_{k+1,2}\ne a_{j,2}$,$A_{k+1}\setminus\{a_{k+1,1},a_{k+1,2}\}\ne A_j\setminus\{a_{j,1},a_{j,2}\}$($j\le k$) y restricciones adicionales$a_{k+1,2}\ne a_{1,m}$pero ahora con$m>2$. Esto da$c!$opciones de nuevo, y así sucesivamente. Así, de cada elemento de$V$, obtenemos$b(b-1)\dots(b-c+1) (c!)^{b-c}$distintos elementos de$U$. La recuperación de un elemento de$V$de un elemento de$U$ahora es posible de una sola manera, si es que lo es, lo que, nuevamente, da una desigualdad no estricta. Te dejo a ti decidir cuándo y cómo se vuelve estricto en este caso.