[Math] Combinatorics : relationship between Combinations and Permutations with similar objects

combinationscombinatorial-proofscombinatorics

I have a question in regards to relationship between Combinations and Permutations with like or repeated objects.

Using an example like the the word Mississipi, basic example of using Permutations with like letters.
I have seen this type done with multiplications of Combinations, which works out to be the Permutation formula with like elements which is = n!/a!b!c!, etc.

BUT there is also another formula for Combinations with Repititions, which is
of the form : C(n+r-1, r).
Is there a relationship between all of these, this one an equivalent form of the above.
Also this "Combinations with Repetition" seems to even be similar to Binomial coefficients of Pascal Triangle.

SO just wondering if these are kind of one and the same structure, just 3 or 4 different forms of the same thing?

Hope someone can help.
P

Best Answer

You are right, there is definitely a connection between these two counting problems. In fact, the second problem (also known as "balls and urns" or "stars and bar") is really just a variant of the first.

In the first problem, we first treat same letters and distinguishable from one another (e.g. "mississippi" becomes "M$\text{i}_1\text{s}_1\text{s}_2\text{i}_2\text{s}_3\text{s}_4\text{i}_3\text{p}_1\text{p}_2\text{i}_4$"). There are a total of $11$ letters so there are $11!$ total ways to arrange them. However we have clearly overcounted, as the i's, the s's, and the p's are not different from each other. In fact, for a letter that was repeated $x$ times, we have counted every valid arrangement of "mississippi" $x!$ times (do you see why?). Therefore, we must divide out these overcounted arrangements from $11!$, so our final answer is $\frac{11!}{4!4!2!}$.

Suppose we want to put $m$ indistinguishable balls into $n$ distinguishable urns. How many ways are there to do this?

We can line up the $m$ balls in a row from left to right, like this:

$B\text{ } B\text{ } \cdots \text{ }B$

Now imagine that we place $n-1$ partitions (let us denote them with the letter P) in the spaces between the B's to separate them into urns as follows:

  1. Every ball to the left of the leftmost partition goes into urn 1.
  2. Every ball between the $i-1$th and $i$th partition goes into urn $i$.
  3. Every ball to the right of the rightmost partition goes into urn $n$.

Note that it is perfectly fine to have multiple partitions next to each other; this just means that the corresponding urn has $0$ balls.

Because every arrangement is valid, we are in essence rearranging letters of the "word" with $m$ B's and $n-1$ P's. This is exactly the same as the first problem, and our final answer is $\frac{(m+n-1)!}{m!(n-1)!}=\binom{m+n-1}{m}$.

Hope this helped :)

Related Question