proof by induction, the number of ways of grouping unlabelled objects

Question

How can i prove by induction that, while grouping n unlabelled objects into m groups,

$$ f(n,m) = { n+m-1 \choose m-1 }$$

This is the step i could get to, after assuming true for k, for some k+1, I have to prove that

$${ n+k \choose k } = { n+k-1 \choose k-1 }\cdot n+1$$

Since I am adding 1 new group,it will cause n+1 ways of placing n objects in that group ( including empty case ) I am not sure how to procced from here.

Answer 1

Denote by ${\cal F}(n,m)$ the set of all groupings of $n$ identical marbles into $m$ groups, the latter labeled from $1$ to $m$. As is well known, each element of ${\cal F}(n,m)$ can be encoded as a binary string of length $n+m-1$ containing $n$ zeros representing the marbles and $m-1$ ones acting as separators between the groups. This leads to the formula $$\bigl|{\cal F}(n,m)\bigr|={n+m-1\choose m-1}\tag{1}$$ alluded to in the question.

Now you want an induction proof of this formula. Looking at the recursion valid for the right hand side when $m\rightsquigarrow m+1$ this means that we have to prove somehow that $$\bigl|{\cal F}(n,m+1)\bigr|={n+m\over m}\>\bigl|{\cal F}(n,m)\bigr|\tag{2}$$ (you got this wrong in your question).

This can be seen as follows: Any sequence in ${\cal F}(n,m)$ has length $n+m-1$ and therefore a total of $n+m$ spaces (including the ends) where an $m^{\rm th}$, "golden", separator can be inserted. This means that any sequence in ${\cal F}(n,m)$ can be enlarged in $m+n$ ways to an element of ${\cal F}(n,m+1)$. In this way every sequence in ${\cal F}(n,m+1)$ is produced exactly $m$ times, insofar as any of its $m$ separators could be the "golden" one. Therefore $(2)$ counts ${\cal F}(n,m+1)$ correctly, and it is then easy to derive $(1)$ from $(2)$.

Answer 2

The problem is equivalent to finding the number of solutions of equation $a_1 + a_2 + a_3 + ... + a_m = n$ where $a_i >= 0$ for all i.

Assumes $f(n,k) = { n+k-1 \choose k-1 }$ and $f(n-1,k+1) = { n+k-1 \choose k }$ by induction hypothesis. Let's consider $f(n,k+1)$. Each grouping will be corresponding to a solution of the equation: $b_1 + b_2 + b_3 + ... + b_{k+1} = n$ where $b_i >= 1$ for all i

Case 1. if $b_1$ is 0, then $b_2, b_3, ... b_{k+1}$ is a solution of equation $c_1 + c_2 + ... + c_k = n$. The number of solution is $f(n,k) = { n+k-1 \choose k-1 }$.

Case 2. if $b_1$ is at least 1, then $(b_1-1), b_2, b_3, ..., b_{k+1}$ is a solution of equation $c_1 + c_2 + ... + c_{k+1} = n - 1$. The number of solution is $f(n-1,k+1) = { n+k-1 \choose k }$

The sum is ${ n+k-1 \choose k } + { n+k-1 \choose k-1 } = { n+k \choose k }$ (pascal triangle identity) which shows $f(n,k+1)$ also has the same formula.

In addition, in order for the induction to work, the base case needs to be all $f(n,1)$ for all n and $f(0,n)$ for all n. (I believe they are trivial enough). For example, $f(1,2)$ can be inducted from $f(1,1)$ and $f(0,2)$ which are base cases. $f(1,3)$ can be inducted from $f(1,2)$ and $f(0,3)$. $f(2,2)$ can be inducted from $f(1,2)$ and $f(2,1)$ .etc.