5
$\begingroup$

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$

Not quite where to starting proving this one. Thanks!

$\endgroup$
  • 1
    $\begingroup$ The definition of $C$ is usually a great starting point. $\endgroup$ – Jonny Nov 10 '14 at 21:20
  • $\begingroup$ Edited for clarification. $\endgroup$ – sanic Nov 10 '14 at 21:22
  • $\begingroup$ A combinatorial argument means to count the same set of things two different ways. $\endgroup$ – Matthew Leingang Nov 11 '14 at 1:02
12
$\begingroup$

Hint

From $6$ candidate, how many ways do we have to form a team and pick a team leader?

$\endgroup$
3
$\begingroup$

For whatever it's worth, here's a standard probabilistic argument: The number of ways to get $k$ heads in six trials when tossing a coin is $\dbinom 6 k$. If all $2^6=64$ sequences are equally likely (as they are when the coin is "fair", i.e. gives heads and tails equally often) then the probability of exactly $k$ successes in $6$ trials is $\dbinom 6 k \cdot \dfrac 1 {64}$. So the average number of successes in $6$ trials is $$ \frac{\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6}}{64}. $$

But the average number of successes in $6$ trials, with probability $1/2$ of success on each trial, is $6\cdot\frac 1 2=3$, so the sum above equals $3$.

On way of showing that the average number of successes with six trials is three is to observe that the average number of successes in one trial is $1/2$, so you're just adding up $1/2$ six times, getting $3$.

$\endgroup$
2
$\begingroup$

$$2^5$$ is just a way to count the elements in a 5 member set. (For each member of the set you make a binary decision to include it or not)

Now let's say you have a six element set.

Let's look at $$ \binom{6}{1} $$ Fix any member of the 6 element set. Now you have 5 members left. So that is $$ \binom{5}{1} $$ But you could have choosen that fixed member in 6 ways. So that is effectively $$ 6\cdot\binom{5}{1} $$ Repeat the same argument for each binomial and we get:

$$ 6(\binom{5}{1} + \binom{5}{2} +\binom{5}{3} + \binom{5}{4} + \binom{5}{5} + \binom{5}{6}) $$

But what is inside the parenthesis is simply another way of counting the sub-sets of a set of 5 elements.

$\endgroup$
1
$\begingroup$

Hint: $C(n,m)$ counts the number of $m$ element subsets of a set with $n$ elements. What are you changing as you change $m$? How does $C(n,m)$ relate to $C(n,n-m)$? How does that let you simplify your sum?

$\endgroup$
  • $\begingroup$ as m changes, the number multiplying the combinations changes. That I see. I dont understand how the right hand side is formulated from that? Why do you focus on C(n, n - m)? $\endgroup$ – sanic Nov 10 '14 at 21:31
  • $\begingroup$ I focus on $C(n, n-m)$ because you have a sum where, for a lot of $m$'s (about half), you have $(m\cdot C(n,m)) + ((n-m)\cdot C(n, n-m))$ by rearranging the order of additions. $\endgroup$ – nomen Nov 10 '14 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.