sum of binomial series of the form $\sum^{9}_{k=0}\binom{10}{10-k}(10-k)^9$

Question

Finding sum of $$\binom{10}{10}10^9-\binom{10}{1}9^9+\binom{10}{2}8^9-\cdots \cdots -\binom{10}{9}$$

Attempt: $$\binom{10}{10}10^9-\binom{10}{1}9^9+\binom{10}{2}8^9-\cdots \cdots -\binom{10}{9}=\sum^{9}_{k=0}\binom{10}{10-k}(10-k)^9$$

$$=\sum^{9}_{k=0}\binom{10}{k}(10-k)^9$$

I am not be able to go further , could some help me how to solve it , thanks

Answer 1

Suppose that you want to get an account at a fictional website called Math StuckExchange, but to do that you need to make up a password.

Passwords have to be sequences of exactly $9$ digits, such as $314159265$ or $000000000$. However, to make sure that the password is secure, each digit between $0$ and $9$ has to be used at least once.

(At least they don't require any special characters!)

---

We can count the number of passwords that satisfy this requirement by the principle of inclusion-exclusion.

• First of all, there are $10^9$ passwords total.
• But then we should subtract the passwords that only use $9$ digits. There are $\binom{10}{1}$ ways to choose which digits to leave out, and $9^9$ ways to make a password with those digits: $\binom{10}{1} 9^9$ such passwords total.
• But then, as usual with inclusion-exclusion, we should add back in passwords that only use $8$ digits, because we subtracted them too many times. There are $\binom{10}{2}$ ways to choose which digits to leave out, and $8^9$ ways to make a password with those digits: $\binom{10}{2} 8^9$ such passwords total.
• Then we should subtract the passwords that only use $7$ digits, and so on...

When we're done with this process, we get the formula $$10^9 - \binom{10}{1} 9^9 + \binom{10}{2} 8^9 - \binom{10}{3} 7^9 + \dots - \binom{10}{9} 1^9$$ for the total number of possible passwords. This happens to be exactly the sum you want to evaluate.

---

Unfortunately for Math StuckExchange, there is a problem with their password requirements. How many passwords are there that are $9$ digits long, but use every digit between $0$ and $9$?