Problem of the Month
Problem 5: February 2024
Introduction
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 and
, the expression denotes the number of ways
to choose objects from distinct objects. For this reason, the
quantity is
pronounced " choose ".
For example, consider the four letters , , , and . There are ways to select three of them. They are as follows:
Since there are ways to choose of the objects (order does not matter –
it only matters which objects are chosen), we have that .
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 .
What are and
?
Convince yourself that for .
Convince yourself that
when .
Convince yourself that is equal to the coefficient
of in the expanded form of
. This is why is called a "binomial
coefficient".
It turns out that there is a convenient way to compute binomial
coefficients using factorial notation. If are integers, then . Here,
, pronounced " factorial", is defined so that when and , and for integers . It
is also a useful exercise to think about why this formula for works.
Main Problems
For a positive integer ,
show that is the
answer to each of these three questions. Think about why the answers to
all three questions are the same.
What is ?
How many pairs of
non-negative integers satisfy ?
How many triples of
non-negative integers satisfy ?
Let and 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 indistinguishable balls in distinguishable cups?
How many non-negative integer solutions are there to the equation
?
Let and be integers. By counting -tuples of non-negative integers that satisfy , prove the
identity Clarification: The quantity on
the left in the equation above is the sum of the binomial coefficients
where ranges from to .
Determine the number of non-negative integers with that have a digit sum of .
For a positive integer where
the are the digits of , the alternating sum of is the expression . For
example, the alternating sum of is . Determine the number of
non-negative integers with at most digits that have an alternating sum
equal to .
How many ways are there to choose integers , , and such that and ?