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.)

$\endgroup$
3
  • $\begingroup$ No, these are compositions, not partitions. $\endgroup$ – user02138 Sep 4 '11 at 21:34
  • $\begingroup$ Oh, my mistake. Sorry for not reading closely enough; I'll delete my comment. $\endgroup$ – Arturo Magidin Sep 4 '11 at 21:41
  • $\begingroup$ No worries. There is a very subtle difference between the two: order. $\endgroup$ – user02138 Sep 4 '11 at 21:47
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.