For a illustrative example:
22 people are being sorted into 12 teams. 12 colored balls are placed in a hat. Each player draws a ball from the hat (with replacement) to figure out which team they are on. When the 3 largest teams are counted (random selection among ties for 3rd), the total of these teams is 11 or higher. What are the chances that this is the case?
Here's what I've gotten so far.
I've established that the maximum number of configurations for the teams is (33 choose 11). I know that I need to select for the largest 3 which can be chosen in (13 choose 2) ways. I'm unsure how to check if the largest 3 teams have 11 or more players.
This problem actually relates to a non-mathematical query I had regarding 12 possible outcomes selected by a sample of 22 persons. I have only foundational mathematical knowledge.
Source of the question:
In Dungeons and Dragons, there are 12 classes players can select. While the chance a player selects them is obviously not random in the real world, a chatizen friend of mine was contemplating a combinatorics question regarding a specific outcome of one of the games he is running. In particular, 11 of the first 22 applicants chose the same 3 classes (Wizard, Fighter, and Paladin). Then, after more applications came in (checking later on during the conversation), 50% of the 28 applications were still these 3. So we wanted a more generalized approach, prompting a question here. This conversation was in a StackExchange chat room, a bookmark of which can be found here.
Counting problems of this kind can be difficult. An exact count can be had by modelling the team selections as a Markov chain/state transitions.
Each of 22 players gets assigned a "color" randomly assigned from the twelve possibilities. If the outcomes are considered to be assignments of 22 players to twelve teams, there will be $12^{22}$ possibilities.
How many of these satisfy the condition that in the end at least eleven players belong to not more than three of the teams? Or on the contrary, how many outcomes do not have more than ten players combined among three teams?
Counting all $12^{22}$ outcomes would be time-consuming:
$$ 12^{22} \approx 10^{23.74} $$
But there is a way to trim down the outcome space to just the integer partitions of $n\le 22$ into at most twelve parts. As the tabulation below shows, this is a much more manageable number of outcomes to track:
$$ \begin{array}{|c|c|c|c|} \hline n & p_{\le 12}(n) & n & p_{\le 12}(n) \\ \hline 1 & 1 & 12 & 77 \\ 2 & 2 & 13 & 100 \\ 3 & 3 & 14 & 133 \\ 4 & 5 & 15 & 172 \\ 5 & 7 & 16 & 224 \\ 6 & 11 & 17 & 285 \\ 7 & 15 & 18 & 366 \\ 8 & 22 & 19 & 460 \\ 9 & 30 & 20 & 582 \\ 10 & 42 & 21 & 725 \\ 11 & 56 & 22 & 905 \\ \hline \end{array} $$
Table 1. Integer partitions $p_{\le 12}(n)$ of $n$ with at most $12$ parts
However not all partitions of this kind are equally likely. The bookkeeping will need to keep track of non-uniform probabilities for the $905$ outcomes. This is enough state information to tell us when some combination of three teams has eleven or more players.
I did a bit of Prolog coding to get the probability values as floating point approximations, and the result is about $0.488104643$.
Here is a sketch of the probability state transition process. We identify the states with counts adding to $n=1,\ldots,22$ (partitions with at most twelve parts of $n$), starting with the one state for $n=1$ where:
$$ 1 = 1+0+0+0+0+0+0+0+0+0+0+0 $$
This "initial" state is reached with probability $1.0$ after the first colored ball is chosen, although the underlying color choice is not shown (and could be any one of the twelve colors).
Next the second ball is drawn, giving two possible states (partitions of $2$ with at most twelve parts). The probabilities of the two states are unequal at this second stage, because it is more likely a different color will be drawn than it is the same color:
$$ 2 = 2+0+0+0+0+0+0+0+0+0+0+0 $$
$$ 2 = 1+1+0+0+0+0+0+0+0+0+0+0 $$
Thus these states have respective probabilities at step $2$ of $1/12$ and $11/12$.
The rules for propagating the probabilities from one step to the next are straightforward but tedious. The number of states grows inexorably, and many of the states will have eventually have insignificantly small probabilities. But the combined probability of all states at any one step is $1.0$, and there are no subtraction cancellations (which makes our floating point computation quite robust and reliable).
After I polish my Prolog code and commenting of it a little, I'll push it up to GitHub and give a link to it here. Curiously I found that all but $58$ of the $905$ final states give eleven in the largest three parts, but the collective probability of these states is (as already noted) slightly less than $50$%.