Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
No, these are compositions, not partitions. –  user02138 Sep 4 '11 at 21:34
    
Oh, my mistake. Sorry for not reading closely enough; I'll delete my comment. –  Arturo Magidin Sep 4 '11 at 21:41
    
No worries. There is a very subtle difference between the two: order. –  user02138 Sep 4 '11 at 21:47

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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