Intereting Posts

Prove that the limit of $\sin n$ as $n \rightarrow \infty$ does not exist
Mean curvature in terms of Christoffel symbols
Two problems about Structure Theorem for finitely generated modules over PIDs
Different ways to prove there are infinitely many primes?
Is $z^{-1}(e^z-1)$ surjective?
Taking away infinitely many elements infinitely many times
Is $1$ a subset of $\{1\}$
Essential Supremum vs. Uniform norm
Minimum / Maximum and other Advanced Properties of the Covariance of Two Random Variables
Express Integer as Sum of Two Squares
totally bounded, complete $\implies$ compact
Prove that Anosov Automorphisms are chaotic
Infinite Integration by Parts
Can anybody explain about real linear space and complex linear space?
Bounded data means bounded solution to parabolic PDE

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.

- Finding a combinatorial argument for an interesting identity: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$
- Sum involving the product of binomial coefficients
- Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$
- Calculate the binomial sum $ I_n=\sum_{i=0}^n (-1)^i { 2n+1-i \choose i} $
- On a “coincidence” of two sequences involving $a_n = {_2F_1}\left(\tfrac{1}{2},-n;\tfrac{3}{2};\tfrac{1}{2}\right)$
- Prove that $\sum\limits_{k=0}^r\binom{n+k}k=\binom{n+r+1}r$ using combinatoric arguments.

- From a bag containing $10$ pairs of socks, how many must a person pull out to ensure that they get at least $2$ matching pairs of socks?
- 6-letter permutations in MISSISSIPPI
- Enumerate certain special configurations - combinatorics.
- Uniformly distributed points distance question
- Double Factorial: Number of possibilities to partition a set of $2n$ items into $n$ pairs
- Every $k$ vertices in an $k$ - connected graph are contained in a cycle.
- Number of equivalence relations splitting set into sets with exactly 3 elements
- Finding binomial coefficients of product of two binomials
- Positive integers less than 1000 without repeated digits
- Number of monomials of certain degree

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.

- Prove that $\sum^{n}_{r=0}(-1)^r\cdot \large\frac{\binom{n}{r}}{\binom{r+3}{r}} = \frac{3!}{2(n+3)}$
- Extended Euclidean Algorithm, what is our answer?
- k-Cells are Connected
- About the Riemann surface associated to an analytic germ
- How to construct examples of functions in the Spaces of type $\mathcal{S}$
- Alternate definition of Hilbert space operator norm
- Four fractions of certain factorials give another factorial
- Show that $(\sqrt{2}-1)^n$ is irrational
- Solving a 2nd order differential equation by the Frobenius method
- How many different ways can a number N be expressed as a sum of K different positive integers?
- Matrices whose Linear Combinations are All Singular
- Cardinal equalities: $\aleph_0^\mathfrak c=2^\mathfrak c$
- What is A Set Raised to the 0 Power? (In Relation to the Definition of a Nullary Operation)
- Product of spheres embeds in Euclidean space of 1 dimension higher
- Is there a set theory that avoids Russel's paradox while still allowing one to define the set of all sets not containing themselves?