Re: Calculating the number of repetitions in a permutation problem

From: The Ghost In The Machine (ewill_at_aurigae.athghost7038suus.net)
Date: 06/29/04 

Date: Tue, 29 Jun 2004 16:00:17 GMT

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. 

-- 
#191, ewill3@earthlink.net
It's still legal to go .sigless.

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, ... >can't be picked again, so the second roll is only 35-sided, ...
    (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)