Composiciones de$n$ con la mayor parte a lo sumo$m$

Question

Este es un problema de Stanley Combinatoria Enumerativa que estoy fallando un poco (mucho):

Deje $\bar{c}(m,n)$ denotar el número de composiciones de $n$ con la parte más grande en la mayoría de las $m$. Mostrar que $$\sum_{n\geq 0}\bar{c}(m,n)x^n={{1-x}\over{1-2x+x^{m+1}}}$$

Algunas definiciones: Una composición de $n$ $ordered$ lista de enteros positivos que equivale a $n$. Si $\{a_1,...,a_k\}$ es uno de esos composición, podemos decir que la composición ha $k$ $parts$.

Sé que es bastante tradicional a la lista de "lo que hemos hecho hasta ahora", pero de verdad que estoy tan ciegamente se pega como puede ser.

Answer 1

He probado mi propio camino y tiene algo ligeramente diferente, más que en un segundo. Deje $c(m,n,k)$ el número de enteros composiciones con largers parte $\le m$ y exactamente $k$ partes. Entonces

$$\sum_n c(m,n,k)x^n=\left.\sum_{p_1=1}^m\cdots\sum_{p_k=1}^m x_1^{p_1}\cdots x_k^{p_k}\right|_{x_1=x_2=\cdots=x_k=x}=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$

y por lo tanto

$$\sum_n c(m,n)x^n=\sum_n\left[\sum_{k\ge1}c(m,n,k)\right]x^n=\sum_{k\ge1}\sum_nc(m,n,k)x^n$$

$$=\sum_{k\ge1}\left(x\frac{1-x^m}{1-x~~~}\right)^k=\frac{\displaystyle x\frac{1-x^m}{1-x~~~}}{\displaystyle 1-x\frac{1-x^m}{1-x~~~}}=\frac{x(1-x^m)}{1-2x+x^{m+1}}.$$

Tenga en cuenta que

$$\frac{x(1-x^m)}{1-2x+x^{m+1}}=\frac{1-x}{1-2x+x^{m+1}}-1,$$

así que la respuesta y la mía se diferencian simplemente por $1$. ¿Cuál es el trato? La razón por la que debemos agregar $1$ supongo que $n=0$ tiene un número entero de la composición, es decir, el conjunto vacío (es el vacío de la suma). Al menos eso es lo que OEIS dice, realmente no he visto el libro de texto de la definición/convenio para $0$.

Answer 2

Esto se puede solucionar de dos maneras, ambas bastante fácil.

Para la primera, en cuenta que la fracción simplifica debido a la descomposición $1-2x+x^{m+1}=(1-x)(1-x-x^2-\cdots-x^m)$ a la función racional $$ \frac1{1-x-x^2-\cdots-x^m}. $$ Los coeficientes $a_i$ de la potencia correspondiente de la serie satisfacer $a_0=1$ y la recurrencia $$ a_i=a_{i-1}+a_{i-2}+\cdots+a_m \qquad\text{para $i>0$,} $$ donde los términos con la negativa del índice son la$~0$. Pero tomando las $a_i=\bar c(n,i)$ esta recurrencia puede ser visto fácilmente para estar satisfecho: una composición de $i>0$ tiene una parte final$~k$$1\leq k\leq m$, y quitando la parte de las hojas que la composición de la $i-k$ en partes en la mayoría de las$~m$, obtuvieron cada uno exactamente una vez, por lo $\bar c(n,i)=\sum_{k=1}^m\bar c(n,i-k)$.

La otra forma es usar el formulario de la fracción dada en la pregunta directamente. Su denominador indica que la recurrencia $ a_i=2a_{i-1}-a_{i-(m+1)} $ debe ser satisfecho suficientemente grande$~i$. Aquí cada la composición de $i$ puede obtenerse de dos formas a partir de una composición de $i-1$: la adición de una parte $1$, o por el aumento de la última parte por$~1$. Sin embargo este método no puede aplicarse a todas las composiciones de $i-1$ en partes en la mayoría de las $m$, ya que puede hacer que la parte final $m+1$. El número de tales prohibido extensiones es igual a $\bar c(n,i-(m+1))$ (de cada la composición de la cuenta por ese número se produce cuando una $m+1$ añadido en su extremo), por lo que el número debe ser restado de la recurrencia. Con la convención de que la recurrencia de términos con índices negativos son para ser llevado a $0$, la recurrencia de la relación le da la correcct número de $i>1$, pero el valor de$~2$ daría para $i=1$ es uno demasiado (ya que la composición de $0$ no tiene parte en aumento). Esto se refleja por el término "$-x$" en el numerador de la fracción $\frac{1-x}{1-2x+x^{m+1}}$.

Answer 3

Hazy idea: intentaría derivar una relación$(\dagger)$ entre por ejemplo$\bar{c}(m, n)$ y$\bar{c}(m, n-1)$ (o incluso con varios términos$\bar{c}(m, n-k)$), o algo similar. El objetivo sería encontrar un EDP para$f\colon x \to \sum_{n=0}^\infty \bar{c}(m, n)x^n$ diferenciando términos por términos y usando$(\dagger)$. Luego, al tomar el EDP para$f$, uno podría obtener una expresión de forma cerrada de la misma - esperemos que la que se le pide que demuestre.

Por supuesto, el paso principal es encontrar (vía combinatorics?) Dicha relación.