¿Cómo expresar esta combinación en forma de fórmula?

Question

Supongamos que tengo un conjunto infinito $A(z)$ donde los elementos del conjunto son:

$$ A(z) = \{z^0,z^1,z^2,...\} $$

Quiero obtener el número de formas en que puedo combinar sus elementos si multiplico el conjunto consigo mismo, donde la multiplicación es una operación que da como resultado otro conjunto (llamemos a este conjunto el producto). El producto tiene coeficientes para cada elemento que cuenta el número de formas en que se produjo a partir de la multiplicación. Por ejemplo,

$$ A(z)^2=A(z)A(z)=\{z^0z^0,z^0z^1,z^1z^0,z^1z^1,z^0z^2,z^2z^0,z^1z^2,z^2z^1,...\}=\{z^0,2z^1,3z^2,....\} $$

Así que en $A(z)^2$ el coeficiente de $z^1$ es $2$ ya que hay dos maneras de llegar a $z^1$ de $A(z)^2$ es decir $\{z^0z^1,z^1z^0\}$ . El coeficiente de $z^2$ es $3$ ya que hay tres maneras de llegar a $z^2$ de $A(z)^2$ que son $\{z^0z^2,z^2z^0,z^1z^1\}$ ...

Ahora me gustaría preguntar, ¿existe una fórmula que pueda calcular los coeficientes de los elementos de a $k$ -producto, es decir $A(z)^k$ ...

Answer 1

¡Has descubierto la idea de generar funciones! Utilicemos la notación estándar $\left[z^n\right]F(z)$ para denotar el coeficiente de $z^n$ en $F$ . Entonces podemos definir el anillo de series formales de potencias por la regla de la multiplicación:

$$\left[z^n\right]\left(A(z)B(z)\right) = \sum_{k=0}^{n}\left[z^k\right]A(z)\left[z^{n-k}\right]B(z)$$

Si las series de potencias tienen radio de convergencia positivo, esto corresponde a la multiplicación de las funciones correspondientes. También corresponde a su noción de multiplicación de "conjuntos". La serie (ordinaria) función generadora de una secuencia es la serie de potencias formal que tiene la secuencia como coeficientes. Por ejemplo, consideremos la cosa que usted anotó de forma un tanto abusiva como $A(z)=\left\{z^0,z^1,z^2,\ldots\right\}$ . Esto puede representarse mediante una serie de potencias formal que resulta ser convergente para $|z|<1$ :

$$A(z)=1+z+z^2+...=\sum_kz^k=\frac{1}{1-z}$$

que es la función generadora de la secuencia $1,1,1,\ldots$ Los poderes de $A(z)$ por su regla de multiplicación simplemente da las potencias de $A(z)$ como función, por ejemplo:

$$A(z)^2=\frac{1}{(1-z)^2}=\frac{d}{dx}\frac{1}{1-x}=\sum_{k}(k+1)z^k$$

es la función generadora de la secuencia $1,2,3,\ldots$ En general:

$$A(z)^n=\frac{1}{(1-z)^n}=\sum_{k}\binom{n+k-1}{k}z^k$$ así que los coeficientes que estás buscando son:

$$\left[z^k\right]A(z)^n=\binom{n+k-1}{k}$$