Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've somewhat got this question down but I'm only half way.

How many $7$-digit even numbers less than $3,000,000$ can be formed using all the digits $1,2,2,3,5,5,6$?

So I figured that there's about $4$ possible approaches

$1$ _ _ _ _ _ $6$
$1$ _ _ _ _ _ $2$
$2$ _ _ _ _ _ $6$
$2$ _ _ _ _ _ $2$

How do I fill in the middle? I tried $5!$ and dividing out the similar factorials but I didn't get the right answer .

share|improve this question

3 Answers 3

We actually have only two cases: 1... and 2... .

In the first case, we have to fit the numbers 2,2,3,5,5,6 somehow. Imagine that we tag each of the repeated elements somehow, e.g. 2',2",3,5',5",6. If we care about the tags, then there are $6!$ possible ways to arrange the numbers. Now each untagged arrangement corresponds to $2!2!$ different tagged arrangements (consider the order in which the tags on the $2$s and $5$s appear). In total, this gives $6!/2!2!= 180$.

In the second case, we have only one repeated element $5$ so there are $6!/2! = 360$ possibilities, for a total of $540$.

In general, if we have $k$ unique elements repeated $t_1,\ldots,t_k$ times (respectively), then the answer is going to be $(t_1+\cdots+t_k)!/t_1!\cdots t_k!$, using the same reasoning. This is known as a multinomial coefficient since it appears in the multinomial theorem:

$$(x_1 + \cdots + x_k)^n = \sum_{t_1 + \cdots + t_k = n} n!/t_1!\cdots t_k! x_1^{t_1} \cdots x_k^{t_k}$$

where the sum is over all non-negative integers summing to $n$. The multinomial coefficient is sometimes denoted $\binom{n}{t_1\ldots t_k}$, although one of these numbers is really redundant. When $k=2$ we get the binomial coefficient, and we usually omit $t_2$.

share|improve this answer
    
This can be checked computationally: In GAP, Size(Filtered(PermutationsList([1,2,2,3,5,5,6]),i->i[1]<3)); which agrees with the result in this answer. –  Douglas S. Stones Sep 17 '10 at 3:42

It appears that both previous answers missed that the number was to be even. So the real count is 5!/2! + 5!/2!/2! + 5!/2! + 5!/2! = 210

share|improve this answer
    
Nicely spotted! (I'm going to delete my answer) –  Douglas S. Stones Sep 18 '10 at 1:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.