Tag Archives: Generating functions

The four types of distribution problems

Posted on by

In MO, we are often concerned with the number of ways to distribute a certain number of objects into a certain number of boxes. Many SMO round 1 problems are modelled after specific cases of distribution problem. We will discuss the 4 main types of distribution problems in this post. Sticking to conventions, let n be the number of boxes while r be the number of objects throughout this post. Also, a multi-set is a set with repeated terms, such as (2 \cdot a_1, a_2, 3 \cdot a_3, \infty \cdot a_4).

Case 1: n distinct boxes, r distinct objects

We assume that each box has infinite capacity and can contain contain any amount of objects. For each object, you have n choices of boxes where you can place the object. Hence, by multiplication principle, we have \bold{n^r} possible ways to put r distinct objects in n distinct boxes.

Of course, this is a very simple computation which does not utilise the concept of permutation and combination at all. What is more likely to be asked in competitions is the number of ways of distributing the objects if the ordering of the objects in each boxes matters. If this is the case, let us label each object as a_1, a_2, \cdots, a_r respectively. Now consider the set (a_1, a_2, \cdots, a_n, (n-1) \cdot 1) where there are n-1 1s in the set. We shall treat these “1”s as partitions i.e. the objects between 2 “1”s represent the objects in a box. Essentially, we want to find the number of ways to arrange the items in the set. Since the partitions are identical, the number of ways is equal to:

\dfrac{^{r+n-1}P_{r+n-1}}{(n-1)!}=\dfrac{(r+n-1)!}{(n-1)!}

Case 2: n distinct boxes, r identical objects

This is the kind of situation that is most commonly modelled in SMO problems. The number of ways to place r identical objects into n distinct boxes is

\dbinom {r+n-1}{r}

To see this, let us consider a binary sequence with r 0s representing the objects and n-1 1s representing the partitions of the boxes. The problem is equivalent to finding the number of possible binary sequences with r 0s and n-1 1s, hence we obtain the above formula.

A popular corollary to this observation concerns the number of integer solutions to equations in the form x_1+x_2+\cdots+x_n=r. We can treat each variables as a box and the value at the right hand side of the equation as the number of identical objects. This problem is equivalent to distributing the amount of objects at the right hand side of the equation into the n variables on the left of the equation, and hence the number of solution is \dbinom {r+n-1}{r}.

More formally, we indicate that ^nH_r = \dbinom {r+n-1}{r}. The symbol ^nH_r represents the number of r-element multi-subset of a multi-set with n distinct objects.

I think it’s sufficient to familiarise with the above two scenarios for SMO(J) problems (or perhaps even SMO(S)). For people taking part in SMO(O), you may be interested in the following two cases as well:

Case 3: n identical boxes, r distinct objects

We denote the number of ways to place r distinct objects into n identical boxes such that no box is empty as S(r,n), also known as the Stirling’s Number of Second Kind. Unfortunately, there is no general formula which relates S(r,n) with the number of objects and number of boxes. However, we can compute S(r,n) using some recurrence relations.

Now, here are some results for certain useful cases:

  1. S(0,0)=1
  2. S(r,0)=0
  3. S(r,n)=0 \text{ if }r<n
  4. S(r,1)=1
  5. S(r,n)=1 \text{ if } r=n
  6. S(r,2)=2^{r-1}-1 (Use binomial theorem to obtain this)
  7. S(r,3)=\frac{1}{2}(3^{r-1}+1)-2^{r-1} (Use multinomial theorem and inclusion-exclusion principle to derive this)
  8. S(r,r-1)=\dbinom{r}{2}
  9. \displaystyle{S(r,r-2)=\dbinom{r}{3}+3 \dbinom{r}{4}}

The most important tool to evaluate Stirling’s Number of Second Kind is the following recurrence relationship:

S(r,n)=S(r-1,n-1)+nS(r-1,n)

This is derived from discussing the situations when one of the objects is isolated and when it is mixed with other objects. If it is isolated, the other objects can be distributed in S(r-1,n-1) ways. If it is mixed, after the other objects are being distributed, it can be placed in any other boxes, which amounts to the expression nS(r-1,n). Hence these two situations add up to S(r,n). With this recurrence relationship and some principle values, we can derive other Stirling’s Number of Second Kind.

FYI 1: There’s actually a general formula for Stirling’s Number of Second Kind (damn I hate typing this long name) which can be derived using the multinomial theorem and inclusion-exclusion principle. It is

S(m,n)=\displaystyle{\sum_{r=0}^n (-1)^r \dfrac{(n-r)^m}{r!(n-r)!}}

FYI 2: Stirling’s Number of First Kind S'(m,n) is the coefficient of  x^n in the expansion x(x+1)(x+2)\cdots(x+m-1).

Case 4: n identical boxes, r identical objects

ALERT: Knowledge of generating functions required

The partition number of an integer P(n) refers to the number of ways that a positive integer can be written as the sum of smaller positive integers. For example, p(4)=5 since 4=4=3+1=2+2=1+1+2=1+1+1+1. The problem of finding the number of ways to distribute r identical objects into n identical boxes such that no box is empty can be rephrased as finding the number of partitions of r into n parts. In order to proceed, we require the following theorem by Leonhard Euler:

The number of ways to partition an integer r into n parts is equivalent to the number of ways to partition r into parts such that the part with the largest size is n.

So for example, the number of ways to distribute 4 identical objects into 2 identical boxes is 2, since there are 2 ways to write 4 as partition of integers such the largest term is 2 (2+2, 1+1+2). The ways to partition are (2,2), (3,1).

The theorem can be explained with the use of Ferrer’s diagram. I am lazy so I will just refer you to the explanation on Wikipedia (which surprisingly doesn’t look too daunting).

OK so now the problem sorta “simplifies” into finding the number of ways to partition a number r into parts in which the parts with the largest size is n (regardless of the number of parts). This can be achieved by inspecting the coefficient of the following generating function:

(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(x^n+x^{2n}+\cdots)

The coefficient of x^r is the number of ways to place r identical objects into n identical boxes such that no box is empty.

People usually use computers to evaluate large partition numbers… If this really comes out in SMO, good luck then.

So in summary, here’s are the approaches to find the number of distributions in different cases:

References:

Chee, C.C., Koh, K.M. (2007) Principles and Techniques in Combinatorics (1st ed p.298) World Scientific.

Cheers,

ksj