Permutation & Combination of multiple duplicates

[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?

 

[awkward]

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.

 

[scoutfai]

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.

Thanks for the reply.
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?

 

[awkward]

Thanks for the reply.
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].

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

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

[/edit]

 

[scoutfai]

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.

 

[awkward]

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.

 

[scoutfai]

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}$$?

 

[awkward]

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.

 

[scoutfai]

Yes,that is correct.

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

 

[scoutfai]

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

 

[awkward]

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.

 

[scoutfai]

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.

 

[awkward]

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.

 

[scoutfai]

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?

 

[awkward]

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!.

 

[scoutfai]

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?

 

[awkward]

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.