GO Classes Weekly Quiz 13 | Discrete Mathematics | Combinatorics | Question: 3

Answer 1

1. We can verify algebraically that the identity holds: $$\left(\begin{array}{l}n \\2\end{array}\right)+\left(\begin{array}{c}n+1 \\2\end{array}\right)=\frac{n(n-1)}{2}+\frac{n(n+1)}{2}=n^{2}$$

 

1. Algebraically, this identity is rather immediate. For a combinatorial perspective, consider the task of selecting a cabinet of $k$ people with a president out of $n$ possible candidates. One can either
   1. Select the president in $n$ ways and the remaining $k-1$ members of the cabinet in $\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ ways for a total of $n\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$ ways.
   2. Or select the $k$ members of the cabinet first in $\left(\begin{array}{l}n \\ k\end{array}\right)$ ways and then the president among those in the cabinet in $k$ ways for a total of $k\left(\begin{array}{l}n \\ k\end{array}\right)$ ways.

https://www.goclasses.in/

Comments

For second one we can proof is like ,

LHS ,

$\large k\binom{n}{k}=\frac{k.n!}{k!(n-k)!}$

RHS ,

$\large n\binom{n-1}{k-1}=\frac{n.(n-1)!}{(k-1)!(n-1-k+1)!}$

                  =$\large \frac{k.n!}{k.(k-1)!(n-k)!}$

                   =$\large \frac{k.n!}{k!(n-k)!}$ =LHS

so, LHS=RHS

---

@GO Classes What could be a combinatorial argument for the first part?

Answer 2

Great question. Great answers already by many.

Combinatorial argument for 1.

This answer is plagiarized from math.stackexchange.com so I deserve no credit at all. Just here to explain.

n^2 is the no. of integers less than 100.

2C(n, 2) : is the no. of numbers less than 100 having distinct digits.

C(n,1): is the no. of numbers less than hundred having both digits same.

Therefore,. n^2 = 2C(n, 2) + C(n,1)

                    n^2 = 2C(n,2) + n.

Now coming to the real part.

Our question,

                   C(n, 2) + C( n+1, 2 ) = n^2

                   C(n,2) + C( n+1, 2 ) = 2C(n, 2) + n.

                   C( n+1, 2) = C(n, 2) + n. (we will prove that this is true.)

 LHS

C( n+1, 2) = no. of edges in a n+1 complete graph.

RHS

C(n, 2) + n = no. of edges between n nodes + put another node and join it with all n nodes.

Therefore we have proved that,

            C( n+1, 2 )= C(n, 2) + n.

And hence

            C(n,2)+ C(n+1, 2) = n^2 is true.

Comments

$n^2$ is the number of non-negative integers less than $100 \equiv$ number of $2$ digit numbers with leading $0s$ allowed $\implies n = 10$.

Case $1$ : with distinct digits $= {n \choose 2} * 2!$.

Case $2$ : with same digits $= {n \choose 1}$.

Therefore, $n^2 = 2{n \choose 2} + {n \choose 1}$.

This part was not clear from your solution.