0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ ${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)!}$. $\endgroup$ – Ian May 15 '18 at 2:30
  • $\begingroup$ Thank you! If you'll write that out as an answer, I'll take it. I didn't even know what to Google for that, haha $\endgroup$ – aecend May 15 '18 at 2:31
  • $\begingroup$ google for "binomial coefficient" $\endgroup$ – fleablood May 15 '18 at 2:36
  • $\begingroup$ "If you'll write that out as an answer, I'll take it" and then "One last question; the "!" in that formula, how does one evaluate that?" Please don't take answer if you don't understand them. If you don't understand, ask further. $\endgroup$ – fleablood May 15 '18 at 2:41
  • $\begingroup$ This is not an equation. It is rather a definition of the function $f(d,n)$. $\endgroup$ – user May 15 '18 at 21:28
1
$\begingroup$

${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)!}$.

$\endgroup$
  • $\begingroup$ One last question; the "!" in that formula, how does one evaluate that? $\endgroup$ – aecend May 15 '18 at 2:33
  • $\begingroup$ $n!$ where $n$ is a positive integer (for now) is the value you get when you multiply $1*2*3*4*.........*(n-1)*n$. $\endgroup$ – fleablood May 15 '18 at 2:35
  • $\begingroup$ @fleablood Thank you!!! $\endgroup$ – aecend May 15 '18 at 2:38
2
$\begingroup$

${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.

$\endgroup$

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.