# All possible tournament pairing such that you get no pair from the same group.

I thought about this problem for a while, but I have no idea how to approach it.

You have 8 groups, with 4 of the groups having 6 people and rest of the 4 groups having 3 people. So you have 36 people in total.

Now we want to pick 18 pairs from 36 people to form a tournament.

I believe there are $$\frac{36!}{18! 2^{18}}$$(I don't really understand how to get this number though) as can be seen here: Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Now, I want pairings to be such that no people from the same group play against each other. How many possible pairings exist under this constraint?

This is a very similar question: UEFA Champions League quarterfinals 2018 draw - pairing of same country teams

However, I don't think the approach there would work.

Thanks!

EDIT: The most general form of this question would be to let the number of groups and number of people in each group vary, and to find the formula for this. I am now wondering if such a formula exists. So for example, what if you have 11 groups, and 4 of them have 5 people, 5 of them have 4 people, and 2 of them have 12 people.

EDIT:

I ran some simulation, I keep getting about 0.11 instead of Henry's 0.245. Here is my code.

team_list = c(rep(1:6, 4), rep(1:3,4))

for (i in 1:6){
team_list[i] = paste("A", team_list[i], sep = "")
}

for (i in 7:12){
team_list[i] = paste("B", team_list[i], sep = "")
}

for (i in 13:18){
team_list[i] = paste("C", team_list[i], sep = "")
}

for (i in 19:24){
team_list[i] = paste("D", team_list[i], sep = "")
}

for (i in 25:27){
team_list[i] = paste("E", team_list[i], sep = "")
}

for (i in 28:30){
team_list[i] = paste("F", team_list[i], sep = "")
}

for (i in 31:33){
team_list[i] = paste("G", team_list[i], sep = "")
}

for (i in 34:36){
team_list[i] = paste("H", team_list[i], sep = "")
}

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0

for (i in 1:10000){
x = sample(team_list, size = 36)
if (!check_pair(x)){
count = count+1
}
}

count/10000

team_list = c("A1", "A2", "B1", "B2", "C1", "C2")

pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}

pair_combn(team_list)

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0

for (i in 1:10000){
x = sample(team_list, size = 6)
if (!check_pair(x)){
count = count+1
}
}

count/10000

team_list = c("A1", "A2", "B1", "B2", "C1", "D1")

pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}

pair_combn(team_list)

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0

for (i in 1:10000){
x = sample(team_list, size = 6)
if (!check_pair(x)){
count = count+1
}
}

count/10000

z = pair_combn(team_list)

team_list = c("A1", "A2", "B1", "B2", "C1", "D1", "E1", "E2")

pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}

print (count)

count = 0

for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}

count/10000

team_list = c("A1", "A2", "A3", "A4", "B1", "B2", "C1", "C2")

pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}

print (count)

count = 0

for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}

count/10000

team_list = c("A1", "A2", "A3", "B1", "B2", "B3", "C1", "C2")

pair_combn <- function(x) {
Filter(function(e) all(unique(x) %in% unlist(e)),
combn(as.data.frame(combn(x, 2)),
length(x)/2, simplify = FALSE))
}

combination = pair_combn(team_list)

check_pair = function(x){
for (i in seq(from = 1, to = length(x), by = 2)){
if (substr(x[i],1,1) == substr(x[i+1],1,1)){
return (TRUE)
}
}
return (FALSE)
}

count = 0
for (i in 1:105){
to_check = as.vector(unlist(combination[[i]]))
if (!check_pair(to_check)){
count = count+1
}
}

print (count)

count = 0

for (i in 1:10000){
x = sample(team_list, size = 8)
if (!check_pair(x)){
count = count+1
}
}

count/10000



And some results I get:

For 3 group of 4 people, 2 people, and 2 people, I get 24 out of 105

For 3 group of 3 people, 3 people and 2 people, I get 36 out of 105

For 5 group of 2 people, 2 people, 2 people, 1 person and 1 person, I get 68 out of 105.

• Your $\frac{36!}{18! 2^{18}}$ is just a way of writing $35 \times 33 \times \cdots \times 3 \times 1$ which might be seen to be "the first in the alphabet plays any of the other $35$, then the next unpaired in the alphabet plays any of the other $33$ unpaired, etc." Jan 3, 2021 at 2:03
• @Henry That makes sense, thanks!
– Phil
Jan 3, 2021 at 2:15
• Simulation suggests that the number meeting your constraint may be something like around $0.244$ or $0.245$ times the original number Jan 3, 2021 at 2:25
• @Henry, good to know thanks! I might run a few simulation with different numbers to see some pattern.
– Phil
Jan 3, 2021 at 2:26

The number is 24855678464505984000.

Suppose we have $$k$$ different groups, of sizes $$N_1, N_2 ... N_k$$. Define $$F(N_1, N_2, ... N_k)$$ to be the number of possible tournaments. So the answer to your particular problem is $$F(3, 3, 3, 3, 6, 6, 6, 6)$$.

How to compute $$F$$? We can come up with a recurrence relation, and hopefully a computer should be compute it. Here's the recurrence relation:

$$F(N_1...N_k) = \frac{2}{\sum_l N_l}\sum_i\sum_{j < i} N_j \times N_i \times F(N_1, N_2\dots N_j-1 \dots N_i-1 \dots N_k)$$

The idea is that we choose a pair (from different groups), then figure out the subproblem with that pair removed. The factor $$2 / \sum_l N_l$$ comes from the fact that we can choose any of the pairs to be the first one, which would lead to over-counting without dividing by the number of pairs.

For the base cases, we have $$F(0, 0, \dots 0) = 1$$, and $$F=0$$ if any of its arguments are 0.

I used the following code, which takes about a minute to run.

from functools import lru_cache

@lru_cache(maxsize = 1000000)
def F(M, ntup, k):
if M < 0: return 0
for n in ntup:
if n < 0: return 0
if M == 0:
return 1
ans = 0
for i in range(1, k):
for j in range(0, i):
ans += ntup[i] * ntup[j] * F(M-2, ntup[:j] + (ntup[j]-1,) + ntup[j+1:i] + (ntup[i]-1,) + (ntup[i+1:] if i+1 < k else ()), k)
return (2 * ans) // M

print(F(36, (3, 3, 3, 3, 6, 6, 6, 6), 8))


This prints 24855678464505984000. That means the probability of finding a successful tournament (meaning no pairs from the same group) by randomly sampling from all possible pairings is about 0.11, as expected.

• Oh my god,thanks so much!
– Phil
Jan 5, 2021 at 16:55