# Permutation & Combination of multiple duplicates

• scoutfai
In summary: You son-of-a-guns, can't you see it is the coefficient of x^10 in the expansion of (x + x^2 + x^3 + x^4 + x^5 + x^6)^3?" He then wrote the expansion on the board. We were then all able to extract the coefficient of x^10, getting the answer 27/216. I was so impressed that I wrote a letter to the professor telling him that this was the most exciting thing that had happened to me in college. He wrote back saying that he was glad to see that I was interested in mathematics and that I should read a book called "Applied Combinatorics"
scoutfai
Let me phrase the problem in a general way.

Given $$n$$ objects in a set. All the objects can be categorized into $$k$$ groups such that no two objects from different groups are identical. Objects in the same group are indistinguishable from each other within the group. Number of objects in each group is as shown in the following:

1st group has $$m_{1}$$ objects;
2nd group has $$m_{2}$$ objects;
3rd group has $$m_{3}$$ objects;
... ...
$$k^{th}$$ group has $$m_{k}$$ objects.

What is the number of possible combination if one was to pick $$r$$ objects from the set?
What is the number of possible permutation if one was to pick $$r$$ objects from the set?

Example:
AAA BBBB CC DDD EE FF G H I JJ
There are 21 ($$n=21$$) alphabets above. These alphabets can be categorized into 10 ($$k=10$$) groups. The number of alphabets in each group is as shown:
1st group (A), $$m_{1}=3$$
2nd group (B), $$m_{2}=4$$
3rd group (C), $$m_{3}=2$$
4th group (D), $$m_{4}=3$$
5th group (E), $$m_{5}=2$$
6th group (F), $$m_{6}=2$$
7th group (G), $$m_{7}=1$$
8th group (H), $$m_{8}=1$$
9th group (I), $$m_{9}=1$$
10th group (J), $$m_{10}=2$$

What is the number of possible combination if one was to pick 5 ($$r=5$$) objects from this set of alphabets?
What is the number of possible permutation if one was to pick 5 ($$r=5$$) objects from this set of alphabets?

For this kind of question, if every parameters were given its value to me, then I can solve for the answer (a series of lengthy calculation, one has to consider all possibilities one by one). But when the parameters remain as unknown, I am unable to derive a general solution (a formula).

I suspect that this is a kind of problem that can be represented analytically, but one can not solve it analytically. Just like the equation $$e^{x}sin x=0$$ , the problem can be represented analytically, but one can not express x analytically and can only be solved numerically.

Any thought?

Problems like these are solved with generating functions, which you can find discussed in books on combinatorial analysis or some web sites. To take your alphabet example, suppose we want to find the number of combinations of r objects taken from the given set of alphabets; say the answer is $$a_r$$. Define the ordinary power series generating function f(x) by

$$f(x) = \sum_r a_r x^r$$.

Then it's easy to see (once you know how) that

$$f(x) = (1+x)^3 (1+x+x^2)^4 (1+x+x^2+x^3)^2 (1+x+x^2+x^3+x^4)$$

You can expand this function using a computer algebra system and find that the coefficient of $$x^5$$ is 1143. Pencil and paper solution is also possible but likely to be tedious in this case.

The corresponding problem with permutations instead of combinations is solved with exponential generating functions.

Some resources:

"An Introduction to Combinatorial Analysis", Riordan

"Generatingfunctionology", Wilf (available on-line)

Generating functions are one of the Big Ideas of mathematics. I hope you get to explore them.

awkward said:
Problems like these are solved with generating functions, which you can find discussed in books on combinatorial analysis or some web sites. To take your alphabet example, suppose we want to find the number of combinations of r objects taken from the given set of alphabets; say the answer is $$a_r$$. Define the ordinary power series generating function f(x) by

$$f(x) = \sum_r a_r x^r$$.

Then it's easy to see (once you know how) that

