1
$\begingroup$

I am new to combinatorics and might ask a trivial question:

There are $69$ different items, each present $4$ times. From this total of $276$ items, $20$ should be picked at random. I need the formula to find the total number of unique permutations possible. I struggle to deal with the condition that repetitions in the source have a maximum of $4$ and can be combined.

Any help or hint is appreciated.

EDIT:

To make it more down to earth: The $276$ items are lower and upper case characters, numbers and special characters, each present $4$ times. The $20$ equals the password length, formed from this character set. I would like to calculate the password strength against bruteforce attacks.

$\endgroup$
  • $\begingroup$ I tried 276!/(276-20)! to find the set of 20 and 276!/((4!)^69) to deal with the repetitions, but struggle to combine the two. $\endgroup$ – sanjuu Nov 26 '14 at 21:22
2
$\begingroup$

I tried some elementary approaches and failed, but I was able to use exponential generating functions and some computer algebra to obtain a result.

You have 69 distinct characters that can appear up to 4 times on a sequence of length 20. For each character, we have the exponential generating function: $$ \left( \frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right) = \left( 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24}\right)$$

Thus, accounting all 69 characters, we have: $$EG(X) = \left( 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24}\right)^{69} $$ The number of passwords that you want is equivalent to the coefficient of $\frac{x^{20}}{20!}$ on the expansion of $EG(X)$. Using Mathematica, we get the expansion:

$$ EG(x) = \dots + 5980453108717018801550601671826075000 \frac{x^{20}}{20!} + \dots $$

Hence there are 5980453108717018801550601671826075000 different passwords.


PS.: The difficulty of this problems lies on the fact that you had posed some restrictions on both the maximum number of times that an character appears and the number of characters on the password. It may be an innocent looking problem, but questions like this can have messy solutions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice, thank you. I can follow everything until your use of Mathematica. Can the formula be expanded and solved on wolframalpha.com as well? I was unable to reproduce the result and wonder whether you know the approach? My intention is to calculate further results based on your formula. $\endgroup$ – sanjuu Nov 27 '14 at 20:31
  • $\begingroup$ You can try the query: "Expand (1 + x + x^2/2 + x^3/6 + x^4/24)^(69)" and ask for more terms until you get the $x^{20}$ term. It will pop you eventually "(19573373401107120316087345 x^20)/7962624". If you multiply that by $20!$, the coefficient will be $5980453108717018801550601671826075000$, as before. $\endgroup$ – victorsouza Nov 28 '14 at 13:16
  • $\begingroup$ The multiplication with 20! was the missing link. Got it - Thank you! $\endgroup$ – sanjuu Nov 28 '14 at 15:34
  • $\begingroup$ see EDIT 2 above. $\endgroup$ – sanjuu Nov 30 '14 at 12:51
  • $\begingroup$ The term $(1 + x + \frac{x^2}{2})^3 = \dotsc + \frac{9 x^4}{4} + \dotsc $. The coefficient of $x^4$ is $\frac{9}{4}$. But $\frac{4! \cdot 9}{4} = 54$, so the term of $\frac{x^4}{4!}$ is $54$ as wanted. $\endgroup$ – victorsouza Nov 30 '14 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.