# Combinatorics - Total # of possibilities of a number sequence with given conditions

Consider a ten-digit sequence of positive integers 0 - 9.
The 1st, 4th, and 5th digits are either 7 or 9
3rd and tenth digits are either 2 or 4.
Somewhere in the phone number are 2 zeros, and the sum of all the digits equate to 42.
What are all possible such sequence of 10 digits??

Just from going by total possible ways of arranging said numbers we have $2^5 * 10^3 * 5!$ (for each specified digit slot there are 2 ways of doing it. In the 5 slots left in 2 digits it has to be zero so 1 way of picking those, and 10 ways of picking the unspecified digits and 5! ways of arranging those digits. From that I guess we can use method of complements and find set of all possible number that DO NOT add up to 42 and subtract the total permutations by that, but my problem is calculating the cardinality of said set. Is the only way of doing so directly/explicitly? If so then it seems like I have a lot of calculating to do..

-
That $5!$ shouldn't be there; you already selected the 2 slots with 5, you cannot shuffle them; and you are already filling the other three slots in order, you cannot shuffle them. – Arturo Magidin Nov 15 '11 at 6:48
The unspecified 5 digits, we're told zero can go anywhere in those 5 slots, then the left over 3 slots are then decided by wherever we choose to place the zero. Since the ordering matters, shouldn't we need to shuffle those 5 digits around? – Friday Nov 15 '11 at 6:54
No: first you choose the slots for 2 zeros; once you choose the slots, you decide what goes on the first empty slot, then the second, then the third. By multiplying by 5! you are counting, say, 00123 once when you select "first two open slots for the 0s", and then again when you select "fourth and fifth open slots for the zeros" and shuffle them so they end up in the first two. In addition, you are overcounting as well because you are allowing 0s in the other three empty slots; so you will count 00000 many, many times. – Arturo Magidin Nov 15 '11 at 14:47

The two possibilities for the half-fixed digits all differ by $2$. The lowest value for their sum is $3\cdot7+2\cdot2=25$ and the highest is $25+5\cdot2=35$. For the six values $25+2n$, there are $\binom5n$ ways of choosing the half-fixed digits to make that sum. That leaves $17-2n$ to be composed by the remaining digits. The rest I'm afraid is details; you'll have to figure out the numbers of compositions with parts not greater than $9$ of the various possible remaining sums.
As you note, you have $2^3$ ways of filling in the 1st, 4th, and 5th position of the number. And you have $2^2$ ways of filling in the 3rd and 10th. So it comes down to figuring out the number of ways to fill out the remaining five positions. To count those, I will ignore the 1st, 3rd, 4th, 5th, and 10th position, and think simply that we are trying to fill out five positions (which will correspond to the 2nd, 6th, 7th, 8th, and 9th positions of the phone number).
If exactly two of these five positions must be equal to $0$, then we can first select which two positions will get the zeros: this can be done in $\binom{5}{2}=10$ ways. Then we select the digits to go in the three remaining positions, in order: there are $9$ possible digits for the first open position, $9$ for the second open position, and $9$ for the third open position. This gives $10\times 9^3$, and that's it. We don't need to "shuffle them". In fact, we shouldn't! If we multiply by $5!$, then we are overcounting: consider the situation in which we select the first two positions for the $0$, and we take 1, 2, and 3 for the remaining three open positions, in that order. Multiplying by 5!$will give us all possible "reshuffles" of 00123; e.g., 00312. But we already counted that one: we counted it when we said that 3 could be in the first open position, 1 in the second, and 2 in the third. Worse! Multiplying by 5! includes the shuffle in which we exchange the first and second positions and do nothing else: but doing that to 00123 just gives 00123 back! So we are overcounting. We don't need that 5!. Under this interpretation ("exactly two zeros"), the total number (ignoring the restriction on the sum being equal to$42$) would be$2^3\times 2^2\times\binom{5}{2}\times 9^3 = 2^5\times 10\times 9^3$. Now consider the case in which there are at least two zeros, but could be more. In this case, after selecting the two positions for the two zeros, it would seem that we now have 10 choices for each of the remaining three open slots, giving$\binom{10}{2}\times 10^3 = 10^4$possibilities. Unfortunately, this overcounts as well, when the number has more than two zeros. For example, 00012 is counted three times: once when we designate the first and second positions as having$0$s, and happen to select the third as having a zero; again when we designate first and third positions; and yet again when we designate second and third positions. So you would have to be more carefl; here as well. One possibility is to use inclusion-exclusion; another is to be more careful, and count those with exactly two zeros first; then those with exactly three zeros ($\binom{5}{3}\times 9^2$); then those with exactly four zeros ($\binom{5}{4}\times 9$), and finally those with exactly five zeros ($\binom{5}{5}=1$). In any case, we don't need that$5!\$ "shuffling factor" here either.