7
$\begingroup$

Let $c_{k}(N;[a,b])$ denote the number of compositions of $N$ into $k$ parts, where each part is restricted to the interval $[a,b]$, i.e., $N = \sum_{i = 1}^{k} s_{i}$ with $a \leq s_{i} \leq b$. The generating function of $c_{k}(N;[a,b])$ is \begin{align} G(c_{k}(N; [a,b]);t) = t^{ka} \left( \frac{1-t^{b-a+1}}{1-t} \right)^{k}, \end{align} Hence, $c_{k}(N;[a,b]) = [t^{N}] G(c_{k}(N; [a,b]);t)$.

For example, if $N = 8$, $a = 1$, $b = 3$ and $k = 4$, then \begin{align} c_{4}(8;[1,3]) = [t^{8}]t^{4} \left( \frac{1-t^{3}}{1-t} \right)^{4} = [t^{8}] (t^{4} + 4 t^{5} +10 t^{6} + 16 t^{7} + 19 t^{8}) = 19. \end{align} The nineteen positive compositions of $8$ into $4$ parts no greater than $3$ are $2 + 2 + 2 + 2$, as well as, $1 + 1 + 3 + 3$, $1 + 3 + 1 + 3$, $1 + 3 + 3 + 1$, $1 + 2 + 2 + 3$, $1 + 2 + 3 + 2$, $1 + 3 + 2 + 2$, $2 + 1 + 2 + 3$, $2 + 1 + 3 + 2$, $2 + 2 + 1 + 3$, $2 + 2 + 3 + 1$, $2 + 3 + 1 + 2$, $2 + 3 + 2 + 1$, $3 + 1 + 2 + 2$, $3 + 2 + 1 + 2$, $3 + 2 + 2 + 1$, $3 + 1 + 1 + 3$, $3 + 3 + 1 + 1$ and $3 + 1 + 3 + 1$.

What about products of generating functions? For example, what combinatorial information is encoded in the following: \begin{align} [t^{N}]t^{4} \left( \frac{1-t^{3}}{1-t} \right)^{4} t^{5} \left( \frac{1-t^{2}}{1-t} \right)^{3}, \end{align} where $N$ is again a positive integer?

More generally, is there a nice combinatorial interpretation of the following coefficient in terms of restricted compositions, \begin{align} [t^{N}]\prod_{i = 1}^{m} t^{\alpha_i} \left( \frac{1-t^{\beta_i}}{1-t^{\gamma_i}} \right)^{k_i}, \end{align} where $\alpha_i, \beta_i, \gamma_i, m, N$ and $k_i$ are positive integers? (NB: In general, the coefficient will be rational, but one can add simple relations on the coefficients $\beta_i, \gamma_i$ and $k_i$ to ensure integrality.)

  • 0
    No worries. There is a very subtle difference between the two: _order_.2011-09-04

1 Answers 1

2

The $\alpha_i$ really contribute nothing and can simply be subtracted from $N$.

For the rest, if $\gamma_i$ divides $\beta_i$, you are looking for compositions of $N$ (minus the sum of the alphas) that start with $k_1$ terms at most $\beta_1$ and divisible by $\gamma_1$ then $k_2$ terms with the analogous properties and so on.

If you have other "simple relations" in mind that ensure integrality you could clarifiy this in the question.