Statistical Combinations/Permutations

[Big-Daddy]

Problem statement:

Of the letters in the word "POSSESSES", if you must choose 5 letters:

a) How many possible combinations are there (of 5)?
b) How many possible arrangements are there (of 5)?

Given a word of n letters, where one of the letters is present 'a' times in the word and the other is present 'b' times in the word, how many possible combinations of r letters are there, and how many possible arrangements of r letters are there?

My comments:

Actually I don't have a clue where to start with this. Don't worry about finding that general formula; that part of the question is an extension written by me for myself, which I will attempt once I've seen the method.

Frankly I was surprised it was this difficult to consider repeated elements in nPr and nCr, but it would really help me if you would outline in detail the method to take to solve such a problem, so I could then try to apply it to a general case.

Thanks in advance for any help.

 

[haruspex]

With many problems like this, you just have to find some convenient way to break it into cases. I would start by considering the various possibilities for the number of Ss.

 

[awkward]

The general method for solving problems of this type is the application of generating functions: ordinary power series generating problems for a) and exponential generating functions for b). Maybe that's too advanced for your course, in which case haruspex's advice applies. Many combinatorics textbooks discuss generating functions. The nice thing about generating functions is they immediately give you the answer for words of all lengths (not just 5).

One online resource is Bogart's Combinatorics Notes:
http://www.math.dartmouth.edu/archive/kpbogart/public_html/ComboNotes3-20-05.pdf

Generating functions are one of the Great Ideas in mathematics. In hope of wheting your interest in them, here is what the statistician Frederick Mosteller said about his first encounter with GFs:

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

 

[haruspex]

The general method for solving problems of this type is the application of generating functions:

Generating functions are wonderfully powerful constructs, but they don't always help. In the present problem, it produces (1+x)²(1+x+x²)(1+x+x²+x³+x⁴+x⁵). Answering the question posed then consists of multiplying that out and finding the coefficient of x⁵. That again just reduces to breaking it up into cases.
Or you could rewrite it as (1+x)²(1+x+x²)(1-x⁶)/(1-x), differentiate 5 times, set x = 0 and divide the result by 5!.

 

[awkward]

If I were working on extracting the coefficient of $x^5$ "by hand", I would try the identity
$$(1+x)^2 (1+x+x^2) (1+x+x^2+x^3+x^4+x^5) = (1+2x+x^2)(1-x^3)(1-x^6)(1-x)^{-2}$$ and then expand $(1-x)^{-2}$ by the Binomial Theorem.

But don't overlook the possibility of automation. Even if you don't have a readily available computer algebra system, typing

"expand (1+x)^2 (1+x+x^2) (1+x+x^2+x^3+x^4+x^5)"

into Wolfram Alpha will get the answer quickly.