Difference between revisions of "Combinatorial identity"
(Relevent link add, needs more work) |
Willy132423 (talk | contribs) m (→Pascal's Identity) |
||
(114 intermediate revisions by 45 users not shown) | |||
Line 1: | Line 1: | ||
+ | == Pascal's Identity == | ||
+ | Pascal's Identity states that | ||
+ | |||
+ | <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math> | ||
+ | |||
+ | for any [[positive integer]]s <math>k</math> and <math>n</math>. Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = {}_nC_k = C_k^n</math>. | ||
+ | |||
+ | This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things. | ||
+ | |||
+ | === Proof === | ||
+ | If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial. So assume <math>k \leq n</math>. Thenfd | ||
+ | |||
+ | <cmath>\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\ | ||
+ | &=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\ | ||
+ | &=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\ | ||
+ | &=&\frac{n!}{k!(n-k)!}\\ | ||
+ | &=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath> | ||
+ | |||
+ | ===Alternate Proofs=== | ||
+ | Here, we prove this using [[committee forming]]. | ||
+ | |||
+ | Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways. | ||
+ | |||
+ | Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways. | ||
+ | |||
+ | But we already know they can be picked in <math>\binom{n}{k}</math> ways, so | ||
+ | |||
+ | <cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} </cmath> | ||
+ | |||
+ | |||
+ | Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>. | ||
+ | |||
+ | ==Vandermonde's Identity== | ||
+ | Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>. | ||
+ | |||
+ | ===Video Proof=== | ||
+ | |||
+ | https://www.youtube.com/watch?v=u1fktz9U9ig | ||
+ | |||
+ | ===Combinatorial Proof=== | ||
+ | |||
+ | Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true. | ||
+ | |||
+ | ~avn | ||
+ | |||
+ | ===Algebraic proof=== | ||
+ | For all <math>x,</math> <cmath>(1+x)^m(1+x)^n = (1+x)^{m+n}</cmath> | ||
+ | The coefficients of <math>x^r</math> on both sides must be the same, so using the [[Binomial Theorem]], <cmath>\sum_{k=0}^r \binom mk \binom n{r-k} = \binom {m+n}r.</cmath> | ||
+ | |||
==Hockey-Stick Identity== | ==Hockey-Stick Identity== | ||
+ | For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>. | ||
+ | |||
+ | <asy> | ||
+ | int chew(int n,int r){ | ||
+ | int res=1; | ||
+ | for(int i=0;i<r;++i){ | ||
+ | res=quotient(res*(n-i),i+1); | ||
+ | } | ||
+ | return res; | ||
+ | } | ||
+ | for(int n=0;n<9;++n){ | ||
+ | for(int i=0;i<=n;++i){ | ||
+ | if((i==2 && n<8)||(i==3 && n==8)){ | ||
+ | if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);} | ||
+ | else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);} | ||
+ | } | ||
+ | else{ | ||
+ | label(string(chew(n,i)),(11+n/2-i,-n)); | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </asy> | ||
+ | |||
+ | This identity is known as the ''hockey-stick'' identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed. We can also flip the hockey stick because pascal's triangle is symmetrical. | ||
+ | |||
+ | |||
+ | ===Proof=== | ||
+ | |||
+ | '''Inductive Proof''' | ||
+ | |||
+ | This identity can be proven by induction on <math>n</math>. | ||
+ | |||
+ | <u>Base Case</u> | ||
+ | Let <math>n=r</math>. | ||
+ | |||
+ | <math>\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}</math>. | ||
+ | |||
+ | <u>Inductive Step</u> | ||
+ | Suppose, for some <math>k\in\mathbb{N}, k>r</math>, <math>\sum^k_{i=r}{i\choose r}={k+1\choose r+1}</math>. | ||
+ | Then <math>\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}</math>. | ||
+ | |||
+ | '''Algebraic Proof''' | ||
+ | |||
+ | It can also be proven algebraically with [[Pascal's Identity]], <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>. | ||
+ | Note that | ||
+ | |||
+ | <math>{r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math> | ||
+ | <math>={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}</math> | ||
+ | <math>={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r+1}+{r+a \choose r}={r+a+1 \choose r+1}</math>, which is equivalent to the desired result. | ||
+ | |||
+ | '''Combinatorial Proof 1''' | ||
+ | |||
+ | Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result. | ||
+ | |||
+ | '''Combinatorial Proof 2''' | ||
+ | |||
+ | We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people. We can divide this into <math>n-k+1</math> disjoint cases. In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee. This can be done in <math>\binom{n-x+1}{k}</math> ways. Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath> | ||
+ | |||
+ | |||
+ | |||
+ | '''Algebraic Proof 2''' | ||
+ | |||
+ | Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity. | ||
+ | |||
+ | '''Algebraic Proof 3''' | ||
+ | |||
+ | Consider the number of solutions to the equation <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ≤ N where each <math>a_i</math> is a | ||
+ | non-negative integer for 1≤i≤r. | ||
+ | |||
+ | '''METHOD 1''' | ||
+ | We know since all numbers on LHS are non-negative therefore 0≤N and N is a integer. | ||
+ | |||
+ | Therfore, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> = 0,1,2......N. Consider each case seperately. | ||
+ | |||
+ | <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =0 by [[Stars-and-bars]] the equation has <math>\binom {0+r-1}{r-1}</math> solutions. | ||
+ | |||
+ | <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =1 by [[Stars-and-bars]] the equation has <math>\binom {1+r-1}{r-1}</math> solutions. | ||
− | ==Vandermonde's Identity== | + | <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =2 by [[Stars-and-bars]] the equation has <math>\binom {2+r-1}{r-1}</math> solutions. |
+ | |||
+ | ........... | ||
+ | <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> =N by [[Stars-and-bars]] the equation has <math>\binom {N+r-1}{r-1}</math> solutions. | ||
+ | |||
+ | Hence, the equation has <math>\binom {r-1}{r-1}</math>+ <math>\binom {r}{r-1}</math>+ <math>\binom {r+1}{r-1}</math>+.... <math>\binom {N+r-1}{r-1}</math>= <math>\sum^k_{i=r-1}{i\choose r-1}</math> (where k=N+r-1) SOLUTIONS. | ||
+ | |||
+ | '''METHOD 2''' | ||
+ | Since, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ≤ N Therefore we may say <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> = N -m where m is another non-negative integer. | ||
+ | 0 ≤<math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> ⇒ 0≤ N-m ⇒ m≤ N So, we need not count this as an extra restriction. | ||
+ | |||
+ | Now, <math>a_1</math>+<math>a_2</math>+<math>a_3</math>+<math>a_4</math>+<math>a_5</math>+<math>a_6</math>+.......+<math>a_r</math> +m = N. Again by [[Stars-and-bars]] this has <math>\binom {N+r}{r}</math> solutions. | ||
+ | |||
+ | Therefore, the equation has <math>\binom {N+r}{r}</math> = <math>\binom {k+1}{r}</math> solutions(As N+r-1 =k). | ||
+ | |||
+ | Since, both methods yeild the same answer ⇒''' <math>\sum^k_{i=r-1}{i\choose r-1}</math> = <math>\binom {k+1}{r}</math>'''. Taking r-1= p redirects to the honeystick identity. | ||
+ | |||
+ | ~SANSGANKRSNGUPTA | ||
+ | |||
+ | ==Another Identity== | ||
+ | |||
+ | <cmath> | ||
+ | \sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k} | ||
+ | </cmath> | ||
+ | |||
+ | ===Hat Proof=== | ||
+ | We have <math>2k</math> different hats. We split them into two groups, each with k hats: then we choose <math>i</math> hats from the first group and <math>k-i</math> hats from the second group. This may be done in <math>\binom{k}{i}^2</math> ways. Evidently, to generate all possible choices of <math>k</math> hats from the <math>2k</math> hats, we must choose <math>i=0,1,\cdots,k</math> hats from the first <math>k</math> and the remaining <math>k-i</math> hats from the second <math>k</math>; the sum over all such <math>i</math> is the number of ways of choosing <math>k</math> hats from <math>2k</math>. Therefore <math>\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}</math>, as desired. | ||
+ | |||
+ | ===Proof 2=== | ||
+ | This is a special case of Vandermonde's identity, in which we set <math>m=n=r</math>. | ||
+ | |||
+ | == Even Odd Identity == | ||
+ | <cmath> | ||
+ | \sum_{k=0}^m (-1)^k \binom{n}{k}= (-1)^m \binom{n-1}{m} | ||
+ | </cmath> | ||
== Examples == | == Examples == | ||
− | + | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=394407#394407 1986 AIME Problem 11] | |
− | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 AIME | + | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385891 2000 AIME II Problem 7] |
+ | * [https://artofproblemsolving.com/wiki/index.php?title=2013_AIME_I_Problems/Problem_6#Solution_2 2013 AIME I Problem 6 (Solution 2)] | ||
+ | * [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12] | ||
+ | * [http://artofproblemsolving.com/wiki/index.php/2018_AIME_I_Problems/Problem_10 2018 AIME I Problem 10] | ||
+ | * [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7] | ||
+ | * [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20] | ||
+ | * [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_15 2021 AMC 12A Problem 15] | ||
+ | * [https://artofproblemsolving.com/wiki/index.php/1981_IMO_Problems 1981 IMO Problem 2] | ||
+ | * [https://artofproblemsolving.com/wiki/index.php/2022_AIME_I_Problems/Problem_12 2022 AIME I Problem 12 ] | ||
==See also== | ==See also== | ||
+ | * [[Pascal's Triangle]] | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
+ | * [[Pascal's Identity]] | ||
+ | |||
+ | [[Category:Theorems]] | ||
+ | |||
+ | [[Category:Combinatorics]] |
Latest revision as of 20:06, 23 June 2024
Contents
Pascal's Identity
Pascal's Identity states that
for any positive integers and
. Here,
is the binomial coefficient
.
This result can be interpreted combinatorially as follows: the number of ways to choose things from
things is equal to the number of ways to choose
things from
things added to the number of ways to choose
things from
things.
Proof
If then
and so the result is trivial. So assume
. Thenfd
Alternate Proofs
Here, we prove this using committee forming.
Consider picking one fixed object out of objects. Then, we can choose
objects including that one in
ways.
Because our final group of objects either contains the specified one or doesn't, we can choose the group in ways.
But we already know they can be picked in ways, so
Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term . Above that, we would see the terms
and
. Due to the definition of Pascal's Triangle,
.
Vandermonde's Identity
Vandermonde's Identity states that , which can be proven combinatorially by noting that any combination of
objects from a group of
objects must have some
objects from group
and the remaining from group
.
Video Proof
https://www.youtube.com/watch?v=u1fktz9U9ig
Combinatorial Proof
Think of the right hand side as picking people from
men and
women. Think of the left hand side as picking
men from the
total men and picking
women from the
total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.
~avn
Algebraic proof
For all
The coefficients of
on both sides must be the same, so using the Binomial Theorem,
Hockey-Stick Identity
For .
This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself is highlighted, a hockey-stick shape is revealed. We can also flip the hockey stick because pascal's triangle is symmetrical.
Proof
Inductive Proof
This identity can be proven by induction on .
Base Case
Let .
.
Inductive Step
Suppose, for some ,
.
Then
.
Algebraic Proof
It can also be proven algebraically with Pascal's Identity, .
Note that
, which is equivalent to the desired result.
Combinatorial Proof 1
Imagine that we are distributing indistinguishable candies to
distinguishable children. By a direct application of Balls and Urns, there are
ways to do this. Alternatively, we can first give
candies to the oldest child so that we are essentially giving
candies to
kids and again, with Balls and Urns,
, which simplifies to the desired result.
Combinatorial Proof 2
We can form a committee of size from a group of
people in
ways. Now we hand out the numbers
to
of the
people. We can divide this into
disjoint cases. In general, in case
,
, person
is on the committee and persons
are not on the committee. This can be done in
ways. Now we can sum the values of these
disjoint cases, getting
Algebraic Proof 2
Apply the finite geometric series formula to :
Then expand with the Binomial Theorem and simplify:
Finally, equate coefficients of
on both sides:
Since for
,
, this simplifies to the hockey stick identity.
Algebraic Proof 3
Consider the number of solutions to the equation +
+
+
+
+
+.......+
≤ N where each
is a
non-negative integer for 1≤i≤r.
METHOD 1 We know since all numbers on LHS are non-negative therefore 0≤N and N is a integer.
Therfore, +
+
+
+
+
+.......+
= 0,1,2......N. Consider each case seperately.
+
+
+
+
+
+.......+
=0 by Stars-and-bars the equation has
solutions.
+
+
+
+
+
+.......+
=1 by Stars-and-bars the equation has
solutions.
+
+
+
+
+
+.......+
=2 by Stars-and-bars the equation has
solutions.
...........
+
+
+
+
+
+.......+
=N by Stars-and-bars the equation has
solutions.
Hence, the equation has +
+
+....
=
(where k=N+r-1) SOLUTIONS.
METHOD 2
Since, +
+
+
+
+
+.......+
≤ N Therefore we may say
+
+
+
+
+
+.......+
= N -m where m is another non-negative integer.
0 ≤
+
+
+
+
+
+.......+
⇒ 0≤ N-m ⇒ m≤ N So, we need not count this as an extra restriction.
Now, +
+
+
+
+
+.......+
+m = N. Again by Stars-and-bars this has
solutions.
Therefore, the equation has =
solutions(As N+r-1 =k).
Since, both methods yeild the same answer ⇒ =
. Taking r-1= p redirects to the honeystick identity.
~SANSGANKRSNGUPTA
Another Identity
Hat Proof
We have different hats. We split them into two groups, each with k hats: then we choose
hats from the first group and
hats from the second group. This may be done in
ways. Evidently, to generate all possible choices of
hats from the
hats, we must choose
hats from the first
and the remaining
hats from the second
; the sum over all such
is the number of ways of choosing
hats from
. Therefore
, as desired.
Proof 2
This is a special case of Vandermonde's identity, in which we set .
Even Odd Identity
Examples
- 1986 AIME Problem 11
- 2000 AIME II Problem 7
- 2013 AIME I Problem 6 (Solution 2)
- 2015 AIME I Problem 12
- 2018 AIME I Problem 10
- 2020 AIME I Problem 7
- 2016 AMC 10A Problem 20
- 2021 AMC 12A Problem 15
- 1981 IMO Problem 2
- 2022 AIME I Problem 12