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.

What are the number of ways of dividing $n_1$ objects of type $1$, $n_2$ objects of type $2,\ldots,n_k$ objects of type $k$ into 2 equal parts?

Note: take $\sum n_i=2n$ so that each part contains $n$ objects.

share|improve this question
    
can you give a simple example? Not sure what this question is asking and the answer to it didn't help me in understanding the question either. –  Arjang Feb 7 '13 at 21:56
add comment

1 Answer

I'll give two solutions. One is the generating function, and the other is an exact (but messy) answer using inclusion/exclusion.

First, the problem is equivalent to finding the number of integer solutions to $x_1 + x_2 + \cdots + x_k = n$, where $0 \leq x_j \leq n_j$. This is because we need to select $n$ total items from the $k$ groups, with the restriction that we can't select any more than $n_j$ objects from group $j$, to form the first part. Once that selection is made, the second part is completely determined.


Generating function.

Problems of finding the number of integer solutions to an equation subject to certain restrictions are a classic use of generating functions. In fact, these types of problems are often used to motivate generating functions in introductory combinatorics texts. (For example, see Tucker's Applied Combinatorics.)

Anyway, the generating function is $$f(x) = \prod_{j=1}^k \left(\sum_{i=0}^{n_j} x^i \right).$$ So the answer to your question is the coefficient of $x^n$ in this expression.

But why is this? Well, the problem of finding the number of integer solutions to $x_1 + x_2 + \cdots + x_k = n$, where $0 \leq x_j\leq n_j$, is the same as finding the number of ways to choose integers $x_1, x_2, \ldots, x_k$ with $0 \leq x_j\leq n_j$ so that we have $x^{x_1} x^{x_2} \cdots x^{x_k} = x^n$. Now, for $x_1$ we can choose the factor to be $x^0$ or $x^1$ or $x^2$, and so forth, up to $x^{n_1}$. Expressing the "or" as addition, this can be represented as $1 + x + x^2 + \cdots + x^{n_1}$. Similarly, we can represent the choices for $x_2$ as $1 + x + x^2 + \cdots + x^{n_2}$, and so forth, up to the choices for $x_k$ as $1 + x + x^2 + \cdots + x^{n_k}$. Now, we need to choose one of the $x_j$'s for each $j$. Representing "and" by multiplication, we get that the expression $f(x)$ above represents in some sense the different ways to choose the $x_j$'s. Moreover, expanding $f(x)$ in powers of $x$, we can see that any term with $x^n$ encodes a way to choose an $x_1$, an $x_2$, and so forth, so that $x_1 + x_2 + \cdots + x_k = n$. The coefficient of $x^n$ in $f(x)$ therefore must be the number of solutions to $x_1 + x_2 + \cdots + x_k = n$, where $0 \leq x_j\leq n_j$.


Exact answer using inclusion/exclusion.

The number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_k = n$ with no restrictions is $\binom{n+k-1}{k-1}$. This is a classic application of the stars and bars argument. Any ordering of $n$ stars and $k-1$ bars determines a solution to this equation, and vice versa. You just have to select the positions of the bars, and then the stars are in the remaining positions.

Now, let $A_k$ be the set of solutions to $x_1 + x_2 + \cdots + x_k = n$ with $x_j \leq n_j$. We want $$|A_1 \cap A_2 \cap \cdots \cap A_k|.$$

To calculate this we can use the principle of inclusion and exclusion. We need $|A_j'|$, which is the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_k = n$ with $x_j \geq n_j+1$. Since there are $n_j+1$ places where we cannot put bars, we have $|A_j'| = \binom{n+k-n_j-2}{k-1}$. Similarly, $|A_i' \cap A_j'| = \binom{n+k-n_i - n_j-3}{k-1}$, and so forth.

Applying inclusion/exclusion, then, the answer is \begin{align} |A_1 \cap A_2 \cap \cdots \cap A_k| = &\binom{n+k-1}{k-1} - \sum_{j=1}^n \binom{n+k-n_j-2}{k-1} + \sum_{j_1 < j_2} \binom{n+k-n_{j_1} - n_{j_2} -3}{k-1} \\ &- \cdots + (-1)^i \sum_{j_1 < j_2 < \cdots < j_i} \binom{n+k- \sum_{\ell=1}^i n_{j_\ell} - i -1}{k-1} \\ &+ \cdots + (-1)^k \binom{n+k- 2n - k -1}{k-1}. \end{align} In practice you won't need to go all the way to the end with the calculations because after a while the binomial coefficient values (such as the last one) will all be $0$.

share|improve this answer
add comment

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.