Simple combinatorial problem

Question

I am curious about this problem that I came up and tried to solve for myself:

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$.

Answer 1

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.

Answer 2

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}.$$