1
$\begingroup$

Since some days, I'm trying to simplify a recursive and long algorithm into a fast (non recursive) equation taking 3 parameters into account.

I want to precise that I don't know really how to specify my problem in one question (I don't know well mathematical combinatorials vocabulary). I will try to be as much understandable as possible. Please let me know if I use wrong vocabulary or if something I said can be simplified using mathematics vocab.

So, my question can be explained with the following problem for example:

There is a game that can be played from 2 to an infinite number of teams.
Each team should be composed by the same number of players.
A player cannot be in 2 different teams during one game at the time.

There is a certain amount of players (lets say P).
I want to find the equation f(P,T,S)=y as y is the number of different games rounds we can make, specifying the number of teams who will play (T) against each others, and the number of players by team (S for team Sizes).

For example, let say there are P=5 players. If I want the numbers of combinations as there is T=2 teams of S=2 players, the equation should be f(P=5,T=2,S=2)=15 as we can do the following combinations:

{{1,2},{3,4}}, {{1,2},{3,5}}, {{1,2},{4,5}}
{{1,3},{2,4}}, {{1,3},{2,5}}, {{1,3},{4,5}}
{{1,4},{2,3}}, {{1,4},{2,5}}, {{1,4},{3,5}}
{{1,5},{2,3}}, {{1,5},{2,4}}, {{1,5},{3,4}}
{{2,3},{4,5}}, {{2,4},{3,5}}, {{2,5},{3,4}}

(Maybe I've the wrong notations, so note that {1,2} and {2,1} are representing the same subset (same "Team" for the example problem), and that {{1,2},{3,4}} and {{3,4},{1,2}} are representing the same set (the same "game round"))

Following, some results I expect (hand made calculation)
expected


I found some partial equations for now:

With S=1 fixed, I've found that: $f(P,T,1)={P \choose T}=\frac{P!}{T!(P-T)!}$

With T=1 fixed, I've found that: $f(P,1,S)={P \choose S}=\frac{P!}{S!(P-S)!}$

With T=2 and S=2, I've found that: $f(P,2,2)={{P \choose 2} \choose 2}=\frac{P!}{8((P-4)!)}$ (Tri-triangular numbers)

I'm pretty sure there is a function that gather these 3 I've found into only one, taking P, T and S as a variable. But I have difficulties to find it.

Thank you for any help, if you need more information please ask for !

$\endgroup$
  • $\begingroup$ This is studied as part of combinatorial design theory, sometimes under a name like tournament scheduling or team assignment. I would start with the Handbook of Combinatorial Designs and see what references they recommend. In my opinion, in general f is unknown, and provable bounds are weak. Gerhard "Is Mathematics A Team Sport?" Paseman, 2018.01.08. $\endgroup$ – Gerhard Paseman Jan 8 '18 at 17:45
2
$\begingroup$

Picking $S$ players from $P$ for the first team, we have $${P \choose S} = \frac{P!}{S!(P-S)!}$$ choices. We are left with $P-S$ players to pick from for the second team, so for a total of $T$ teams, we would have $$\prod_{i=0}^{T-1} {P-iS \choose S}$$ choices, assuming of course that $ST \leq P$. But now we count a little bit too much, in your example we would count $\{\{1,2\},\{3,4\}\}$ twice, once as $\{1,2\},\{3,4\}$ and once as $\{3,4\},\{1,2\}$. If we have $T$ teams, there are $T!$ ways to order them, we count them all but only want one. Therefore, the final formula is $$\frac{\prod_{i=0}^{T-1} {P-iS \choose S}}{T!} = \prod_{j = 1}^T \frac{(P-jS+S)!}{S!(P-jS)!j} = \ldots.$$

I am sure you can simplify this further if needed.

$\endgroup$
  • $\begingroup$ Thank you ! for information, I could reduce this into the following: $ f(P,T,S)= \frac{P!}{T! S!^T (P-TS)!} $, and after test, it seems to work well ! $\endgroup$ – NatNgs Jan 8 '18 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.