0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

The following are equivalent expressions for the multinomial coefficient:$${{}^{(a+b+c)}\mathrm C_{a,b,c}\\= \binom{a+b+c}{a,b,c}\\= \dfrac{(a+b+c)!}{a!~b!~c!}\\ = \binom{a+b+c}{a}\binom{b+c}b\\ \vdots \text{ and such like}}$$

The multinomial coefficient counts the ways to permute (or arrange) a multiset of $a, b,$ and $c$ items of three types (the items are otherwise considered indistinguishable).

This also counts the ways to select a combination of places for the items of each type.

These are simply different ways of looking at the same task; the count of possible ways to perform them will therefore be the same.


The combination with repetition you mention counts ways to select a number of items from a set with replacement/repetition, when the order of selection is not recorded. (Each item may be selected multiple times.)

Choosing $k$ objects with repletion from a menu of $n$ can be counted as ways to arrange a string of $k$ 'stars' and $n-1$ 'bars', where the number of stars before the first bars counts the number of times the first object is selected, and so on, as though putting balls into boxes with the bars representing the dividers between boxes. (This counting technique is thus known as "stars and bars")

Hence $\tfrac{(k+n-1)!}{k!~(n-1)!}$ is the count for ways to select with repetition, a combination of $k$ objects from a menu of $n$ .

$\endgroup$
0
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.