Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am given $m$ ordered "free spaces" and $k$ disjoint sets $\mathcal{S} = \{S_1, \ldots, S_k\}$, where the $S_i$ contains $n_i > 0$ elements.

In how may ways can I fill up the free spaces with elements from sets in $\mathcal{S}$, s.t. for each $S_i$ between 1 and $n_i$ elements are picked, and that all elements from $S_i$ are added to the free spaces after the elements of $S_{i-1}$ and before $S_{i+1}$?

I see some connection to stirling numbers of second kind, but the upper bound of $n_i$ make the problem more difficult. Also the stirling number counts the number of ways to partition the set into non empty unlabeled subsets, but since we have the constraint that lements from $S_i$ are added to the free spaces after the elements of $S_{i-1}$ and before $S_{i+1}$ we have labeled subsets.

share|cite|improve this question
up vote 0 down vote accepted

It seems like you basically need to find the number solutions to

$$x_1 + x_2 + \dots + x_k = m$$

with $ 1\le x_i \le n_i$.

Those can be computed using generating functions as in here: An efficient method for computing the number of submultisets of size n, of a given multiset

share|cite|improve this answer
Yes and in the generating function only the $1-x^{m_i+1}$ terms change to $x(1-x^{m_i})$ since $x_i > 0$ – alex Feb 9 '12 at 19:36
@alex: Yes, you use $x + x^2 + \dots + x^{n_i}$. – Aryabhata Feb 9 '12 at 19:46

Your Answer


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.