[Math] How to calculate the number of possible license plate using the formula for combinations with repetitions allowed

combinationscombinatoricspermutations

I'm having a little trouble reconciling two different methods for calculating the number of license plates that can be formed from three letters (from the standard 26-letter alphabet) and four digits, where repetition of characters is allowed and the letters and digits may appear in any order.

The first thought I had was to consider the letters and digits as two separate permutations before mixing them together. There are $26^3$ possible permutations of three letters and $10^4$ possible permutations of four digits. Since the permutations of letters and digits come pre-ordered by definition, all that remains is to choose the letter/digit pattern that appears in the license plate. This can be thought of as either the number of ways to divide the seven license-plate positions into two groups, the number of ways to choose three positions from the seven to contain the letters, or the number of ways to choose four positions from the seven to contain the digits. In any event, this evaluates to $\binom{7}{3}=35$. So, the total number of license plates given these constraints is $35\cdot26^3\cdot10^4=6151600000$.

However, I feel that there should also be a way to approach this problem using the expression for combinations of $r$ objects from a group of $n$ with repetitions allowed, $\binom{r+n-1}{r}$. From my understanding, this formula allows me to determine the number of ways to construct an unordered "pool" of letters and digits by first choosing three letters with repetition allowed,

$$\binom{3+26-1}{3}=\frac{(3+26-1)!}{3!\,(26-1)!}=3276\text{,}$$

then choosing four digits with repetition allowed,

$$\binom{4+10-1}{4}=\frac{(4+10-1)!}{4!\,(10-1)!}=715\text{,}$$

then multiplying the two numbers together to get $3276\cdot715=2342340$. From there, there are $7!$ ways to permute any chosen assortment of seven letters and digits, so the final answer is $7!\cdot2342340=11805393600$, nearly twice the previous answer. This second method is motivated by the process used to find the number of three-letter, four-digit license plates that are possible when repetition is not allowed; this calculation would proceed by choosing three letters from a group of 26 (without repetition),

$$\binom{26}{3}=\frac{26!}{3!\,(26-3)!}=2600\text{,}$$

then choosing four digits,

$$\binom{10}{4}=\frac{10!}{4!\,(10-4)!}=210\text{,}$$

pooling them in $2600\cdot210=546000$ possible ways, then ordering the pool in $7!$ possible ways to yield $7!\cdot546000=2751840000$. It would seem that to translate this calculation to a scenario in which repetition of letters and digits is allowed, one would simply substitute $\binom{r+n-1}{r}$ for $\binom{n}{r}$ (as I did in the second calculation), but this leads to the incongruity presented above.

I'm not sure exactly where my logic is breaking down, but I can trace it back to the idea of permutations with repetition allowed simply being ordered combinations with repetitions allowed. That is, when repetition is not allowed it is true that $$_n P_r=\frac{n!}{(n-r)!}=r!\frac{n!}{r!\,(n-r)!}=r!\cdot \left(_nC_r\right)\text{,}$$ but when repetition is allowed it is clear that $$_n P_r=r^n\neq r!\cdot\frac{(r+n-1)!}{r!\,(n-1)!}=r!\cdot \left(_nC_r\right)\text{.}$$ This discrepency seems counterintuitive given the respective definitions of permutations and combinations. Can somebody help me understand how all of these puzzle pieces fit together, and how they can be applied to the example problem I've given? Thank you!

Best Answer

The problem with the second method is double-counting. Namely every sequence containing $n_A$ of letters 'A', $n_B$ of letters 'B' and so on will be counted $$n_A!n_B!\cdots$$ times.

Related Question