número de multiíndices de un orden fijo que son menores que un multiíndice dado

Question

Queridos todos,

Tengo el siguiente problema que me parece bastante estándar pero sin embargo estoy atascado ahora mismo.

Dado un número entero positivo $n$ y un índice múltiple $p \in \mathbb{N}_0^n$ Quiero contar el número de multiíndices $k \in \mathbb{N}_0^n$ que están dominados por $p$ (es decir, cada componente de $k$ es menor o igual que el componente correspondiente de $p$ ) y cuyos componentes suman un número entero positivo dado $s$ . Para expresarlo de otra manera, me interesa la cardinalidad del conjunto

$C(n,s,p) = \{ k = (k_1, \ldots, k_n) \in \mathbb{N}_0^n \mid k \leq p, |k| = s\}$ .

Sin la condición $k \leq p$ He encontrado una solución por recursión (que supongo que no es la forma más elegante). ¿Alguien tiene alguna sugerencia para la cardinalidad general?

Saludos,

Simon

Answer 1

El número de soluciones de la ecuación $a_{1}+a_{2}+\cdots+a_{n}=k$ donde $s>a_{i}\geq0$ , $a_{i}\in\mathbb{N}$ por todo lo que es (a no ser que haya cometido un error tipográfico) $\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\binom{n+k-js-1}{n-1}$

Answer 2

Ampliando mi comentario en una respuesta completa:

Por inspección, podemos ver que $C(n,s,p)$ es el coeficiente de $x^s$ en:

$(1 + x + x^2 + \cdots + x^{p_1}) (1 + x + x^2 + \cdots + x^{p_2}) \cdots (1 + x + x^2 + \cdots + x^{p_n})$

$= \Pi_{j=1}^n \Sigma_{i=0}^{p_j} x^i $

$= \Pi_{j=1}^n {{(x^{p_j+1}-1)}\over{(x-1)}}$

No soy especialmente experto en generar funciones, así que no he podido reducir esto a una expresión más agradable (de forma cerrada). Tal vez más tiempo de estudio de Wilf Generación de funciones dará mejores resultados.

El solicitante también menciona el caso especial en el que el $k \leq p$ se ignora la restricción (lo que equivale a la situación cuando $p_i \geq s$ para todos $i$ ). En este caso, podemos obtener una fórmula mejor. Sea $C(n,s)$ denotan la cantidad deseada.

En primer lugar, recordamos la definición del composición de un número entero. A continuación, observamos que hay ${s-1}\choose{i-1}$ composiciones de $s$ en $i$ (no cero) y que hay ${n}\choose{i}$ formas de distribuirlas $i$ partes en el $n$ índices (dejamos que los otros $n-i$ sean cero). Así, tenemos $$C(n,s) = \Sigma_{i=1}^{min(n,s)} {{s-1}\choose{i-1}} {{n}\choose{i}}$$