# Simple combinatorial problem

The settings is an $$2k$$ player game. It's a team game of $$2$$ teams. Each team has $$k$$ player slots. Each of the players chooses to play exactly one of $$m$$ factions.

The question is: How many unique possible team vs team match-ups are there (uniqueness in terms of which factions play against which factions, not in terms of which players play against each other)?

(Edit: Multiple players may choose the same faction. E.g. let's say there are 4 factions F1, F2, F3, F4, then ((F1, F1, F2) vs. (F1, F2, F4)) is a possible 3v3 match-up. Also, by uniqueness I mean that the order of players in a team does not matter, and the order of teams does not matter. E.g. ((F1, F2) vs. (F2, F4)) is the same 2v2 match-up as ((F2, F1) vs. (F2, F4)) and (F2, F4) vs. ((F1, F2)) )

I've tried two derivations:

My first answer (it must be wrong because for $$k = 4, m=4$$ I don't get an integer solution): $$\frac{m^k} {k!} \cdot \frac{m^k} {k!} / 2$$ because for each team, we can select $$m^k$$ combinations of factions, before accounting for possible permutations of players inside the team, by dividing by $$k!$$. Finally, divide by $$2$$ because the order of the teams does also not matter.

My second answer (also wrong for the same reason): $$\frac{m^{2k}}{ \binom {2k}{k}}$$ because there are $$m^{2k}$$ possibilities for fixed players picking factions, and in the second step we then select $$k$$ players for the first team, so divide by all possible ways to pick $$k$$ players out of $$2k$$, i.e. divide by $$\binom {2k}{k}$$.

Both answers are wrong because for $$k = 4, m=4$$ I get non-integer answers:

First answer fails: \begin{align} & \frac{4^4} {4!} \cdot \frac{4^4} {4!} / 2 &= \frac{4^3} {3!} \cdot \frac{4^3} {3!} / 2 &= \frac{64} {6} \cdot \frac{64} {6} / 2 &\approx 56.88 \end{align}

second answer fails: \begin{align} & \frac{4^{2 \cdot 4}}{ \binom {2 \cdot 4}{4}} &= \frac{4^8}{ \binom {8}{4}} &\approx 936.22 \end{align}

I'm confused where my assumptions/formulas are wrong.

It would also be interesting to see a more general answer for $$t$$ teams instead of only $$2$$.

• You need to clarify how the fractions are picked. Is it possible to pick the same fraction twice? Commented May 23 at 19:21
• @Vasili I agree that that your comment indicates an ambiguity in the question. Judging by the analysis in the posted question, which included the expression $~k^m,~$ I inferred (in my answer, perhaps wrongly) that each of the $~2k~$ players is selecting some fraction at random, sampling the fractions with replacement. Commented May 23 at 19:57

There are $$2k$$ players, each of which are assigned to a team of $$k$$ players. That can be done in $$\binom{2k}{k}$$ ways. Now, each player belongs to one of $$m$$ factions, so for each possible team assignment, each player can be part of one of $$m$$ (possibly empty) factions, meaning we multiply $$\cdot m^{2k}$$.

So, with overcounting, we have $$\binom{2k}{k} (2k)^m$$. However, now you need to decide what makes a situation unique. Are two team situations the same if there exists a relabeling of the players where all of the faction and team differences are held? Are two team situations the same if you can relabel the factions? Clearly the "true" answer is simply taking this overcounting example, and then making sure to account for what you consider to be a duplicate.

Since you didn't specify, I will assume that everything is unique. So the factions and people are "set", so that if you had two people, assigning person 1 to team 1 and person 2 to team 2 would be DIFFERENT than assigning person 1 to team 2 and person 2 to team 1, even though the structure that they are on different teams is held. This is natural when you have labels for the factions that serve particular roles.

I will leave you to decide what you want to divide out, whether you want to relabel factions, teams - what actually matters is defining WHAT specifically is unique and then simply counting all of those possibilities. Without specifying that, the answer is simply the "overcount" answer I wrote above.

• Sorry, I see now that my question was ill-posed and have tried to refine it now. Commented May 23 at 19:56
• I'd recommend modifying the question to specify all the restrictions and all the processes for choosing and uniqueness in your question. Then I can modify the answer to appropriately count the situation you fully describe. Otherwise the answer depends on choices, and so any proof would need to do a branching case - which you must eliminate all of those (up to the only 'natural' choice remaining) by the way your situation is posed in the question. Be as specific as to only leave 1 possible interpretation of the situation to count, and you can edit the original question even if it obsoletes an Commented May 23 at 20:42

This answer is a response to the question in its original format. After reading this answer, the original poster changed the question. See my comments, to the original poster, following this answer.

The settings is an $$2k$$ player game. It's a team game of $$2$$ teams. Each team has $$k$$ players. Each of the players chooses between $$m$$ fractions.

The question is: How many unique possible match-ups are there (in terms of which fractions play against which fractions)?

First of all, the question might be construed to be ambiguous. For example, assume that $$~k = 2,~$$ and that the players on team-1 are designated as Player-1.1, Player-1.2, and the players on team-2 are designated as Player-2.1, Player-2.2.

The natural way of reading the question is that if Player-1.1 plays first, and then Player-1.2 plays second,

that the matchup of [Player-1.1:Player-2.1] followed by the matchup of [Player-1.2:Player-2.2]

is to be regarded as identical to

the matchup of [Player-1.2:Player-2.2] followed by the matchup of [Player-1.1:Player-2.2].

That is, under this interpretation of the problem, the order that the matchups occur is irrelevant.

I will assume that this (natural) interpretation is intended by the problem composer during the first part of my answer. At the end of my answer, I will explore the alternative interpretation that the order of the matchups is relevant.

Line up the first team in the order Player-1.1, Player-1.2, ... Player 1.k.

To determine how many ways that the matchups can occur, consider that there are $$~k!~$$ ways that the players on team-2 can be ordered.

So, reserve the factor of $$~k!~$$ and then assume, without loss of generality, that the matchups are

[Player-1.1:Player-2.1], [Player-1.2:Player-2.2], ..., [Player-1.k:Player-2.k].

So, you now have $$~k~$$ distinct matchups, and the question is: In how many distinct ways can each matchup occur?

Examine the number of ways that the matchup of [Player-1.1:Player-2.1] can occur.

Judging by the analysis given in your posted question, each player chooses among $$~m~$$ fractions, sampling with replacement. This signifies (for example) that it is theoretically possible (but unlikely) that all $$~2k~$$ players choose the same fraction.

So, in the matchup of [player-1.1:player-2.1], each of the players has $$~m~$$ choices for which fraction they will select.

Therefore, the number of ways that the [player-1.1:player-2.1] matchup can occur is $$~m^2.~$$

Further, since each of the $$~2k~$$ players is (presumably) choosing a fraction, with replacement, the number of ways that each of the matchups of

[Player-1.1:Player-2.1], [Player-1.2:Player-2.2], ..., [Player-1.k:Player-2.k]

can occur is $$~m^2~$$ for each matchup.

This implies that the total number of ways that all of the matchups of

[Player-1.1:Player-2.1], [Player-1.2:Player-2.2], ..., [Player-1.k:Player-2.k]

can occur is $$~\displaystyle \left( ~m^2 ~\right)^k = m^{2k}.$$

Therefore, the final answer for the natural interpretation of the problem is

$$k! \times m^{2k}.$$

$$\underline{\text{Adddendum}}$$

Exploring the alternate interpretation that the order that the matchups occur is to be regarded as relevant.

In the first part of the answer, it was computed that with the team-1 players lined up in the order of

Player-1.1, Player-1.2, ..., Player-1.k, that the number of different matchups possible was

$$k! \times m^{2k}.$$

In the Addendum, the only significance of the alternate interpretation of the problem is that there are $$~k!~$$ ways that the players in team-1 can be lined up, with the idea that the order that they are lined up determines the order in which they play.

Therefore, the only adjustment needed in the Addendum is to include the extra factor of $$~k!.$$

Therefore, within the Addendum, the computation is

$$(k!)^2 \times m^{2k}.$$

• $m^2$? Why would two players of the same faction fight against each other? The question is ill posed and until it's further refined I don't think a formula can possibly answer it Commented May 23 at 19:52
• @Snared : Two players with the same fraction might well fight against each other, if none of the players on team-1 have any idea of which fractions will be chosen by any of the players on team-2, and vice versa. The way that I read the question, this is a reasonable interpretation, and is consistent with the idea that each player is selecting a fraction, with replacement. See also the comment that I left, following the posted question. Commented May 23 at 19:55
• Thanks for the answer, I have reformulated my question. I think you misunderstood me: The teams play against each other not in a 1v1 way, but in a team vs team way (see my example in the edited question formulation). Commented May 23 at 20:05
• @Krampfmeister Please revert your posted question back to its original version. Otherwise, given that you have made major changes/clarifications to better reveal your intent, you are discourteously imposing the shooting gallery blues on the MathSE reviewer(s), forcing them to alter their answer in order to hit a moving target. Given your actual intent, please (instead, after you have reverted the question), post a new question, on a separate webpage. ...see next comment Commented May 23 at 20:10
• @Krampfmeister Then, you might include double cross-references, where each of the two posted questions contains a link to the other posted question, as a reference. Because it is unreasonable to ask a reviewer to hit a moving target, I am going to leave my answer as is, with a note that you changed the question after I answered it. Commented May 23 at 20:12