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

-
Wouldn't repetitions be represented by multiple planes on a single runway? – Jack Henahan Jun 15 '11 at 18:29
But I thought "Multiple planes on a single runway" means repetitions are not allowed - since it's Multiple planes, but different planes. I thought repetition would mean the same plane again and again – Arvin Jun 15 '11 at 18:48

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

-
I see, the way I was thinking of it was.. You have to choose 4 planes to assign to each runway, in other words assigning a plane onto a runway, rather than a runway to each plane. I see how the solution works, it's the recognising of repetitions allowed/not allowed and order matters/doesn't matter that confuses me – Arvin Jun 15 '11 at 18:46
@Arvin: But even if you think about assigning planes to runways, it doesn't make sense to just choose 4 planes. Why 4 planes, and only 4 planes? Every plane needs to be assigned to some runway, after all, and you are only selecting 4, leaving 66 planes unassigned. If you want to assign planes to runways instead of runways to planes, you need to count ordered partitions of 70, which is harder to think about. Basically, this problem amounts to the same as distributing a bunch of identical balls in 4 buckets (each ball representing a plane, each bucket a runway). – Arturo Magidin Jun 15 '11 at 18:49
Ahhh I see, that makes sense now! I was thinking of it in terms of.. you choose 4 planes, that's 1 way. then you choose another 4 planes, that's another way. That's totally wrong, Thanks! – Arvin Jun 15 '11 at 18:53
@Arvin: Glad I could help. – Arturo Magidin Jun 15 '11 at 18:56

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

-

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

-
Imagining stars and bars as grid traversal gives the formula a lot more sense. Thanks! – Michael Chen Jun 15 '11 at 23:55