# Counting distinct sets of pairwise distances for some number of passengers loaded onto different cars of a ferris wheel

We load three different passengers - A, B, and C - onto a ferris wheel with $M$ cars symmetrically distributed around the wheel. Let d(AB), d(AC), and d(BC) represent the number of cars between all possible sets of two passengers going clockwise around the ferris wheel. If no two passengers are loaded in the same car, how many distinct sets, $S$, of these three pairwise distances (d(AB), d(AC), d(BC)) are possible? How does this generalize as the number of passengers loaded in distinct cars increases to $M$?

To clarify, each passenger is distinct/labeled, and the set of all possible pairwise distances should form an ordered list. For example, (d(AB), d(AC), d(BC)) = (2,3,4) would be counted as distinct from (d(AB), d(AC), d(BC)) = (3,2,4). If one filled the ferris wheel with $(M - 1)$ passengers, there would therefore be $S = M$ possible sets of these pairwise distances.

Correct me if I'm wrong, but I believe this is equivalent to asking for the number, $S$, of possible ordered lists of $N$ zero or positive integers for some $N < M$ s.t. their sum is equal to $(M - N)$.

Results of brute force calculations:

For $N$ = 3 and $M$ = 3 to 10, a brute force calculation shows that the number of such distinct ordered lists, $S$, increases as {1,3,6,10,15,21,28,36}, which fits the relation: $S = \frac{1}{2}(M-2)(M-1)$, or $S = \frac{1}{2}\frac{(M-1)!}{(M-N)!}$. This relation holds when $M = 100$ and $S = 4851$.

For $N$ = 4 and $M$ = 4 to 10, a brute force calculation shows that the number of such distinct ordered lists, $S$, increases as {1,4,10,20,35,56,84}, which fits the relation: $S = \frac{1}{6}(M-3)(M-2)(M-1)$, or $S = \frac{1}{6}\frac{(M-1)!}{(M-N)!}$. This relation holds when $M = 20$ and $S = 969$.

For $N$ = 5 and $M$ = 5 to 10, a brute force calculation shows that the number of such distinct ordered lists, $S$, increases as {1,5,15,35,70,126}, which fits the relation: $S = \frac{1}{24}(M-3)(M-2)(M-1)$, or $S = \frac{1}{24}\frac{(M-1)!}{(M-N)!}$.

For $N$ = 6 and $M$ = 6 to 10, we have $S$ increasing as {1,6,21,56,126}, which fits the relation $S = \frac{1}{120}\frac{(M-1)!}{(M-N)!}$.

From these results, one might guess that $S = C*\frac{(M-1)!}{(M-N)!}$, where $C$ is some fractional coefficient. Using the predicted coefficients for $N = {3,4,5,6}$, which are {$\frac{1}{2}$,$\frac{1}{6}$,$\frac{1}{24}$,$\frac{1}{120}$}, I'd say that $C = \frac{1}{(N-1)!}$, which gives us a solution of:

$S = \frac{1}{(N-1)!}\frac{(M-1)!}{(M-N)!}$

Is this true?

-
You're asking for the number of partitions of $M$ into 3 parts. You can use that phrase for a websearch. I'm pretty sure the question has been asked and answered on this website. –  Gerry Myerson Jan 25 '12 at 12:30
@Gerry Myerson, the answer should be greater than the number of integer partitions of the cars without passengers, no? I'm asking for the count of all sets of possible pairwise distances between distinct/labeled passengers. –  Tess Jan 25 '12 at 12:37
I missed that $(2,3,4)$ and $(3,2,4)$ count as different. So then it's the number of solutions in positive integers of $x+y+z=M$, which has also come up on this website more than once. –  Gerry Myerson Jan 25 '12 at 23:01

Your numerical data don’t agree with your statement of the problem, though they’re related. I’ll solve the problem as you stated it and show what related problem your numerical data solve.

Let the riders be $A_0,A_1,\dots,A_{N-1}$. Number the cars clockwise from $0$ through $M-1$, with $A_0$ occupying Car $0$. If $A_k$ occupies car $c_k$, the distance from $A_0$ to $A_k$ is $c_k$. Thus, the relative placements of all of the riders are completely determined by the list $\langle c_1,\dots,c_{N-1}\rangle$ of distances from $A_0$, and the other distances between riders can be inferred from these, since $M$ is known. The number of distinct ordered lists of distances is therefore equal to the number of lists of the form $\langle c_1,\dots,c_{N-1}\rangle$, where $c_k$ is the distance from $A_0$ to $A_k$. This is simply the number of $(N-1)$-tuples of distinct integers from the set $\{1,2,\dots,M-1\}$, which is $$(M-1)(M-2)\cdots(M-N+1)=\frac{(M-1)!}{(M-N)!}\;:$$ there are $M-1$ possible locations for $A_1$, after which $A_2$ can occupy any of the $M-2$ remaining cars, and so on.

For $M=N=3$, for instance, there are $(3-1)(3-2)=2$ possible lists, $\langle 1,2\rangle$ and $\langle 2,1\rangle$, depending on whether the clockwise seating order is $A_0,A_1,A_2$ or $A_0,A_2,A_1$. Similarly, for $N=3$ and $M=4$ there are $6$ possible lists, not $3$: $\langle 1,2\rangle,\langle 2,1\rangle,\langle 1,3\rangle,\langle 3,1\rangle,\langle 2,3\rangle$, and $\langle 3,2\rangle$.

Suppose, now, that you don’t care about the identities of the riders other that $A_0$. That is, you’re interested just in the set of inter-rider distances, not in which distance goes with which pair of riders. Then all you need to know is which set of $N-1$ cars are occupied by riders $A_1$ through $A_{N-1}$: you need to know the set $\{c_1,\dots,c_{N-1}\}$ of numbers, but not the order in which its members are associated with riders $A_1$ through $A_{N-1}$. You can still infer from this set what all of the other inter-rider distances are; you just don’t know which distance goes with which pair of riders. For this problem you’re counting the $(N-1)$-element subsets of the $(M-1)$-element set $\{1,\dots,M-1\}$, a number which is given by the binomial coefficient

$$\binom{M-1}{N-1}=\frac{(M-1)!}{(N-1)!(M-N)!}\;.$$

This expression gives the numbers from your brute force calculations.

The relationship between the two counts is straightforward: each set of $N-1$ car numbers can be arranged in an ordered list in $(N-1)!$ ways, so the number of lists must be $(N-1)!$ times the number of unordered sets, and indeed

$$\frac{(M-1)!}{(M-N)!}=(N-1)!\binom{M-1}{N-1}\;.$$

-