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 i1…in that are arranged into m pairs.

Let xi be any item in the remaining pool.

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

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

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

…

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

Let (xn-1,xn) be the mth pair. There is only 1 possible mth pair after xn-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

mnnC2PC(m)
1211
2463
361515
4828105
51045945
6126610,395
71491135,135
8161202,027,025
91815334,459,425
1020190654,729,075
112223113,749,310,575
1224276316,234,143,225

PC(m) can also be expressed in the form (2m)! / ( m! 2m ). 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

F1 = 0

F2 = n-1

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

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

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

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

Thus

P(i,j) = Fi + j-i = (i-1)(2n - i)/2 + j-i
12
11
2
pairmutations=1, combos per tournament=1
 1: items=1,2 pairIds=1
0ms
1234
1123
245
36
4
pairmutations=3, combos per tournament=3
 1: items=1,2,3,4 pairIds=1,6
 2: items=1,3,2,4 pairIds=2,5
 3: items=1,4,3,2 pairIds=3,4
0ms
123456
112345
26789
3101112
41314
515
6
pairmutations=15, combos per tournament=5
 1: items=1,2,3,4,5,6 pairIds=1,10,15
 2: items=1,2,3,5,4,6 pairIds=1,11,14
 3: items=1,2,3,6,5,4 pairIds=1,12,13
 4: items=1,3,2,4,5,6 pairIds=2,7,15
 5: items=1,3,2,5,4,6 pairIds=2,8,14
 6: items=1,3,2,6,5,4 pairIds=2,9,13
 7: items=1,4,3,2,5,6 pairIds=3,6,15
 8: items=1,4,3,5,2,6 pairIds=3,11,9
 9: items=1,4,3,6,5,2 pairIds=3,12,8
10: items=1,5,3,4,2,6 pairIds=4,10,9
11: items=1,5,3,2,4,6 pairIds=4,6,14
12: items=1,5,3,6,2,4 pairIds=4,12,7
13: items=1,6,3,4,5,2 pairIds=5,10,8
14: items=1,6,3,5,4,2 pairIds=5,11,7
15: items=1,6,3,2,5,4 pairIds=5,6,13
0ms
12345678
11234567
28910111213
31415161718
419202122
5232425
62627
728
8
pairmutations=105, combos per tournament=7
 1: items=1,2,3,4,5,6,7,8 pairIds=1,14,23,28
 2: items=1,2,3,4,5,7,6,8 pairIds=1,14,24,27
 3: items=1,2,3,4,5,8,7,6 pairIds=1,14,25,26
 4: items=1,2,3,5,4,6,7,8 pairIds=1,15,20,28
 5: items=1,2,3,5,4,7,6,8 pairIds=1,15,21,27
 6: items=1,2,3,5,4,8,7,6 pairIds=1,15,22,26
 7: items=1,2,3,6,5,4,7,8 pairIds=1,16,19,28
 8: items=1,2,3,6,5,7,4,8 pairIds=1,16,24,22
 9: items=1,2,3,6,5,8,7,4 pairIds=1,16,25,21
10: items=1,2,3,7,5,6,4,8 pairIds=1,17,23,22
11: items=1,2,3,7,5,4,6,8 pairIds=1,17,19,27
12: items=1,2,3,7,5,8,4,6 pairIds=1,17,25,20
13: items=1,2,3,8,5,6,7,4 pairIds=1,18,23,21
14: items=1,2,3,8,5,7,6,4 pairIds=1,18,24,20
15: items=1,2,3,8,5,4,7,6 pairIds=1,18,19,26
...
0ms
12345678910
1123456789
21011121314151617
318192021222324
4252627282930
53132333435
636373839
7404142
84344
945
10
pairmutations=945, combos per tournament=9
 1: items=1,2,3,4,5,6,7,8,9,10 pairIds=1,18,31,40,45
 2: items=1,2,3,4,5,6,7,9,8,10 pairIds=1,18,31,41,44
 3: items=1,2,3,4,5,6,7,10,9,8 pairIds=1,18,31,42,43
 4: items=1,2,3,4,5,7,6,8,9,10 pairIds=1,18,32,37,45
 5: items=1,2,3,4,5,7,6,9,8,10 pairIds=1,18,32,38,44
 6: items=1,2,3,4,5,7,6,10,9,8 pairIds=1,18,32,39,43
 7: items=1,2,3,4,5,8,7,6,9,10 pairIds=1,18,33,36,45
 8: items=1,2,3,4,5,8,7,9,6,10 pairIds=1,18,33,41,39
 9: items=1,2,3,4,5,8,7,10,9,6 pairIds=1,18,33,42,38
10: items=1,2,3,4,5,9,7,8,6,10 pairIds=1,18,34,40,39
11: items=1,2,3,4,5,9,7,6,8,10 pairIds=1,18,34,36,44
12: items=1,2,3,4,5,9,7,10,6,8 pairIds=1,18,34,42,37
13: items=1,2,3,4,5,10,7,8,9,6 pairIds=1,18,35,40,38
14: items=1,2,3,4,5,10,7,9,8,6 pairIds=1,18,35,41,37
15: items=1,2,3,4,5,10,7,6,9,8 pairIds=1,18,35,36,43
...
0ms
123456789101112
11234567891011
212131415161718192021
3222324252627282930
43132333435363738
539404142434445
6464748495051
75253545556
857585960
9616263
106465
1166
12
pairmutations=10395, combos per tournament=11
 1: items=1,2,3,4,5,6,7,8,9,10,11,12 pairIds=1,22,39,52,61,66
 2: items=1,2,3,4,5,6,7,8,9,11,10,12 pairIds=1,22,39,52,62,65
 3: items=1,2,3,4,5,6,7,8,9,12,11,10 pairIds=1,22,39,52,63,64
 4: items=1,2,3,4,5,6,7,9,8,10,11,12 pairIds=1,22,39,53,58,66
 5: items=1,2,3,4,5,6,7,9,8,11,10,12 pairIds=1,22,39,53,59,65
 6: items=1,2,3,4,5,6,7,9,8,12,11,10 pairIds=1,22,39,53,60,64
 7: items=1,2,3,4,5,6,7,10,9,8,11,12 pairIds=1,22,39,54,57,66
 8: items=1,2,3,4,5,6,7,10,9,11,8,12 pairIds=1,22,39,54,62,60
 9: items=1,2,3,4,5,6,7,10,9,12,11,8 pairIds=1,22,39,54,63,59
10: items=1,2,3,4,5,6,7,11,9,10,8,12 pairIds=1,22,39,55,61,60
11: items=1,2,3,4,5,6,7,11,9,8,10,12 pairIds=1,22,39,55,57,65
12: items=1,2,3,4,5,6,7,11,9,12,8,10 pairIds=1,22,39,55,63,58
13: items=1,2,3,4,5,6,7,12,9,10,11,8 pairIds=1,22,39,56,61,59
14: items=1,2,3,4,5,6,7,12,9,11,10,8 pairIds=1,22,39,56,62,58
15: items=1,2,3,4,5,6,7,12,9,8,11,10 pairIds=1,22,39,56,57,64
...
4ms