Given a digits {$0,1,2,...,9$} . Find the number of numbers of 6 digits which cantain $7$ or $7$'s digit and they is permulated(For example 137456 and 314756 is one numbers).
Problem
Source: UZMO 2012
Tags: combinatorics unsolved, combinatorics
29.05.2012 15:40
shohvanilu wrote: Given a digits {$0,1,2,...,9$} . Find the number of numbers of 6 digits which cantain $7$ or $7$'s digit and they is permulated(For example 137456 and 314756 is one numbers). Interpreted: shohvanilu wrote: Find the number of multisets which are subsets of $\{0,1,2,\ldots,9\}$ and contain $7$. If there is one $7$, there are $5$ elements remaining in the multiset, and by a well-known theorem (number of $k$-element multisets where the elements are also in a set of cardinality $n$ is $\binom{n+k-1}{k}$) there is $\binom{9+5-1}{5} = 1287$ multisets. Similarly, if there are two $7$, there are $4$ elements remaining, and hence $\binom{9+4-1}{4} = 495$ multisets. If there are three $7$, there are $3$ elements remaining, and hence $\binom{9+3-1}{3} = 165$ multisets. If there are four $7$, there are $2$ elements remaining, and hence $\binom{9+2-1}{2} = 45$ multisets. If there are five $7$, there is $1$ element remaining, and hence $\binom{9+1-1}{1} = 9$ multisets. If there are six $7$, it's trivial that there is only one multiset possible (which is also given from $\binom{9+0-1}{0} = 1$). Hence $1287 + 495 + 165 + 45 + 9 + 1 = \boxed{2002}$ multisets in total. EDIT: Or otherwise fix an element to be $7$, and the rest follows identically: $\binom{10+5-1}{5} = \boxed{2002}$ multisets. Why didn't I think of this before