{"id":285,"date":"2016-05-26T00:55:01","date_gmt":"2016-05-26T00:55:01","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=285"},"modified":"2016-05-30T08:57:02","modified_gmt":"2016-05-30T08:57:02","slug":"double-counting-part-2","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/double-counting-part-2\/","title":{"rendered":"Double-counting, Part 2"},"content":{"rendered":"

This post is a follow-up to Part 1<\/a>, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills!<\/p>\n

First identity.<\/b> This is Vandermonde’s Identity<\/a>.
\n\\[
\n\\sum_{k=0}^p {m \\choose k}{n \\choose p-k} = {m+n \\choose p}
\n\\]<\/p>\n

[Show Solution]<\/a><\/p>\n

\nSuppose we have a population of $m$ boys and $n$ girls and we’d like to count how many groups of $p$ people we can make. This is clearly $m+n \\choose p$. Another way to count is to let $k$ be the number of boys in our group. We can choose the boys in $m \\choose k$ ways, and the remaining $p-k$ group members, which must be girls, can be chosen in $n \\choose p-k$ ways. So there are ${m \\choose k}{n \\choose p-k}$ groups that contain $k$ boys. Summing this over all possible $k$ gives us the total number of groups with any number of boys.<\/p>\n<\/div>\n

Second identity.<\/b> This is the Christmas Stocking Identity<\/a>. It is also sometimes called the Hockey-Stick Identity.
\n\\[
\n\\sum_{k=0}^m {n+k \\choose n} = {m+n+1 \\choose n+1}
\n\\]<\/p>\n

[Show Solution]<\/a><\/p>\n

\nSuppose we have a set of $m+n+1$ marbles and we would like to choose a subset of size $n+1$. There are $m+n+1 \\choose n+1$ ways of doing this. Counting differently, suppose the marbles are numbered $1,2,\\dots,m+n+1$. Since we are choosing $n+1$ marbles, the largest-numbered marble in our subset must have label $n+1$ or larger. If the largest-numbered marble in our subset has label $n+k+1$ ($k=0,1,\\dots,m$), then the remaining $n$ marbles must be selected among the $n+k$ smaller-numbered marbles, which can be done in $n+k \\choose n$ ways. <\/p>\n<\/div>\n

Third identity.<\/b> This one looks similar to the first one, but notice that the upper<\/em> coefficient is varying this time.
\n\\[
\n\\sum_{k=0}^p {k \\choose m}{p-k \\choose n} = {p+1 \\choose m+n+1}
\n\\]<\/p>\n

[Show Solution]<\/a><\/p>\n

\nSuppose we have a set of $p+1$ marbles and we’d like to choose a subset of size $m+n+1$. There are $p+1 \\choose m+n+1$ ways of doing this. Counting differently, suppose the marbles are numbered $1,2,\\dots,p+1$. We’ll select our subset in order of ascending labels: first we’ll choose the $m$ smallest-numbered marbles, then the middle marble, and then the $n$ remaining larger-numbered marbles. If our middle marble happens to be labeled $k+1$, there are $k$ smaller marbles (labeled $1,2,\\dots,k$) among which we need to choose $m$, so $k \\choose m$ ways. Likewise, there are $p-k$ larger marbles (labeled $k+2,k+3,\\dots,p$) among which we need to choose $n$, so $p-k \\choose n$ ways. As we sum over all possible values of the middle marble, we obtain the expression on the left-hand side.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This post is a follow-up to Part 1, where I talked about the technique of double-counting in the context of proving combinatorial identities. In this post, I’ll show three more identities that can be proven using simple double-counting. Test your skills! First identity. This is Vandermonde’s Identity. \\[ \\sum_{k=0}^p {m \\choose k}{n \\choose p-k} = … Continue reading “Double-counting, Part 2”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[12],"tags":[9,6],"class_list":["post-285","post","type-post","status-publish","format-standard","hentry","category-tutorials","tag-binomial","tag-counting"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=285"}],"version-history":[{"count":9,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/285\/revisions"}],"predecessor-version":[{"id":294,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/285\/revisions\/294"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}