$$f(x) = (1+x)^3 (1+x+x^2)^4 (1+x+x^2+x^3)^2 (1+x+x^2+x^3+x^4)$$

You can expand this function using a computer algebra system and find that the coefficient of $$x^5$$ is 1143. Pencil and paper solution is also possible but likely to be tedious in this case.

The corresponding problem with permutations instead of combinations is solved with exponential generating functions.

Some resources:

"An Introduction to Combinatorial Analysis", Riordan

"Generatingfunctionology", Wilf (available on-line)

Generating functions are one of the Big Ideas of mathematics. I hope you get to explore them.

I have never came across such branch of mathematics before, not even heard of it.
How is the generating function able to solve the problem? what is the use of f(x)? Is the 1143 an answer to the problem?

scoutfai said:
I have never came across such branch of mathematics before, not even heard of it.
How is the generating function able to solve the problem? what is the use of f(x)? Is the 1143 an answer to the problem?
1143 is the answer to your problem of selecting combinations of 5 letters from the specified alphabets.

As to how it works, let's try a simpler example. Suppose you have 2 apples and 3 oranges (otherwise indistinguishable) and you want to count the number of possible ways to select 3 pieces of fruit. You could just list the possibilities:

0 apples + 3 oranges
1 apple + 2 oranges
2 apples + 3 oranges

So there are 3 ways in all. Or consider the mechanics of expanding

(1 + x + x^2) (1 + x + x^2 + x^3).

In order to get a term of x^3 in the product, we need to match an x^i taken from 1 + x + x^2 with an x^j taken from 1 + x + x^2 + x^3 where i+j = 3. If you think about it, that's just like generating the apple-orange combinations above. But the beauty of the generating function is that it gives, in a concise form, the solution to the more general problem of selecting r pieces of fruit: the answer is just the coefficient of x^r in the generating function.

The most basic book I know of that introduces generating functions is "Mathematics of Choice" by Niven. You can't get very far at the high-school level, though, because many applications of generating functions involve infinite series.

To whet your interest, here is what the statistician Frederick Mosteller had to say about his first exposure to generating functions:

A key moment in my life occurred in one of those classes during my sophomore year. We had the question: When three dice are rolled what is the chance that the sum of the faces will be 10? The students in this course were very good, but we all got the answer largely by counting on our fingers. When we came to class, I said to the teacher, "That's all very well - we got the answer - but if we had been asked about six dice and the probability of getting 18, we would still be home counting. How do you do problems like that?" He said, "I don't know, but I know a man who probably does and I'll ask him." One day I was in the library and Professor Edwin G Olds of the Mathematics Department came in. He shouted at me, "I hear you're interested in the three dice problem." He had a huge voice, and you know how libraries are. I was embarrassed. "Well, come and see me," he said, and I'll show you about it." "Sure, " I said. But I was saying to myself, "I'll never go." Then he said, "What are you doing?" I showed him. "That's nothing important," he said. "Let's go now."

So we went to his office, and he showed me a generating function. It was the most marvelous thing I had ever seen in mathematics. It used mathematics that, up to that time, in my heart of hearts, I had thought was something that mathematicians just did to create homework problems for innocent students in high school and college. I don't know where I had got ideas like that about various parts of mathematics. Anyway, I was stunned when I saw how Olds used this mathematics that I hadn't believed in. He used it in such an unusually outrageous way. It was a total retranslation of the meaning of the numbers. [Albers, More Mathematical People].

and here is a link to an article from Poker Digest with a nicely explained example:

http://people.math.sfu.ca/~alspach/mag82/

[/edit]

Last edited:
awkward said:
1143 is the answer to your problem of selecting combinations of 5 letters from the specified alphabets.

