Pairmute

Richard A. DeVenezia. 15MAR2004

Enumerating all possible rounds that can be considered for combination into a tournament (thanks to James Parmenter).

Consider n = 2m and items i₁…i_n that are arranged into m pairs.

Let x_i be any item in the remaining pool.

Let (x₁,x₂) be the first pair. There are n-1 possible first pairs after x₁ has been selected. The remaining pool has n-2 items in it.

Let (x₃,x₄) be the second pair. There are n-3 possible second pairs after x₃ has been selected. The remaining pool has n-4 items in it.

Let (x₅,x₆) be the third pair. There are n-5 possible third pairs after x₅ has been selected. The remaining pool has n-6 items in it.

…

Let (x_n-3,x_n-2) be the (m-1)^st pair. There are 3 possible (m-1)^st pairs after x_n-3 has been selected. The remaining pool has 2 items in it.

Let (x_n-1,x_n) be the m^th pair. There is only 1 possible m^th pair after x_n-1 has been selected. The remaining pool has no items in it.

So the number of possible pairwise combinations is the product (n-1)(n-3)(n-5)…(5)(3)(1).

PC(m) = ∏ (2m-2i+1); i = 1…m -or- ∏ (2i-1); i = 1…m

PC(m) can also be expressed in the form (2m)! / ( m! 2^m ). This form is found by noticing that PC(m) is n! with every even (there are m of them) factor removed.

Consider upper triangular matrix P(i,j); i<j; i=1…n-1, j=i+1…n containing the enumeration 1…m × (n-1).

Each (i,j) is a pairing between i and j.

P(0,j) = 0

P(i,j) = P(i-1,n) + j - i

Sequence F = P(i-1,n); i=1…n-1 enumerates the values in the rightmost column

F₁ = 0

F₂ = n-1

F_i = ∑ (n-k); k=1…i-1

F_i = ∑ n - ∑ k; k=1…i-1

F_i = (i-1)n - (i-1)i/2

F_i = (i-1)(2n - i)/2

Thus

P(i,j) = F_i + j-i = (i-1)(2n - i)/2 + j-i