# Math nomenclature

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!

Thanks

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

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

-
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
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

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.

-
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

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

"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}$$

-
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

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

-

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.

-