¿Cuántas combinaciones podemos crear a partir de esta estructura?

Question

Estoy atascado en este problema, y realmente necesito tu ayuda. Lo siento si el título no es muy informativo. Es realmente difícil para mí explicar en una sola frase. Hago mi mejor esfuerzo en explicarlo:

Existe estos dos naturales enteros:

m $\in \mathbb{N}$
$a_i \in \mathbb{N}$ para $i=1 \cdots m$

y algún objeto con el que puedo crear una estructura como esta:
$$\matriz{ 1_1 & 1_2 & ... & 1_m \\ 1_1,2_1&1_2,2_2&...&1_m,2_m \\ 1_1,2_1,3_1 &1_2,2_2,3_2 & \ldots & 1_m,2_m,3_m \\ \vdots & \vdots & \vdots & \vdots \\ 1_1,2_1,...,a_1 & 1_2,2_2,...,a_2, &\ldots & 1_m,2_m,...,a_m\\ }$$

Podemos crear un nuevo objeto mediante la colocación de objetos de diferentes columnas uno al lado de otro. Todas las combinaciones posibles tiene un formato general como este:

$$(1_1),(1_2),...,(1_m)\\ (1_1),(1_2,2_2),...,(1_m)\\ ...\\ (1_1),(1_2),...,(1_m,2_m)\\ (1_1,2_1),(1_2),...,(1_m)\\ (1_1,2_1),(1_2,2_2),...,(1_m)\\ ...\\ (1_1,2_1),(1_2),...,(1_m,2_m)\\ ...\\ ...\\ (1_1,2_1,...,a_1),(1_2,2_2,...,a_2),...,(1_m,2_m,...,a_m)$$

He añadido el parenthesizes para hacerla más clara. El orden no es importante

En otras palabras, creo que todos la combinación de los objetos en el primer, segundo y ... y $a_1-th$ filas de la primera columna con los de la primera, segunda y ... y $a_2-th$ filas de la segunda columna y así sucesivamente. Cada una de estas combinaciones no es un elemento de cada columna.

Creo que todas las combinaciones posibles es $a_1 \times a_2 \times ... \times a_m$.

Pero, Hay una restricción en el número de objetos en cada una de estas combinaciones. vamos a ser $$h\in \mathbb{N}$$ Número de objetos en una combinación no puede ser mayor que el $h$.

Ahora, la pregunta es:
cuántas combinaciones existentes no satisfacen esta condición? (El orden no es importante)

Gracias por tu ayuda.

Answer 1

El problema es equivalente a la siguiente. Deje $N_k=\{1,\dots,a_k\}$ para $k=1,\dots,m$. Vamos $$G=\left\{\langle i_1,\dots,i_m\rangle\in\prod_{k=1}^mN_k:\sum_{k=1}^mi_k\le h\right\}\;;$$ you want to know $|G|$ in terms of $h m$, and the numbers $a_k$ for $k=1,\dots,m$.

Esto es equivalente a pedir el número de soluciones de la ecuación

$$x_1+\ldots+x_m+x_{m+1}=h-m\tag{1}$$

en enteros no negativos sujetos a los límites superiores $x_k\le a_k-1$ para $k=1,\dots,m$: una solución de $\langle x_1,\dots,x_{m+1}\rangle$ corresponde a $\langle x_1+1,\dots,x_m+1\rangle\in G$, con $x_{m+1}=h-\sum_{k=1}^mi_i$. Sin los límites superiores este es un estándar de estrellas-y-bares problema, y $(1)$ ha $\binom{h}m$ soluciones en enteros no negativos.

Para dar cuenta de los límites superiores, una inclusión-exclusión en el cálculo es necesario. La sustitución de $x_k$ por $y_k=x_k-a_k$ y contando soluciones en enteros no negativos a

$$x_1+\ldots+x_{k-1}+y_k+y_{k+1}+\ldots+x_{m+1}=h-m-a_k$$

da el número de soluciones a $(1)$ que exceden el límite superior en $x_k$; por las estrellas y las barras de cálculo que el número es $\binom{h-a_k}m$. Restando estas de $\binom{h}m$ da la aproximación $$\binom{h}m-\sum_{k=1}^m\binom{h-a_k}m\;.\tag{2}$$

Esto no es correcto, sin embargo, ya que es posible que algunas de las soluciones a $(1)$ exceder más de un límite superior, y cualquier tipo de solución ha sido sustraída dos veces en $(2)$. Si $1\le i<k\le m$, el número de soluciones a $(1)$ que superan los límites superiores en ambos $x_i$ e $x_k$ es $\binom{h-a_i-a_k}m$, y cada uno de estos números debe ser agregado en a $(2)$ a producir la siguiente aproximación, $$\binom{h}m-\sum_{k=1}^m\binom{h-a_k}m+\sum_{1\le i<k\le m}\binom{h-a_i-a_k}m\;.$$ Continue in this fashion, alternately adding and subtracting the corrections. If we let $[m]^k$ denote the collection of $k$-element subsets of $\{1,\puntos,m\}$, el resultado final es

$$\sum_{k=0}^m(-1)^k\sum_{S\in[m]^k}\binom{h-\sum\limits_{i\in S}a_i}m\;.\tag{3}$$

Eso es un poco feo, pero si $h$ no es demasiado grande en comparación con los límites $a_i$, la mayor parte de los términos de $(3)$ será $0$, ya que el número superior en los coeficientes binomiales no va a ser positivo para todos, pero los pequeños valores de $k$.