Re: number of permutations and repeating colors

From: Lance Lamboy (lance.lamboy_at_lamboy.nospam.com)
Date: 08/04/04 

Date: Wed, 04 Aug 2004 13:59:29 -0400

On Wed, 04 Aug 2004 10:40:36 -0700, Didier Deshommes wrote:

> Hi,
> Suppose you have 4 people and 4 hat colors (R,G,B,W). How many possible
> combinations of hats are there, if we allow repetitions? The answer is
> simple enough: 4^4=256.
>
> But I'm interested in finding how many permutations contain:
> --The repetition of 4 hat colors (answer:4)
> --of 3 hat colors
> --of 2 hat colors
> --no repetitions at all(answer:4!).

If you have n people, k colors, and r repetitions, then

* the first person has k choices (any one of the k colors)
* the second person has k-1 choices (any one of the k-1 colors that the
first person didn't choose)
...
* the rth person has k-r+1 choices (any one of the k-r+1 colors that the
first r-1 people chose)
* the remaining people have r choices (any of the fir r colors that the
first r people chose)

>
> In other words, I would like to have a breakdown of the permutations
> depending on the number of times any color is repeated. Is there an
> easy way to find the answer to such problem?
>
> BTW, The case for n=3 is almost trivial (and easily verifiable by brute
> force):
> --3 reps: 3 cases
> --2 reps: 18
> --no reps: 3! = 6
> Total is 27
>
> Thanks! 

-- 
Lance Lamboy
"Go F*ck Yourself" ~ *** Cheney
Quantcast