Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I kinda feel ashamed about asking this, but could someone explain me what this means? $$ \binom{k}{i} $$

That should indicate the number of nodes at a certain depth in a binomial heap..but I can't remember what that actually means and I wasn't successful with Google!

Any explanation/link/idea would be awesome!

Thanks

==================================

edit and added

so if i had $$ \binom{0}{0} $$ would that be $$ \dfrac{0!}{0!(0-0)!} $$ ...what would that be...zero?

share|improve this question
1  
Search for binomial coefficient and use \binom{k}{i} to get MathJax to format it properly for display as $\binom{k}{i}$. –  Dilip Sarwate Feb 9 '13 at 15:47
3  
No need to feel ashamed, Seb! That's what we're here for...ask away! Your question was good, and showed context, was clear, and it's hard to google for something when you don't know what to call it! –  amWhy Feb 9 '13 at 16:07
    
thanks for the edits and for the patient :)! –  TriRook Feb 9 '13 at 16:07
    
@Seb Once you know that $0! = 1$, you can answer your own question about $\binom00$. In general $\binom{k}{i}$ is only zero when $i < 0$ or when $i > k$. –  Erick Wong Feb 9 '13 at 19:26
add comment

4 Answers

up vote 7 down vote accepted

I assume you mean $$\dbinom{n}k$$ $\dbinom{n}k$ is a short hand for the number of ways in which you can choose $k$ objects from $n$ distinguishable objects. These number are called the binomial coefficients. Some textbooks and articles also denote this as $C(n,k)$.

As an example, if we have three colored balls, $\color{red}{\text{red}}$, $\color{blue}{\text{blue}}$ and $\color{brown}{\text{brown}}$, then there are three ways of choosing two balls. \begin{matrix} \color{red}{\text{red}} & \color{blue}{\text{blue}}\\ \color{blue}{\text{blue}} & \color{brown}{\text{brown}}\\ \color{brown}{\text{brown}} & \color{red}{\text{red}} \end{matrix} Note that when we say we choose, we are not interested in the order in which these are picked i.e. $\color{red}{\text{red}} \,\, \color{blue}{\text{blue}}$ and $\color{blue}{\text{blue}} \,\, \color{red}{\text{red}}$ refer to the same choice of two balls. Hence, we have $\dbinom{3}2 = 3$.

Similarly, if we have $5$ colored balls, say $\color{red}{\text{red}}$, $\color{blue}{\text{blue}}$, $\color{brown}{\text{brown}}$, $\color{orange}{\text{orange}}$, and $\color{lightgreen}{\text{green}}$, there are $10$ ways of choosing $3$ balls. \begin{matrix} \color{red}{\text{red}} & \color{blue}{\text{blue}} & \color{brown}{\text{brown}}\\ \color{red}{\text{red}} & \color{blue}{\text{blue}} & \color{orange}{\text{orange}}\\ \color{red}{\text{red}} & \color{blue}{\text{blue}} & \color{lightgreen}{\text{green}}\\ \color{red}{\text{red}} & \color{orange}{\text{orange}} & \color{brown}{\text{brown}}\\ \color{red}{\text{red}} & \color{orange}{\text{orange}} & \color{lightgreen}{\text{green}}\\ \color{red}{\text{red}} & \color{brown}{\text{brown}} & \color{lightgreen}{\text{green}}\\ \color{blue}{\text{blue}} & \color{brown}{\text{brown}} & \color{orange}{\text{orange}}\\ \color{blue}{\text{blue}} & \color{brown}{\text{brown}} & \color{lightgreen}{\text{green}}\\ \color{blue}{\text{blue}} & \color{orange}{\text{orange}} & \color{lightgreen}{\text{green}}\\ \color{orange}{\text{orange}} & \color{brown}{\text{brown}} & \color{lightgreen}{\text{green}} \end{matrix}

In general, $$\dbinom{n}r = \dfrac{n!}{r!(n-r)!}$$ where $k! = k \times (k-1) \times (k-2) \times \cdots \times 2 \times 1$.

The name binomial coefficient arises from binomial theorem. When we expand $(x+y)^n$, the coefficient of $x^k y^{n-k}$ is given by $\dbinom{n}k$ i.e. $$(x+y)^n = \sum_{k=0}^n \dbinom{n}k x^k y^{n-k}$$ There are a lot of wonderful properties these binomial coefficients satisfy and I highly recommend you to go through the wiki-page for these properties.

share|improve this answer
    
Nice answer! Your examples would probably look better as matrixes than as aligns. –  Rahul Feb 9 '13 at 16:36
    
@ℝⁿ. Thanks. Yes. These indeed look better. I have updated them. –  user17762 Feb 9 '13 at 16:39
    
awesome answer thanks for taking time to go through it so well!! I have a question but i'll post it below cause i'm trying to put a formula in.. –  TriRook Feb 9 '13 at 17:02
add comment

$$\binom{k}{i}\; \text{ is called a $\color{blue}{\bf{binomial\;coefficient}}$, which is read as "k choose i"}$$

See Binomial Coefficient.

"k choose i" comes from the fact that if gives you the number of ways to choose $i$ elements from a set of $k$ elements. The term "binomial coefficient" makes explicit its relationship to the binomial theorem. When we expand $(x+y)^n$, the coefficient of $x^k y^{n-k}$ is given by $\large\binom{n}k$ i.e. $$(x+y)^n = \sum_{k=0}^n \dbinom{n}k x^k y^{n-k}$$

You can compute your binomial coeffient by noting that $$\displaystyle \;\binom{k}{i} = \frac{k!}{i!(k-i)!} = \frac{k\cdot (k-1)\cdots (k - i + 1)}{i\cdot (i-1) \cdots 2 \cdot 1}$$

share|improve this answer
    
I've not in recent times ever heard $\binom{k}{i}$ read as anything other than "$k$ choose $i$". (But maybe I don't get out enough ...) –  Peter Smith Feb 9 '13 at 16:12
    
@PeterSmith Good point; "often" should have been "usually", which should probably be omitted altogether! Edited accordingly. –  amWhy Feb 9 '13 at 16:16
add comment

$k \choose i$ is a binomial coefficient. It is the coefficient of $x^i$ in expanding $(1+x)^k$. It is also the number of $i$-element subsets of a $k$-element set. It can be computed via $\frac{k!}{i!(k-i)!}$ or with several recursive formulas. Values are often listed with help of Pascal's triangle.

share|improve this answer
add comment

For the question in the edit: We have $0! = 1$, so $\binom{0}{0} = 1$ which is the first entry in Pascal's triangle.

A previous question on this site asked about the definition of zero factorial; there are several excellent answers there. As Zhen Lin points out in a comment, the best explanation of why $0! = 1$ depends on how you define the factorial.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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