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" ~ Dick Cheney

Relevant Pages

  • Re: number of permutations and repeating colors
    ... >> combinations of hats are there, if we allow repetitions? ... > first r-1 people chose) ...
    (sci.math)
  • Re: number of permutations and repeating colors
    ... > combinations of hats are there, if we allow repetitions? ... I would like to have a breakdown of the permutations ... See C++ program which generates exponents, permutations, color permutations, arrangements, and combinations at ...
    (sci.math)
  • Permuatations [was: Please Help!!Daughter...]
    ... Nice algorithm. ... I like the way that the state of the overall iteration is implicit in the state ... even more straightforward to make it generate all permutations with repetitions ...
    (comp.lang.java.programmer)
  • LibGenCrack released
    ... combinations without repetitions and permutations and a new password ... All work throught events both in native C/C++ environment (win and ... linux) and in .net 2 environment. ...
    (comp.lang.c)
  • Re: Calculating the number of repetitions in a permutation problem
    ... The number of permutations is 36^4 if repetitions are allowed ... > but only 36P4 if repetitions are not allowed. ... either copy a previous slot, or roll a 36-sided die again, ...
    (sci.math)