Difficult Stats Problem (Repeated Elements)

[Big-Daddy]

Homework Statement

A word has n letters, in which one of those letters is present a times and another is present b times (all other letters are present only once).

a.) How many combinations of x letters are there from this word?
b.) How many arrangements of x letters are there from this word?

Homework Equations

nCr=n!/((n-r)!r!)
nPr=n!(n-r)!
Any others?

The Attempt at a Solution

I'm not completely clear but I think the problem means, e.g. “POSSESSES”, 5 letters being chosen: n=9, r=5, a=5 (5 Ss), b=2 (2 Es).

I was told the solution would require a sigma function (summation operator) so it won't be easy. So far, for combinations, I came up with something like Ʃ(i=0 to i=n-a-b; C(n-a-b,i)) but now I'm thinking that's only a small piece of the puzzle. Help?

 

[haruspex]

Suppose for some r, s you choose r of the a and s of the b. How many combinations of x letters then?

 

[Big-Daddy]

Suppose for some r, s you choose r of the a and s of the b. How many combinations of x letters then?

So I'm choosing r of the letter repeated a times, and s of the letter repeated b times. These are fixed, right? Then there will be $$x-r-s$$ spaces remaining to be filled and $$n-a-b$$ letters to fill them. By definition r≤a, s≤b, x≤n, so $$x-r-s≤n-a-b$$ and we can write generally that C(n-a-b,x-r-s) will be how many combinations of x letters there are. (Note that C(n,r) is the format I'm using here.) This should hold even if r=0 and/or s=0, and because r and s≤x it should still hold even if x=r or x=s.

Which we can quickly sum over every value of r and s so that Ʃ(r=0 to r=a; Ʃ(s=0 to s=b; C(n-a-b,x-r-s))) is our total number of combinations, the answer to part a). My teacher confirmed this is correct.

What do we do for the permutations? Still $$x-r-s$$ spaces remaining to be filled and $$n-a-b$$ letters to fill them. Now what?

 

[haruspex]

Having chosen your x letters, there are x! permutations, but because r of them are the same, groups of these permutations look the same. How many in each such group? (Similarly for the s that are the same.)

 

[Big-Daddy]

Having chosen your x letters, there are x! permutations, but because r of them are the same, groups of these permutations look the same. How many in each such group? (Similarly for the s that are the same.)

Is it $$x!/(r!s!)$$? I'm not sure what else you might mean by "groups of permutations" ...

 

[haruspex]

Is it $$x!/(r!s!)$$?

yup.

 

[Big-Daddy]

yup.

Thanks, I've reached this solution now.Ʃ(s=0 to 2)Ʃ(r=0 to 5) of (C(n-a-b,x-r-s)*(x!(r!s!))).

I'd like to try a couple of extension problems now. Let's say we go for permutations with repetition allowed, i.e. {a,a,a} is a valid arrangement of 3 from a set of {a,b,c,d,e}. Then where we previously had nPr we have [tex]n^r[/tex], so is our sum now Ʃ(s=0 to 2)Ʃ(r=0 to 5) of (C(n-a-b,x-r-s)*(x^x(r!s!))). Or how else can I reach it? I've got a set of x elements, of which r are repeats, and s are also repeats; how do I find the number of permutations, allowing repetitions?

Edit: Possibly we should be looking at C(n-a-b,x-r-s)*(x-r-s+2)^x instead? (+2 to allow for the number of distinct elements there are, x because that's how many spaces we have to find perms for.) Not sure ...

 

[Big-Daddy]

No help? Is this one too complicated?