Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am a beginner in the subject of combinatorics and would like to know a few things. A) Someone please explain me how we get the K to the nth number of ways of distributing n distinct objects in k boxes.

B) When do we use the following methods: a+b+c+..+n = x ; and (1 + x + x^2 + x^3+...) to the power something

share|cite|improve this question
I don't understand part (B). The first is rather specific, in the second are you asking about virtually the entire theory of generating functions or...? – anon Apr 29 '12 at 10:03
Maybe a book like Path to Combinatorics for Undergraduates will help? – Eisen Apr 29 '12 at 12:28

About 1: You get $k^n$ since for each of the $n$ elements you have $k$ choices (you choose the box), so you have $k\cdot k\cdots k$ exactly $n$ times (this is "the product principle" of combinatorics in action).

In 2 I think you're confusing the notation. The basic idea here is this: suppose you have the equation $a+b=n$ where $a,b$ can get every nonnegative integer value. One way to find the number of solutions is to compute the coefficient of $x^n$ in $(x^0+x^1+x^2+x^3+\dots)(x^0+x^1+x^2+x^3+\dots)$.

Here the first parenthesis represents the values that can $a$ can get, in the exponent of $x$; the second parenthesis represents values $b$ can get.

Now, to generalize this, all you need to do is add more parenthesis - one for each variable in the original equation - and maybe remove some elements from specific parenthesis. For example, if we have the equation $a+b+c=n$ and we demand that $a$ is odd and $b$ is even (and $c$ whatever), this is described by $$(x^1+x^3+x^5+\dots)(x^0+x^2+x^4+\dots)(x^0+x^1+x^2+x^3+\dots)$$

(Note the exponents).

share|cite|improve this answer

protected by Zev Chonoles Apr 20 '13 at 0:47

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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