# Drawing Elements from Multiple Sets

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.

-

## 1 Answer

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

-
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