\nSuppose we have a population of $m$ boys and $n$ girls and we\u2019d 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.\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. \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\u2019d 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\u2019ll select our subset in order of ascending labels: first we\u2019ll 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.\n<\/div>\n<\/body>","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\u2019ll show three more identities that can be proven using simple double-counting. Test your skills! First identity. This is Vandermonde\u2019s 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":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t