7
$\begingroup$

I'm selfstudying 'A walk through combinatorics' by Miklós Bóna. This book has some supplementary exercises at the end of each chapter, no solution provided. I'm trying exercise 51, chapter 3.

Problemstatement:

A store has $n$ different products for sale. Each of them has a different price that is at least one dollar, at most $n$ dollars, and is a whole dollar. A customer only has the time to inspect $k$ different products. After doing so, she buys the product that has the lowest price among the $k$ products she inspected. Prove that on average she will pay $\frac{n+1}{k+1}$ dollars.

Attempt at solution: The customer pays:

  • 1 dollar if the product with price 1 dollar is the cheapest among the $k$ inspected products. This is possible in $\binom{n-1}{k-1}$ ways, since we need to pick $k-1$ products with prices in $\{2, \ldots, n\}$.
  • 2 dollars if the product with price 2 dollars is the cheapest among the $k$ inspected products. This is possible in $\binom{n-2}{k-1}$ ways, since we need to pick $k-1$ products with prices in $\{3, \ldots, n\}$.
  • $\ldots$
  • $n-k+1$ dollar if the product with price $n-k+1$ is the cheapest among the $k$ inspected products. There are only $k-1$ products which are more expensive, so this is possible in $\binom{n-(n-k+1)}{k-1} = \binom{k-1}{k-1}$ ways.

This implies that the customer has to pay, on average $$\frac{1}{\binom{n}{k}}\cdot\left(1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1}\right).$$

This is where I'm stuck: I want to show that the sum in brackets equals $\binom{n+1}{k+1}$ (guess based on what we need to prove, checked with some values of $n,k$. This seems to be correct).

Question: How to prove that $$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1} = \binom{n+1}{k+1},$$ a hint would be appreciated. I tried to give a combinatorial proof, but failed.

$\endgroup$
7
  • $\begingroup$ The identity you want follows from the Vandermonde Identity $\endgroup$
    – lulu
    Commented Dec 29, 2022 at 12:12
  • $\begingroup$ @lulu I tried wrapping my head around this for the last 30 minutes. In the Vandermonde Identity, the $m$ and $n$ are fixed, whereas I have a variable amount to choose from in the summations. Could you elaborate on why this follows from the Vandermonde Identity? $\endgroup$
    – Student
    Commented Dec 29, 2022 at 12:39
  • 3
    $\begingroup$ One version of Vandermonde is $\sum_{m=0}^n\binom mj\times \binom {n-m}{k-j}=\binom {n+1}{k+1}$. See, e.g., this. Now take $j=1$. $\endgroup$
    – lulu
    Commented Dec 29, 2022 at 12:44
  • $\begingroup$ @lulu Thanks. Would you happen to know if there is a combinatorial proof of that version of the identity? $\endgroup$
    – Student
    Commented Dec 29, 2022 at 13:06
  • 1
    $\begingroup$ Oh, to choose $k+1$ out of $n+1$, pick the $(j+1)^{st}$ value, then take $j$ to the left of it and $k-j$ to the right. Might need to play with that idea a bit, but it should be close. $\endgroup$
    – lulu
    Commented Dec 29, 2022 at 13:32

3 Answers 3

5
$\begingroup$

Based on @Lulu's comment, here is a combinatorial proof of the identity needed to complete the solution of the exercise: $$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1} = \binom{n+1}{k+1}$$

Proof: Consider the set $\{0, 1, \ldots, n\}$. Clearly the number of $(k+1)$-element subsets equals $\binom{n+1}{k+1}$.

We could also pick a $(k+1)$-element subset as follows: for an element $x \in \{1,\ldots, n-k+1\}$, take one element in the subset $\{0, 1, \ldots, x-1\}$ and $k-1$ elements in the subset $\{x+1, \ldots, n\}$. There are $x \cdot \binom{n-x}{k-1}$ ways to do this. Summing over all possible values of $x$ proves the identity.

The same approach could be used to prove that $$\sum_{m = 0}^n \binom{m}{j}\binom{n-m}{k-j} = \binom{n+1}{k+1}$$ by taking $j$ elements smaller then $x$ and $k-j$ elements larger than $x$ and summing over all possible values of $x$.

$\endgroup$
2
$\begingroup$

I want to show a proof that uses the lattice interpretation for the binomial coefficients.

A $NE-path$ is a lattice path made up of a unit steps $NORTH$ (from $(a,b)$ to $(a,b+1)$) or unit steps $EAST$ (from $(a,b)$ to $(a+1,b)$).

The binomial coefficient $\binom{n}{k}$ is the number of $NE-paths$ from $(0,0)$ to $(n-k,k)$ (or $(k,n-k)$). Note that you need to take a total of $n$ steps from the origin to get to $(n-k,k)$, out of which exactly $k$ of them have to be $NORTH$.

Now, to come to the identity in question:

$\binom{n+1}{k+1}$ counts the number of $NE-paths$ from $(0,0)$ to $(n-k,k+1)$.

$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1}$ counts the same lattice paths but grouping the paths based on $x-coordinate$ when the lattice path first touches the line $y=2$. (Obviously, any $NE-path$ from $(0,0)$ to $(n-k,k+1)$ has to cross the line $y=2$ for large enough $n,k$).

Once the lattice path touches the line $y=2$, the remainder of the path can be considered as a $NE-path$ from the point of first contact $(i,2)$ to $(n-k,k+1)$.

$\endgroup$
1
$\begingroup$

A small hint for alternative:

  1. List all possible $(k+1)$ - subsets of $\{0,1,...,n\}$
  2. Remove the smallest element from each subset

You'll end up with a list of all possible $k$ - subsets of $\{1,...,n\}$ but with each subset repeated as many times as its smallest element.

How many entries are in the list? $\binom{n+1}{k+1}$

$\endgroup$
2
  • $\begingroup$ I had to write an example to convince myself that this works. Can I ask how you got this idea? What were your thoughts? $\endgroup$
    – Student
    Commented Jan 4, 2023 at 12:15
  • $\begingroup$ @Student for any integer $m$, $\binom{m}{1}=m$. So sometimes when you wish to multiply with $m$, you can think of it as choosing an additional element from a set of $m$ elements. In this particular example, $m$ is the smallest element in a $k$ subset, and the set $\{0,1,...,m-1\}$ contains $m$ elements $\endgroup$
    – acat3
    Commented Jan 4, 2023 at 13:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .