Placing Identical objects to Identical places.

Question

In How many ways can a 25 Identical books can be placed in 5 identical boxes.

I know the process by counting but that is too lengthy . I want different approach by which I can easily calculate required number in Exam hall in few minutes.

Process of Counting : This problem can be taken partitions of 25 into 5 parts.

25 = 25+0+0+0+0

25 = 24 +1 + 0 + 0 +0

25 = 23+ 1 +1 +0 + 0 ... .... Like this way many combinations are made.: about 377

How can we calculate it without this process of manual counting.

Answer 1

The answer of Foobaz John defined $p_k$ and $p_{\le k}$.

Notice first of all that $p_{\le k}(n)=p_k(n+k)$. (That's because we can add one object to each part to ensure that there are no parts of size zero.) Thus, while we must be careful to distinguish them, the tables for these two functions are very similar.

Let's write down the table for $p_k(n)$ up to $k=5$.

The column for $k=1$ is identically $1$, so we can omit it. The column for $k=2$ can be filled in with $\lfloor\tfrac12n\rfloor$; after that, we use the recurrence $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ to get: $$\begin{array}{|c|cccc|}\hline&2&3&4&5\\\hline2&1\\3&1&1\\4&2&1&1\\5&2&2&1&1\\6&3&3&2&1\\\vdots&\vdots&\vdots&\vdots&\vdots\end{array}$$ With practice, the table can be continued fairly rapidly, but it will take a few minutes to get to row $25$, and any error will propagate. An exam ought not to contain such a problem, unless the numbers are very small. However, formulas do exist. I won't attempt to prove them.

$$\begin{align*}p_2(n)&=\lfloor\tfrac12n\rfloor\\ p_3(n)&=[\tfrac1{12}n^2]\\ p_4(n)&=[\tfrac1{144}(n^3+3n^2\underbrace{-9n}_{\text{if }n\text{ odd}})]\end{align*}$$ In the second and third formulas, $[\ldots]$ signifies the nearest integer.

The equivalent formula for $k=5$ is $$p_5(n)=[\tfrac1{2880}(n^4+10n^3+10n^2-75n-45n(-1)^n)]$$

However, rather than memorize this, we could use the recurrence together with an earlier formula.

$$\begin{align*}p_{\le 5}(25)=p_5(30)&=p_4(29)+p_4(24)+p_4(19)+p_4(14)+p_4(9)+p_4(4)\\&=185+108+54+23+6+1\\&=377\end{align*}$$

Answer 2

You could use a recurrence.

For example: put $a=0,1,2,...,n$ books into the first box and calculate, in how many ways you can put $n-a$ books in $m-1$ boxes. To prevent repetitions, assume, that in the next box you will put no less books, than to the previous one.

Of course:

• if $n<a(m-1)$, then there are no options
• if $n\geq a$ and $m-1=1$, then there is one option

This function would look like this:

$$F_m(n,a)=\begin{cases}1, & m=1 \wedge n\geq a\\ 0, & n<am\\ \sum_{k=0}^n F_{m-1}(n-k, k),&\text{in other cases}\end{cases} $$

What you need to calculate is $F_5(25,0)$

Answer 3

In general, you can use the following recursive formula. Let $P_k(n)$ be the set of partitions of $n$ with exactly $k$ parts. Let $p_{k}(n)$ be the number of partitions of $n$ into $k$ parts i.e. $p_{k}(n)=|P_k(n)|$. Then $$ p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k) $$ by classifying $\lambda=(\lambda_1,\dots,\lambda_k)\in P_k(n)$ (where the $\lambda_i$ are weakly decreasing and positive) based on whether $\lambda_k=1$ or $\lambda_k>1$. Let $p_{\leq k}(n)=\sum_{m=0}^kp_{m}(n)$ be the number of partitions of $n$ into at most $k$ parts.

In your case you want to compute $$ p_{\leq 5}(25)=\sum_{m=0}^5p_{m}(25). $$ But note that there are some special values of $k$ which make it easy to compute. Indeed $p_{0}(25)=0$, $p_{1}(25)=1$, $p_2(25)=\lfloor 25/2\rfloor=12$.

Alternatively, we can note that partitions of $n$ into at most $k$ parts correspond bijectively to partitions of $n$ where the largest part is at most $k$. Thus $$ \begin{align} \sum_{n\geq 0}p_{\leq k}(n)x^n&=(1+q+q^2+\dotsb)(1+q^2+q^4+\dotsb)\dotsb(1+q^k+q^{2k}+\dotsb)\\ &=\frac{1}{(1-q)(1-q^2)\dotsb(1-q^k)} \end{align} $$ In particular we find that in your case $$ p_{\leq 5}(25)=[q^{25}]\left(\frac{1}{(1-q)(1-q^2)\dotsb(1-q^5)} \right)=377 $$ using a computer algebra system for example.

Answer 4

Number of partitions of m into b positive parts (blocks) is described here: https://oeis.org/A008284 in the OEIS article.

$P(m,b) = P(m-1, b-1) + P(m-k,b)$

The recurrence formula means that given a $P(m,b)$ partition of m into b blocks, two situations may occur:

1) a singleton is in the partition; we remove it and obtain $ P(m-1, b-1)$ cases

2) there are no singletons in the partition; we remove one piece from each block and we get the $P(m-k, b)$ cases.

for example, for P(7,3)

5+1+1 <----> 5+1

4+2+1 <----> 4+2

3+3+1 <----> 3+3

3+2+2 <----> 2+1+1

After completing the table given by Andrew Wood to the 25th row we get:

P(25,1) + P(25,2) + P(25,3)+ P(25,4)+ P(25,5) = $1+12+52+120+192 = 377$