Re: Calculating the number of repetitions in a permutation problem

From: Quentin Grady (quentin_at_paradise.net.nz)
Date: 06/29/04 

Date: Wed, 30 Jun 2004 08:47:38 +1200

This post not CC'd by email
 On Tue, 29 Jun 2004 16:00:17 GMT, The Ghost In The Machine
<ewill@aurigae.athghost7038suus.net> wrote:

>In sci.math, Quentin Grady
><quentin@paradise.net.nz>
> wrote
>on Tue, 29 Jun 2004 19:23:26 +1200
><tm52e0hf34883kegom9r0nlcdeu63e121c@4ax.com>:
>> G'day G'day Folks,
>>
>> A computer login requires a four character code either letters or
>> digits. The number of permutations is 36^4 if repetitions are allowed
>> but only 36P4 if repetitions are not allowed. The number of
>> permutations that include repetitions is therefore 36^4 - 35P4.
>>
>> Is there another way to work out the number of permutations that
>> include repetitions that could be used as a check calculation?
>>
>> Best wishes,
>>
>
>Well, one can compute the following:
>
>1234 = 35P4 = 36*35*34*33 = 1413720
>1123 = 36*35*34 = 42840
>1213 = 36*35*34 = 42840
>1231 = 36*35*34 = 42840
>1223 = 36*35*34 = 42840
>1232 = 36*35*34 = 42840
>1233 = 36*35*34 = 42840
>1122 = 36*35 = 1260
>1212 = 36*35 = 1260
>1221 = 36*35 = 1260
>1112 = 36*35 = 1260
>1121 = 36*35 = 1260
>1211 = 36*35 = 1260
>1222 = 36*35 = 1260
>1111 = 36
>
>TOTAL = 1679616 = 36^4
>
>where a digit indicates a slot. 1 = 36, 2 = 35, etc.
>(The second 1 doesn't add to the count.)
>
>The scheme is admittedly not that easy to describe;
>basically, 1 number is always picked first (a roll of a
>36-sided die, basically), but the next slot or slots can
>either copy a previous slot, or roll a 36-sided die again,
>except that previous slots have already been picked and
>can't be picked again, so the second roll is only 35-sided,
>the third 34, etc.

G'day G'day and thank you,

   I had hoped there was an algebra that would tie it all together.
However it would seem that often probabilities come down to counting
the ways. Thank you once again for showing me how it is achieved.
  

-- 
Quentin Grady       ^  ^  /
New Zealand,       >#,#< [
                    / \ /\    
"... and the blind dog was leading." 
http://homepages.paradise.net.nz/quentin

Relevant Pages

  • 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)
  • 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: number of permutations and repeating colors
    ... > combinations of hats are there, ... If you have n people, k colors, and r repetitions, then ... first r-1 people chose) ... I would like to have a breakdown of the permutations ...
    (sci.math)