As to how it works, let's try a simpler example. Suppose you have 2 apples and 3 oranges (otherwise indistinguishable) and you want to count the number of possible ways to select
...
[/edit]
I think I got to need some time to do some reading first.
But before that, could you answer me on the question whether the general problem I asked, has an answer that can be represented analytically?
I believe in what you said about the generating function is capable of solving such kind of problem. However, so far in your demonstration they were only numerical example, not a general one (all parameters replaced by unknowns). That's why I still have such doubt.

The generating function for the general problem you posed is

$$\prod_{i=1}^k (1 + x + x^2 + \dots + x^{m_i})$$

but I would not expect it to yield a simple formula for the number of possible combinations.

awkward said:
The generating function for the general problem you posed is

$$\prod_{i=1}^k (1 + x + x^2 + \dots + x^{m_i})$$

but I would not expect it to yield a simple formula for the number of possible combinations.
Hence it is to say that the number of possible combination to select r objects out of this set of objects is the coefficient of the term $$x^{r}$$?

scoutfai said:
Hence it is to say that the number of possible combination to select r objects out of this set of objects is the coefficient of the term $$x^{r}$$?
Yes,that is correct.

awkward said:
Yes,that is correct.

what about the permutation? what kind of generating function is used?

awkward said:
Problems like these are solved with generating functions, which you can find discussed in books on combinatorial analysis or some web sites. To take your alphabet example, suppose we want to find the number of combinations of r objects taken from the given set of alphabets; say the answer is $$a_r$$. Define the ordinary power series generating function f(x) by

$$f(x) = \sum_r a_r x^r$$.

Then it's easy to see (once you know how) that

$$f(x) = (1+x)^3 (1+x+x^2)^4 (1+x+x^2+x^3)^2 (1+x+x^2+x^3+x^4)$$

You can expand this function using a computer algebra system and find that the coefficient of $$x^5$$ is 1143. Pencil and paper solution is also possible but likely to be tedious in this case.
After I read the link you provided, I try to explain what is happening in this f(x) generating function. If I have mistake, please correct me.

The exponent of x represents the number of object chosen.
One pair of bracket represent one category.
Coefficient of x^0, x^1 , x^2, x^3, ... ... in each bracket represents the number of way to choose 0, 1, 2, 3, ... ... objects from that category.

So for each category, the associated content in the bracket of the generating function is as shown below:

for A: 1+x+x^2+x^3
for B: 1+x+x^2+x^3+x^4
for C: 1+x+x^2
for D: 1+x+x^2+x^3
for E: 1+x+x^2
for F: 1+x+x^2
for G: 1+x
for H: 1+x
for I: 1+x
for J: 1+x+x^2

Multiplying each expression, forms the generating function:

$$f(x) = (1+x)^3 * (1+x+x^2)^4 * (1+x+x^2+x^3)^2 * (1+x+x^2+x^3+x^4)$$

Yes, that's right.

In a previous post you asked about the corresponding problem for permutations instead of combinations. In this case you would use exponential generating functions. (I think I mentioned this once before.) But it's probably best to get familiar with ordinary power series generating functions before moving on to the exponential variety.

awkward said:
Yes, that's right.

In a previous post you asked about the corresponding problem for permutations instead of combinations. In this case you would use exponential generating functions. (I think I mentioned this once before.) But it's probably best to get familiar with ordinary power series generating functions before moving on to the exponential variety.
Thanks for the lesson.
Yes you are right, you indeed mentioned it once before. What I am trying to ask is the mathematics expression of the corresponding exponential generating function for the example I gave.

The exponential generating function is

$$\prod_{i=1}^k (1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots + \frac{x^{m_i}}{m_i!})$$

The number of permutations of r objects is the coefficient of
$$\frac{x^r}{r!}$$
when this expression is expanded.
Notice the division by r!. If your computer algebra system doesn't give you the answer in that form, you have to adjust its output appropriately.

awkward said:
The exponential generating function is

$$\prod_{i=1}^k (1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots + \frac{x^{m_i}}{m_i!})$$

