I would appreciate if somebody could help me with the following problem

Q: Seeking a combinatorial proof



Consider a bag with balls numbered from $1$ to $n$. Number of ways of choosing $2$ balls with replacement is $n^2$.

We can also count the same in a different way. The pair of balls can be represented as $(i,j)$. Let us now look at the number of ways such that $\max\{i,j\} = k$, where $k \in \{1,2,\ldots,n\}$. If $C_k$ denotes the number of ways such that $\max\{i,j\} = k$, we then have $$C_k = 2k-1$$ This is because if $\max\{i,j\} = k$, then either $j<i=k$ or $i<j=k$ or $i=j=k$.

  • Number of ways such that $j<i=k$ is $k-1$.
  • Number of ways such that $i<j=k$ is $k-1$.
  • Number of ways such that $i=j=k$ is $1$.

Hence, we have $C_k=2k-1$. Hence, the total number of ways of choosing a pair of balls from $n$ balls with replacement is $$\sum_{k=1}^n C_k$$

  • 4
    $\begingroup$ This is what I’d call a combinatorial proof. @Gerry’s familiar proof without words is elegant and non-computational, and I don’t have a really strong objection to calling it combinatorial, but I don’t think of it in those terms. (+1) $\endgroup$ – Brian M. Scott Oct 6 '13 at 2:28

$$\matrix{a&b&c&d&e&\dots\cr b&b&c&d&e&\dots\cr c&c&c&d&e&\dots\cr d&d&d&d&e&\dots\cr e&e&e&e&e&\dots\cr\vdots&\vdots&\vdots&\vdots&\vdots&\dots\cr}$$


Not the answer you're looking for? Browse other questions tagged or ask your own question.