Buscando una biyección entre este conjunto y los números naturales

Question

Soy programador informático, y estoy luchando con este problema matemático sin encontrar una solución consistente y eficiente.

Dejemos que $A_{k, M}$ sea el conjunto de todas las posibles asignaciones para $n_1, n_2, ...,n_k$ enteros no negativos tales que $\sum_{i=1}^{k}{n_i} = M$ . Necesito calcular $C_{k,M}=|A_{k, M}|$ para la arbitrariedad $k, M$ y necesito una biyección entre $A_{k, M}$ y $[0, C_{k,M}-1]$ . La biyección debe ser sencilla de calcular "en ambas direcciones" y no debe requerir una enumeración exhaustiva.

Ejemplo. $k = 3$ , $M = 3$ . Las posibles asignaciones son $\{3, 0, 0\}, \{0, 3, 0\}, \{0, 0, 3\}, \{0, 1, 2\}, \{0, 2, 1\}, \{1, 0, 2\}, \{2, 0, 1\}, \{1, 2, 0\}, \{2, 1, 0\}, \{1, 1, 1\}$ Por lo tanto $C_{k,M}=|A_{k, M}| = 10$ .

He investigado poco hasta ahora, he mirado los sistemas numéricos combinatorios/factoriales (podéis suponer que sé de qué van) pero el problema parece ser bastante diferente. ¿Pueden darme algunas indicaciones?

EDITAR : Aclaro algunos puntos como se pide. 1) En realidad no sé que exista una biyección "sencilla de calcular", pero sí sé que mi incapacidad para encontrarla no es prueba de su inexistencia, por lo que pido aquí tu consejo. 2) Los dos conjuntos son: $A_{k, M} = \{ (n_1, n_2, ...,n_k) : \sum_{i=1}^{k}{n_i} = M \}$ y $[0, |A_{k, M}|-1] \subset \{ \mathbb{N} \cup \{0\} \}$ .

Answer 1

Por el método de las estrellas y las barras existe una biyección entre $A_{k,M}$ y el conjunto de $k-1$ -subconjuntos de $\{1,2,\dots,M+k-1\}$ .

Esencialmente, $n_1,n_2,\dots,n_k$ va a $\{n_1+1,n_1+n_2+2,\dots,n_1+\dots+n_{k-1}+k-1\}$ .

El conjunto de $m$ -subconjuntos de $\{1,2,\dots,N\}$ se pueden dar índices en $\{0,1,\dots,\binom{N}m-1\}$ a través de la ordenación aplastada, donde $1\leq a_1<a_2<\dots<a_m\leq N$ se asigna al número entero:

$$\sum_{j=1}^m \binom{a_j-1}{j}$$

El mapa inverso, sin embargo, no es tan fácil.

Para calcular el mapa inverso, dado un índice $I$ , encontrar el mayor $a_m$ para que $\binom{a_m-1}{m}\leq I$ . Entonces, si sabes $a_{k+1},\dots,a_m$ encontrar el mayor $a_k$ para que $$\binom{a_k-1}{k} \leq I-\sum_{j=k+1}^m \binom{a_j-1}{j}$$

[Nótese que, en todo lo anterior, estamos asumiendo que si $a<b$ entonces $\binom{a}{b}=0$ .]