# Difficult Stats Problem (Repeated Elements)

1. May 4, 2013

1. The problem statement, all variables and given/known data

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?

2. Relevant equations

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

3. 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?

2. May 4, 2013

### haruspex

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

3. May 11, 2013

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?

Last edited: May 11, 2013
4. May 11, 2013

### 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.)

5. May 11, 2013

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

Last edited: May 11, 2013
6. May 11, 2013

### haruspex

yup.

7. May 12, 2013

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 $$nr$$, so is our sum now Ʃ(s=0 to 2)Ʃ(r=0 to 5) of (C(n-a-b,x-r-s)*(xx(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 ...

Last edited: May 12, 2013
8. May 13, 2013