The number of permutations of r objects is the coefficient of
$$\frac{x^r}{r!}$$
when this expression is expanded.
Notice the division by r!. If your computer algebra system doesn't give you the answer in that form, you have to adjust its output appropriately.
Thanks!
I thought the exponential generating function is something involve the exponent expression (something like $$e^{x}$$).
Can you explain why the division by a factorial? Because usually from combination to permutation, one multiplies by a factorial. Thus it doesn't seem intuitive to me. Any meaning hidden in the factorial in that generating function?

Maybe it will seem more intuitive to you if you notice that if you have a term like

$$5 x^3$$,

in order to convert it to exponential generating function form you have to write it as

$$\frac{3! \cdot 5}{3!} x^3$$

i.e., you have to multiply by 3!.

awkward said:
Maybe it will seem more intuitive to you if you notice that if you have a term like

$$5 x^3$$,

in order to convert it to exponential generating function form you have to write it as

$$\frac{3! \cdot 5}{3!} x^3$$

i.e., you have to multiply by 3!.
But the generating function for permutation case given by you is same as the combination case with only one difference, which is every term was divided by a corresponding factorial.

This would mean the coefficient for a term of the permutation case will always smaller than the combination. Although I never came across such a theorem, but experience says that permutation always bigger than combination, isn't?

Or, is it you mistakenly write it as division instead of multiplication by a factorial?

scoutfai said:
But the generating function for permutation case given by you is same as the combination case with only one difference, which is every term was divided by a corresponding factorial.

This would mean the coefficient for a term of the permutation case will always smaller than the combination. Although I never came across such a theorem, but experience says that permutation always bigger than combination, isn't?

Or, is it you mistakenly write it as division instead of multiplication by a factorial?
No.

For example, the ordinary power series generating function for the number of combinations of 3 distinct objects taken r at a time is

$$(1+x)^3 = 1 + 3x + 3x^2 + x^3$$

The exponential generating function for the number of permutations of 3 distinct objects taken r at a time is

$$(1+ \frac{1}{1!} x)^3 = 1 + \frac{1}{1!} 3x + \frac{1}{2!} 6x^2 + \frac{1}{3!} 6x^3$$

I may not have internet access for a few days. If you have more questions, maybe someone else can answer them or you can consult some of the links given previously.

## 1. What is the difference between permutation and combination?

Permutation is the arrangement of a set of objects in a specific order, while combination is the selection of a subset of objects from a larger set without considering the order.

## 2. How do you calculate the number of permutations of multiple duplicates?

The formula for calculating the number of permutations of multiple duplicates is n!/(n1! * n2! * ... * nk!), where n is the total number of objects and n1, n2, etc. are the number of duplicates for each object.

## 3. What is the difference between permutations with and without repetition?

Permutations with repetition allow for objects to be repeated in the arrangement, while permutations without repetition do not allow for any repetition.

## 4. Can you give an example of permutation with multiple duplicates?

Let's say we have the word "MISSISSIPPI". The number of permutations of this word would be 11!/(4! * 4! * 2!) = 34650, as there are 11 letters (n), 4 duplicates of "I" (n1), 4 duplicates of "S" (n2), and 2 duplicates of "P" (nk).

## 5. How do you use permutations and combinations in real life?

Permutations and combinations are used in various fields such as mathematics, statistics, computer science, and economics. They are also commonly used in everyday situations, such as arranging a seating plan for a wedding or choosing a combination for a lock.

• General Math
Replies
1
Views
716
• General Math
Replies
3
Views
806
• General Math
Replies
2
Views
670
• General Math
Replies
2
Views
1K
• General Math
Replies
2
Views
2K
• General Math
Replies
2
Views
1K
• Introductory Physics Homework Help
Replies
2
Views
227
• General Math
Replies
3
Views
1K
• Introductory Physics Homework Help
Replies
13
Views
1K
• Electromagnetism
Replies
16
Views
1K