Problem 5: February 2024

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:

- \(A\), \(B\), \(C\)
- \(A\), \(B\), \(D\)
- \(A\), \(C\), \(D\)
- \(B\), \(C\), \(D\)

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\)?