This problem explores a counting technique that uses binomial coefficients. The main problems for this month are in the next section. For anyone who is not already familiar with the notation of binomial coefficients, this section includes an introduction with a few standard exercises.
For non-negative integers \(n\) and \(k\), the expression \(\dbinom{n}{k}\) denotes the number of ways to choose \(k\) objects from \(n\) distinct objects. For this reason, the quantity \(\dbinom{n}{k}\) is pronounced "\(n\) choose \(k\)".
For example, consider the four letters \(A\), \(B\), \(C\), and \(D\). There are \(4\) ways to select three of them. They are as follows:
Since there are \(4\) ways to choose \(3\) of the objects (order does not matter – it only matters which objects are chosen), we have that \(\dbinom{4}{3}=4\).
Try the following exercises. Hints will be provided, but solutions will not. These exercises are intended as a way to get familiar with the notation, so they may not be explicitly useful in the main problems.
Show that \(\dbinom{5}{2}=10\).
What are \(\dbinom{n}{0}\) and \(\dbinom{n}{1}\)?
Convince yourself that \(\dbinom{n}{k}=\dbinom{n}{n-k}\) for \(0\leq k\leq n\).
Convince yourself that \(\dbinom{n}{k}+\dbinom{n}{k+1}=\dbinom{n+1}{k+1}\) when \(0\leq k < n\).
Convince yourself that \(\dbinom{n}{k}\) is equal to the coefficient of \(x^k\) in the expanded form of \((1+x)^n\). This is why \(\dbinom{n}{k}\) is called a "binomial coefficient".
It turns out that there is a convenient way to compute binomial coefficients using factorial notation. If \(n\geq k\geq 0\) are integers, then \(\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}\). Here, \(m!\), pronounced "\(m\) factorial", is defined so that \(m!=1\) when \(m=0\) and \(m=1\), and \(m!=1\times2\times3\times\cdots\times(m-1)\times m\) for integers \(m\geq 2\). It is also a useful exercise to think about why this formula for \(\dbinom{n}{k}\) works.
For a positive integer \(n\), show that \(\dbinom{n+1}{2}\) is the answer to each of these three questions. Think about why the answers to all three questions are the same.
What is \(1+2+3+\cdots+n\)?
How many pairs \((x,y)\) of non-negative integers satisfy \(x+y\leq n-1\)?
How many triples \((x,y,z)\) of non-negative integers satisfy \(x+y+z=n-1\)?
Let \(n\geq 0\) and \(r\geq 1\) be integers. Show that the following two questions have the same answer and express the common answer as a single binomial coefficient.
How many ways are there to place \(n\) indistinguishable balls in \(r\) distinguishable cups?
How many non-negative integer solutions are there to the equation \(x_1+x_2+\cdots+x_r=n\)?
Let \(n\geq 0\) and \(r\geq 1\) be integers. By counting \(r\)-tuples of non-negative integers \((x_1,x_2,\dots,x_r)\) that satisfy \(x_1+x_2+x_3+\cdots+x_r \leq n\), prove the identity \[\dbinom{r-1}{r-1}+\dbinom{r}{r-1} + \dbinom{r+1}{r-1} + \dbinom{r+2}{r-1}+\cdots+\dbinom{r-1+n}{r-1} = \dbinom{n+r}{r}\] Clarification: The quantity on the left in the equation above is the sum of the binomial coefficients \(\dbinom{r-1+m}{r-1}\) where \(m\) ranges from \(0\) to \(n\).
Determine the number of non-negative integers \(x\) with \(x< 10^{10}\) that have a digit sum of \(21\).
For a positive integer \(x=a_na_{n-1}a_{n-2}\cdots a_{1}a_0\) where the \(a_i\) are the digits of \(x\), the alternating sum of \(x\) is the expression \(a_0-a_1+a_2-a_3+\cdots+(-1)^na_n\). For example, the alternating sum of \(744923\) is \(3-2+9-4+4-7=3\). Determine the number of non-negative integers with at most \(8\) digits that have an alternating sum equal to \(0\).
How many ways are there to choose integers \(a\), \(b\), and \(c\) such that \(1\leq a < b < c \leq 2024\) and \(a+b+c=2027\)?