# Unique permutations from set with repetitions

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.

• 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. Nov 26, 2014 at 21:22

## 1 Answer

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.

• 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. Nov 27, 2014 at 20:31
• 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. Nov 28, 2014 at 13:16
• The multiplication with 20! was the missing link. Got it - Thank you! Nov 28, 2014 at 15:34
• see EDIT 2 above. Nov 30, 2014 at 12:51
• 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. Nov 30, 2014 at 14:38