{"id":262,"date":"2016-05-25T19:48:25","date_gmt":"2016-05-25T19:48:25","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=262"},"modified":"2016-05-30T08:57:15","modified_gmt":"2016-05-30T08:57:15","slug":"double-counting-part-1","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/double-counting-part-1\/","title":{"rendered":"Double-counting, Part 1"},"content":{"rendered":"

Double-counting<\/em> is one of my favorite proof techniques. The idea is simple: count the same thing in two different ways. In this post, I’ll give some examples of double-counting in the context of proving identities involving binomial coefficients, but it’s a very general technique that can be applied to many other types of problems. <\/p>\n

Pascal’s identity.<\/b> The following is known as Pascal’s identity<\/a>:<\/p>\n

\\[
\n{n \\choose k} = {n-1 \\choose k-1} + {n-1 \\choose k}
\n\\]<\/p>\n

Of course, Pascal’s Identity can also be proven directly using simple algebra, but there is a nice double-counting alternative. Suppose we have a group of $n$ people, and we’d like to choose a committee of $k$ members. There are $n \\choose k$ ways of doing this. Now let’s count the number of committees in a different way. Suppose we pick out one particular person from the group, let’s call her Alice. There are $n-1\\choose k-1$ committees that include<\/em> Alice, because after we’ve included Alice, there are $k-1$ remaining committee members to choose out $n-1$ remaining people. Similarly, there are $n-1\\choose k$ committees that exclude<\/em> Alice, because all $k$ committee members must be chosen out of the remaining $n-1$ people. The total number of committees is equal to the number of committees that include Alice plus the number of committees that exclude Alice, and this completes the proof of Pascal’s Identity.<\/p>\n

Binomial theorem.<\/b> Here is another familiar identity:<\/p>\n

\\[
\n{n \\choose 0} + {n \\choose 1} + \\dots + {n \\choose n} = 2^n
\n\\]<\/p>\n

This identity can be directly obtained by applying the Binomial Theorem<\/a> to $(1+1)^n$. But once again, we can use a double-counting argument. Suppose we have a group of $n$ people. Let’s count the total number of subsets of this group. One way to count is to realize that there are $n \\choose k$ different subsets of size $k$. So the total number of subsets of any size is the sum on the left-hand side of the identity. On the other hand, we can count subsets by looking at each person one at a time. Each person can either be included or excluded in the subset ($2$ possibilities), which yields a total of $2\\times 2 \\times \\dots \\times 2 = 2^n$ possible subsets.<\/p>\n

Binomial products.<\/b> This example involves products:<\/p>\n

\\[
\n{n \\choose s}{s \\choose r} = {n \\choose r}{n-r \\choose s-r}
\n\\]<\/p>\n

Consider a group of $n$ people. This time, we count the number of ways of selecting a team of $s$ members, among which $r$ are designated as captains. One way to do this is to start by selecting the team, which can be done in $n \\choose s$ ways. For each team, we then select the captains, which can be done in $s \\choose r$ ways. The total is therefore ${n \\choose s}{s \\choose r}$. Another way to count is to start by selecting the captains first, which can be done in $n \\choose r$ ways. Then, we must select the rest of the team. There remains $n-r$ people and we must choose $s-r$ to round out the team. So the total count is ${n \\choose r}{n-r \\choose s-r}$.<\/p>\n

This technique of committee selection<\/em> is very powerful. See if you can figure out how to apply it to the following example!<\/p>\n

\\[
\n{n \\choose 1} + 2 {n\\choose 2} + 3 {n\\choose 3} + \\dots + n {n \\choose n} = n 2^{n-1}
\n\\]<\/p>\n

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

\n

Given a group of $n$ people, count the number of ways of forming a committee of any size where one person is appointed as the chairperson. One way is to let $k$ be the size of the committee. There are $n \\choose k$ possible committees of size $k$, and $k$ possible choices of chairperson. This leads to the left-hand side of the equation. Another way to count is to start by appointing the chairperson, which can be done in $n$ ways. Once a chairperson is selected, we must assemble the rest of the committee, which is any subset of the remaining $n-1$ people. There are $2^{n-1}$ possible subsets (see the Binomial Theorem example above), which leads us to the right-hand side of the equation.\n<\/p><\/div>\n

For more double-counting problems, check out Part 2<\/a>!<\/p>\n","protected":false},"excerpt":{"rendered":"

Double-counting is one of my favorite proof techniques. The idea is simple: count the same thing in two different ways. In this post, I’ll give some examples of double-counting in the context of proving identities involving binomial coefficients, but it’s a very general technique that can be applied to many other types of problems. Pascal’s … Continue reading “Double-counting, Part 1”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"footnotes":""},"categories":[12],"tags":[9,6],"class_list":["post-262","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