How many ways can 70 planes be allocated into 4 runways? I'm doing some preparations for an upcoming exam, and a little confused about this problem:

"In an airport, 70 flight landings per hour are allocated among 4
  runways. Any flight can land on any of
  the runways and each flight lands on
  exactly one runway. The flight traffic
  controllers are only interested in the
  number of flights on each runway and
  not which flights they are.
  How many ways can the flight traffic
  controller allocate the incoming 70
  flights per hour to the runways? (Some
  runways may have no flights)"

In my understanding, in this problem, repetitions are not allowed, and order does not matter:


*

*Repetitions are not allowed since
once you put a plane down on one
runway, you can't put that plane down
on another runway.

*Order does not matter because as the
question states, "The flight traffic
controllers are only interested in
the number of flights on each runway,
not which flights they are"
When we have repetitions not allowed and order doesn't matter, we use the Choose formula $C(n,r)$ which yields $C(70,4)$
However this is incorrect, the correct solution states:
The problem is equivalent to finding the total number of solutions to $x1 + x2 + x3 + x4 = 70$ which ends up being $C(73,3)$. Using the formula $C(r+n-1, n-1)$ which correspond to situations in which repetitions ARE allowed, and order doesn't matter. 
What am I missing?
 A: When you do $C(70,4)$, you are selecting 4 out of 70 possibilities. This does not correspond to assigning a runway to each of 70 airplanes (think about it: you are just selecting four of the 70 arriving airplanes... for what?)
Instead, what you need to do is to select a runway, out of 4 possibilities, 70 times (once for each plane), allowing repetition of runways (the same runway may be used by more than one plane), and not caring about the order in which you select them. This is a classic "combination with repetitions problem", also known as a stars and bars problem.
In order to make $r$ selections out of $n$ possible items, allowing unlimited repetitions and where the order of the selections does not matter (only how many times each item is selected), the correct formula is
$$\binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$
which in this case (with $n=4$, the available runways, and $r=70$, the number of times you need to select a runway) yields the provided answer, $\binom{73}{3}$. 
A: The simplest way to look at it is as the hint says, let $x_i$ planes land on the runway $i$ then you are looking for nonnegative integer solutions to $$x_1 + x_2 + x_3 +x_4 =70$$
Which can be seen graphically as the number of ways of traversing a $3\times 70$ grid from one corner to the other making only right and up movements. 

The total number of movemements is $73$ of which 3 have to be up, or equivalently $70$ have to be right, so the total number of ways is $$\binom{73}{3} = \binom{73}{70}$$ Another way is to imagine a two dimensional grid with 70 columns and 3 rows. In this $3\times 70$ grid each row represents a runway and each column represents a plane. So for example a TRUE or $1$ on a lattice point $a_{ij}$ says that plane $j$ landed on the $i$th runway. Each column will contain one TRUE $1$ and three false or $0$ as plane $j$ can land in only one of the $i=4$ four runways. Note that rearranging the rows or the columns would not change these constructions.
If $X$ is the set of all arrays constructed using the above rule, and $P(X)$ is the set obtained by permuting the columns in such a way that all the $1's$ in a row occur together,  then it is easy to see that the mapping $f:S\rightarrow P(S)$ is bijective. The cardinality of $P(S)$ is known from above, it is the number of ways of traversing a grid from one corner to another making only up or right turns in $k-1$ rows and $n$ columns it is $$\binom{n+k-1}{k-1}$$
A: Here is a similar method with generating functions. The number of possibilities is the coefficient of $x^{70}$ in the formal series
$$
(1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots)
$$
since the coefficient is the sum of all possible products of a term from each series whose exponents add to $70$. But the above is
$$
(1+x+x^2+x^3+\cdots)^4=\frac{1}{(1-x)^4}=\sum_{n\geq 0}\binom{n+3}{3}x^n
$$
using the fact that $\sum_{n\geq 0}\binom{n+k}{k}x^n=1/(1-x)^{k+1}$ for generating functions. So the coefficient of $x^{70}$ is $\binom{73}{3}$. 
