How many permutations/combinations?

[Foxer]

I'm trying to write a small app (I hope it will be small!) for a tennis tournament.

We play doubles (2 vs 2) and there are 6 players.

The thing is, the teams are not constant. We change partners so every week we play with and against different people so that whilst we play with the same person more than once, we don't want to play against the same team more than once.



Here are some examples :-

Week 1

Bob & Harry vs Jane & Claire
Bob & Harry vs Jane & Susie

Week 2

Bob & Jane vs Claire & Debbie
Bob & Susie vs Claire & Jane

You can see that there are 6 players but no fixed teams. Its a social thing so everyone wants to play with and against everyone else.

How many total matches would we need and how do I code that in MS Access or MS Excel (I'm a proficient coder at both )

[Harsh Gupta]

Start with 1 person, say Bob. He can pair up with 5 other people. Let's take Harry. Now we are left with 4 other persons. We can form 6 doubles of these 4 persons.
⁴C₂ = 6 (this eliminates doubling, it means Jane & Claire = Claire & Jane)

Bob & Harry together will play 6 matches together against other 4.Similarly,
Bob & Jane together will play 6 matches together against other 4.
Bob & Claire together will play 6 matches together against other 4.
Bob & Susie together will play 6 matches together against other 4.
Bob & Debbie together will play 6 matches together against other 4.

So, total matches played by Bob = 6*5 = 30.

Next take Harry. He can pair up with other 5, and so he will play 30 matches! But wait, we are counting Harry and Bob again, which we have already counted in previous case of Bob and Harry. So deduce those 6 matches from the total of 30. So total matches played by Harry = 30 - 6 = 24.

Considering 3rd person, we need to eliminate pairing up of this and Bob and this and Harry (you guess it right, as we have already considered previously), so we need to eliminate 6+6 matches from total of 30. So total matches palyed by 3rd person is = 30 - (6+6) = 18.

4th person = 30 - (6+6+6) = 12

5th person = 30 - (6+6+6+6) = 6

6th person = 30 - (6+6+6+6+6) = 0, since last person has already paired up with other 5 persons.

Adding them, 30+24+18+12+6+0 = 90.

Total number of matches played = 90.

Alternatively, simple formula would be:
⁶C₂ * ⁴C₂ = 90.

Hoping it to be correct answer.

[Milk]

I got the same answer with different working... 6 players, 15 possible teams, 6 possible games with each team = 15 * 6 = 90 possible games.

[jemidiah]

First pick a team for side 1 by choosing 2 of 6 people. This can be done in 6 choose 2 ways. Next pick a team for side 2 by choosing 2 of the remaining 4 people. This can be done in 6 choose 4 ways, giving rise to Gupta's simple formula. However, this should double count everything, since it counts "Team A playing Team B" as different from "Team B playing Team A". Thus the answer is 6C2*4C2 / 2 = 15*6/2 = 45.

I tried out a size 4 tournament using the previous reasoning and saw it double counts as expected. There are only 6 different teams in a size 4 group, and when the first team has been picked the second is decided automatically. Then you can have Team 1 play Team 2, Team 2 play team 1, Team 3 play Team 4, Team 4 play Team 3, Team 5 play Team 6, and Team 6 play Team 5, resulting in only 3 unique games while 4C2 * 2C2 = 6.


As for coding this generally, the number of ways to choose a group of size k out of a pool of size n is defined as "n choose k" or ⁿC_k as Gupta used. Functionally, it turns out n choose k = n! / [k! * (n-k)!] using factorials.

If you want to count the number of ways to make something, one way to do that is to make up an algorithm that will generate your end product. At each step in the algorithm, count the number of different choices you can have--how many branches you have to choose from. Since the final branch in the web of decisions always results in your end product, you just have to count the number of branches you'll end up with. To do that, just multiply the number of choices you have at each step. The above example follows this pattern.

I won't give the general functional form for a tournament of n players but you should easy be able to figure it out.


Also Milk, you're basically using a combinatorial argument (the same one behind Gupta's formula, and the same one at the start of this post) but not accounting for the double counting. That's cool You seem to have a talent for it

[Foxer]

Hmmm... thanks heaps. Gets me in the right direction.

As for coding it I was getting messed up on Bobby & Harry = Harry & Bobby producing wrong results. I need to adjust my "available pool" to stop this.

[jemidiah]

Assuming no two players have the same name, add this condition: the first player on each team must have a name that comes before the second player's name, alphabetically. That automatically removes Harry & Bobby from the list, leaving only Bobby & Harry.

To remove the similar possibility of Bobby & Harry playing Alice & Jane being the same as Alice & Jane playing Bobby & Harry, add another arbitrary constraint that only allows one pairing through. You could require the first player on the first team to have a name that comes before the first player on the second team's name.


Adding these conditions to whatever you're using to generate matches should cull out the duplicates, and alphabetize the final list nicely

I'm happy at how clever that turned out, hehe, my ideas usually aren't clever.