Could someone please explain the steps to solve an equation like this?

Question

Honestly, I have no idea if I put the correct tag on this question, and I don't even know where to begin to solve an equation like this: $$ f(d,n)=\sum_{i=1}^n\binom{d}{i}. $$

Could someone explain what the "d" over the "i" inside the parenthesis means? I'm attempting to solve for when d is equal to 20, n is equal to 3, but I can't work out what I'm supposed to do here.

Thanks all!

Answer 1

${d \choose i}$ is read as "d choose i" and is called a binomial coefficient. It is given by the formula $\frac{d!}{i!(d-i)!}$.

Answer 2

${d \choose i}$ = "d choose i" is the number of different ways to choose $i$ objects from $d$, total.

So for example if you are given a bag with $a,b,c,d$ in it and you are told to pick two items you can do one of the following: pick $a,b$ ; pick $a,c$; pick $a,d$; pick $b,c$; pick $b,d$ or pick $c,d$. Those are six possible ways. So ${6 \choose 2} = $ "$4$ choose $2$" $= 6$.

So is there an alegebraic formula for ${d\choose i}$? Why, yes there is.

There are $d$ options of the first item. Once you choose the first there are $d-1$ for then second all the way down to $d-i + 1$ chooses for the last item.

So for picking two items from $a,b,c,$ you have $4$ for the first item and $3$ for the second.

So there are $d*(d-1)*(d-2)*.....*(d-i + 1)$ ways to pick out a list of $i$ items.

So there are $4*3$ ways to choose a list of two items from $a,b,c,d$.

There is $a,b; a,c; a,d; b,a; b,c;b,d; c, a; c,b; c,d;$ and $d,a;d,b;d,c$.

But wait! That is treating $a,b$ as though it is the different than $b,a$ and $d,a$ as though it is different than $a,d$.

For every list of $i$ items there are several ways to order them. But we consider them the same no matter how we order them. So the ways to pick them are $\frac {d*(d-1)*....*(d-i+1)}{\text{ number of ways to order a list of }i\text{ items}}$.

So what is $\text{ number of ways to order a list of }i\text{ items}$? Well, there are $i$ ways to choose the first item, $i-1$ ways to choose the second and so on, all the way down to $1$ choice for the last item. $\text{ number of ways to order a list of }i\text{ items} = i*(i-1)*....*2*1$.

So ${d\choose i} = \frac {d*(d-1)*....*(d-i+1)}{i*(i-1) *.....* 2*1}$.

Jeez, that's a lot to type out. Is there any shorthand notation for that? Why, yes there is.

If $k$ is a positive integer we refer to $k!$ = "$k$ factorial" as $k*(k-1)*(k-2)*...2*1$. This is number of ways you can order $k$ items. Example: $2! = 2*1 = 2$ and we can order $a,b$ in two ways: either $a$ comes first or $b$ does. Example: $3! = 3*2*1 = 6$ and we can order $a,b,c$ six ways: either $a$ or $b$ or $c$ comes first. If $a$ comes first the either $b$ or $c$ can come second whereas if $b$ comes first than either $a$ or $c$ can come second, and if $c$ comes first, $a$ or $b$ can come second. In other words; $abc; acb; bac;bca;cab;cba$. And if you want to figure out how many ways you can arrange the $26$ letters of the alphabet it is: $26*25*24*....*3*2*1 = 26! = 403291461126605635584000000$.

So ${d\choose i}= \frac {d*(d-1)*....*(d-i+1)}{i*(i-1)*....*1} = \frac {d*(d-1)*....*(d-i+1)}{i*(i-1)*....*1}*\frac {(d-i)*(d-i-1)*....*2*1}{(d-i)*(d-i-1)*....*2*1} = \frac {d*(d-1)*....*(d-i+1)*(d-i)*(d-i-1)*....*2*1}{(i*(i-1)*....*1)*((d-i)*(d-i-1)*....*2*1)}=\frac {d!}{(d-i)!*i!}$.

Okay.... that is what ${d\choose i}$ is.

So what is ${d \choose 1} + {d\choose 2} + {d\choose 3} + .... + {d\choose n}$ equal to? Well that is an entirely other question. I'll let you play with it.