Intereting Posts

Solving ODE with negative expansion power series
What is the exact and precise definition of an ANGLE?
Is the conjugation map always an isomorphism?
Weak convergence and strong convergence
Does an integral operator with a symmetric integrable kernel have to be bounded on $L^2$?
Expected Value of Max of IID Variables
How to construct symmetric and positive definite $A,B,C$ such that $A+B+C=I$?
Congruence properties of $x_1^6+x_2^6+x_3^6+x_4^6+x_5^6 = z^6$?
Meromorphic and even
Common factors of cyclotomic polynomials and polynomials with prime coefficients
Is $\sum_{n=1}^\infty \frac{\sin(2n)}{1+\cos^4(n)}$ convergent?
Is $\log(n!) \in\Theta(n \log n)$
Is a 2-dimensional subspace always called a plane no matter what the dimensions of the space is?
Dimension of vector space of real numbers over rational number field
Notation — What does “Gauss” brackets mean

I want to prove this equation,

$$

\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}

$$

I thought of proving this equation by prove that you are using different ways to count the same set of balls and get the same result. But I’m stuck. Help me please.

(Presumptive) Source: Theoretical Exercise 1.14(a), P19, *A First Course in Pr*, 8th Ed, by S Ross.

- Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$
- Proof that a Combination is an integer
- Why General Leibniz rule and Newton's Binomial are so similar?
- Calculate limit involving binomial coefficient
- Good upper bound for $\sum\limits_{i=1}^{k}{n \choose i}$?
- How are lopsided binomials (eg $\binom{n}{n+1})?$ defined?

- Combinatorics : # of ways to invite the guests
- How many solutions for equation with simple restrictions
- Find $\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1}$
- Permutation and Combination- Rowing a Boat
- Permutations of a string with duplicate characters
- Prove that $\prod_{k=1}^{\infty} \big\{(1+\frac1{k})^{k+\frac1{2}}\big/e\big\} = \dfrac{e}{\sqrt{2\pi}}$
- How many different ways can you distribute 5 apples and 8 oranges among six children?
- Combinations of selecting $n$ objects with $k$ different types
- Find a closed formula for $\sum_{n=1}^\infty nx^{n-1}$
- Proof $\displaystyle \binom{p-1}{k}\equiv (-1)^k \mod{p}$

First comes a bureaucratic answer.

We have a group of $n$ people. We want to select a committee of $b$ people, and choose $a$ of them to be a steering subcommittee.

The right-hand side counts the number of ways to pick the committee of $b$ people, and then choose the steering subcommittee from this committee.

The left-hand side picks the steering subcommittee first, then the rest of the committee.

Both sides count the same thing, so they are the same.

Or else we want to choose $b$ people from a class of $n$ to go on a trip. Of these $b$ people, $a$ will ride in the limousine, and the rest in an old bus. We can choose the $b$ people, and then choose the $a$ of them who will ride in the limousine.

Or else we can choose the $a$ people who will ride in the limousine , and then pick $b-a$ people from the remaining $n-a$ to ride in the bus.

Directly, we find that

\begin{align*}

{n \choose a}{n – a \choose b – a} &= \frac{n!}{(n – a)!a!} \frac{(n – a)!}{(n – a – (b – a))! (b – a)!} \\

&= \frac{n!}{a!} \frac{1}{(n – b)!(b – a)!} \\

&= \frac{n!}{(n – b)! b!} \frac{b!}{(b – a)!a!} \\

&= {n \choose b}{b \choose a}

\end{align*}

The third equality follows by multiplying and dividing by $b!$.

These are just two different ways to express the trinomial coefficient $\binom n{a,b-a,n-b}$ as a product of two binomial coefficients. The relevant formula (not obviously present on the wikipedia page) is

$$

\binom n{k,l,m} = \binom nk\binom {n-k}l \qquad\text{whenever $k+l+m=n$,}

$$

together with the symmetry with respect to $x,y,z$ of the trinomial coefficient, and similarly for binomial coefficients (so that $\binom nb=\binom n{n-b}$). The formula above is a consequence of $(X+Y+Z)^n=(X+(Y+Z))^n$, and similar formulas hold for higher multinomial coefficients.

Given $n$ people, we can form a committee of size $b$ in ${n\choose b}$ ways. Once the committee is formed we can form a sub-committee of size $a$ in ${b\choose a}$ ways. Thus we can form a committee of size $b$ with a sub-committee of size $a$ in ${n\choose b}{b\choose a}$ ways. We can count the same thing by forming the sub-committee first and then forming the committee that contains the sub-committee. Given $n$ people we can form a sub-committee of size $a$ in ${n\choose a}$ ways. Once the sub-committee is formed we must form the committee of size $b-a$ from the remaining $n-a$ people in ${n-a\choose b-a}$ ways. Thus we can form a sub-committee of size $a$ while forming the committee of size $b-a$ that contains the sub-committee in ${n\choose a}{n-a\choose b-a}$ ways. Hence ${n\choose b}{b\choose a}={n\choose a}{n-a\choose b-a}$.

This combinatorial identity is known as the Subset-of-a-Subset identity.

- How do collinear points on a matrix affect its rank?
- Proving $~\sum_\text{cyclic}\left(\frac{1}{y^{2}+z^{2}}+\frac{1}{1-yz}\right)\geq 9$
- Independence of Poisson random variables coming from Poisson sampling
- Is the following claim true: “every ordinal has the empty set as one of its elements”
- Are axioms and rules of inference interchangeable?
- Why $f(x) = \sqrt{x}$ is a function?
- Solving a set of linked recurrent relations
- How can I evaluate $\lim_{x\to1}\frac{\sqrt{5-x}-2}{\sqrt{2-x}-1}$ without invoking l'Hôpital's rule?
- How to calculate product $\prod_{k=0}^{n-1}\left (1+\frac{1}{2^{2^k}}\right)$?
- How can I compare two matrices?
- An eigenvalue problem for positive semidefinite matrix
- how to solve $\int\frac{1}{1+x^4}dx$
- How to study for analysis?
- Maximize absolute value of complex logarithm
- Complex Integral with exponential