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.

Sorry for the very basic question. I'm a programmer, not a mathematician. The title says it all but I'll just include a little background on why I asked the (stupid?) question.

I'd just finished solving Problem 15 from Project Euler. I used brute force (soooo slow) and I was curious if there's a faster way to do solve the problem. Most people from the Project Euler forum said that the problem could be solved using Combination or Pascal's Triangle. I googled those terms and found these interesting posts:

I understood the facinating relationship between Binomial Expansions and Pascal's Triangle, but I don't quite get the "Combination formula" as the shortcut/formula in getting the Binomial Coefficients.

Request:
Since I'm not a math gal, please refrain from posting very "deep"/complicated formulas. Just imagine you're trying to teach Binomial Expansions to a 9th grade student. ;)

If this is a duplicate post, I'm sorry, I don't know what math terms to search for. If I used the wrong terminologies, I'm sorry. Feel free to edit them.

Thanks in advance. :)

Related but hard to grok (for me) post: question about binomial expansion's coefficients

share|improve this question
2  
Your question is unclear. What do you mean by "the combination formula"? Is your question actually the following: If we let $f(n,k)$ be the coefficient of $x^k$ in the expansion of $(1+x)^n$, why do we get $f(n,k)=n!/(k!(n-k)!)$? –  Gerry Myerson May 3 '12 at 6:18
    
@Gerry: that's how I read her question. I'm sure the combinatorial interpretation of expanding a binomial was already discussed here a long time ago... –  J. M. May 3 '12 at 6:20
3  
BTW Anne: it's not a stupid question at all; I upvoted because of that, and because you took time to search around before asking. :) –  J. M. May 3 '12 at 6:21
2  
Here is a question you might want to see. –  J. M. May 3 '12 at 6:26
3  
This one may also be of interest. –  Brian M. Scott May 3 '12 at 6:27
show 7 more comments

3 Answers 3

up vote 4 down vote accepted

The symbol

$$n\choose k$$

is a shorthand for "The number of ways to choose $k$ objects from a collection of $n$ objects."

That is: you have $n$ objects in a line. You select $k$ of them, and paint them red, and you paint the other $n-k$ blue. How many ways are there to do that so that the final result looks different?

A moment of reflection will convince you that you could have chosen $n-k$ of the objects to paint blue first, and painted the rest of the objects red. The answer shouldn't depend on something arbitrary like whether you pick up the blue or the red paint first. If you can grok this fact, then you will have proved to yourself that

$${n\choose k} = {n\choose n-k}$$

How does this relate to binomial expansions? Well, say that we want to expand

$$(r + b)^n$$

Then we'll get a bunch of terms, each of which is a product of some $r$s with some $b$s. There are $n$ brackets, so there will be $n$ multipliers in each of the terms, and each of them will be either $r$ or $b$, so every term looks like

$$a_kr^kb^{n-k}$$

where $a_k$ is a coefficient, and $k=0, 1, 2, \dots n$.

What is $a_k$? Notice that in every bracket, we have to choose either an $r$ or a $b$. We can imagine going through the brackets one by one and making these choices, or you can imagine looking at all the brackets at once, and choosing which of them to pick $r$ form and which to pick $b$ from. The coefficient $a_k$ is the number of different ways of picking $k$ $r$s and $(n-k)$ $bs$ from the $n$ brackets. That is:

$$a_k = {n\choose k}$$

which, using the fact from earlier, we can instantly use to prove that the coefficients in a binomial expansion are symmetric:

$$a_k = {n\choose k} = {n\choose n-k} = a_{n-k}$$

Maybe you can see how binomial expansions relate to Pascal's triangle now?

Hint: It is linked to another cool and exciting relationship between the binomial coefficients!

share|improve this answer
add comment

Every path in the square consists of exactly $2n$ segments; $n$ 'right' segments (R) and $n$ 'down' segments (D). Every path is a sequence of R's and D's, and the only difference between two paths is then the order of them.

For example, the $2\times2$ case has RRDD, RDRD, RDDR, DDRR, DRDR, and DRRD as the different sequences.

So the question becomes 'how many difference sequences of $n$ R's and $n$ D's can you make?' The answer is given by combinations, or the elements of Pascal's triangle. Of the $2n$ different positions, we want to choose $n$ of them to place the R's, and once that's done the sequence is completely determined. (Put the R's in the places you picked and the D's in all the others.)

Therefore, there are $\binom{2n}{n}$ different paths in an $n \times n$ grid. So for our $2 \times 2$ example, there are $\binom{4}{2} = 6$ different paths, for a $20 \times 20$ grid, there are $\binom{40}{20} = 137846528820$ paths.

share|improve this answer
add comment

Hint: The binomial coefficient $${n\choose k}=\frac{n!}{k!\,(n-k)!}={n\choose n-k}$$ tells you how many ways you can pick $k$ of $n$ identical objects. To get from $(0,0)$ to $(j,k)$ only with moves of $+1$ in the $x$ or $y$ direction, you need a total $n=$ _____ (how many?) moves. Take these as generic, but ordered, objects: move #1, move #2, all the way up to number $n$. Now, which of these moves are in fact in the $x$ direction, and how many ways can you choose that? (By the symmetry above, you can check that the number of paths with $j$ moves in the $x$ direction is the same as the number of paths with $k$ moves in the $y$ direction.)

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.