I'm trying to model random arrival times in discrete time bins.
Suppose I have $n$ (integer) arrival times, which are between $1$ and $m$, with $m$ possible time bins. I randomly draw $n$ integers between $1$ and $m$, and I place every one of the (possibly alike) random numbers in the bin with its number. Thus if I draw $\{1,5,9,5\}$, the bin count for this draw looks like $\{1,0,0,0,2,0,0,0,1,0\}$ and I call this a $\{2,1,1\}$ configuration.
What is the probability of finding a configuration $\{p_1,p_2,\ldots,p_n\}$, with $p_1\ge p_2\ge p_3$ etc, containing $p_1$ count in any bin, $p_2$ count in any other bin, and so forth until $p_n$ (which may or may not be $0$)?
For clarity I imagine I have $n=4$ arrival times and $m=10$ bins. There are $10^4$ possible outcomes. The probability of getting all different arrivals times is the number of permutations of a string like $\{0,0,0,0,0,0,1,2,3,4\}$, containing $4$ distinct symbols and $6$ other identical symbols.
This works out to $10\times 9\times 8\times 7=5040$ as I can choose to place $1$ in any of the $10$ slots, place $2$ in any of the remaining $9$ open slots etc. Thus this type of outcomes occurs with probability $5040/10000$.
Now if I try to compute the probability of getting two like arrival times, and the remaining two arrivals times different - say I draw $\{1,8,2,8\}$ something like $\{0,0,0,0,0,0,1,2,8,8\}$ - there are $10\times 9\times (8\times 7/2)=2520$ permutations of these. The logic is simple: I can place my first symbol in any of the 10 empty bins, my second symbol in any of the remaining $9$ empty bins, and my like symbols in any of the remaining bins, but I must divide by $2$ because they are identical.
However, by running big numerical experiment where I randomly pick $4$-tuples between $1$ and $10$ and simply count the configurations, I find the correct number ought to be something like $10\times 9\times 8\times 6 = 10\times 9\times 8\times {4\choose 2}=4320$. Not good.
The results of the computer simulation (for $10^5$ draws) are $$\left( \begin{array}{cc} \{1,1,1,1\} & 50371 \\ \{2,1,1\} & 43076 \\ \{3,1\} & 3690 \\ \{2,2\} & 2772 \\ \{4\} & 91 \\ \end{array} \right) $$
By hook or by crook I somehow produced the following table: \begin{align} \begin{array}{ccc} \hbox{configuration}&\hbox{combinatorics}&\hbox{Prob}\\ \{1,1,1,1\}& 10!/6!&5040/10^4\\ \{2,1,1\}& 10\times 9\times 8\times {4\choose 2}&4320/10^4\\ \{3,1\}&10\times 9 \times {4\choose 3} & 360/10^4\\ \{2,2\}& 10\times 9 \times {4\choose 2}\times \frac{1}{2}& 270/10^4\\ \{4\} & 10 &10/10^4 \end{array} \end{align} The probabilities sum to $1$, ($10^5\times$Prob) more or less matches the numbers of the simulation, and there's definitely a pattern but I'm defeated to understand how to generalize this to $n$ arrivals times in $m$ time bins. It seems there is a prefactor which depends on the number of distinct symbols, and some combinatorial factor to account for identical entries.
However, trying to $n=5$ times in $m=10$ bins, it's not clear how to infer from the pattern how to compute the probability of the configuration $\{2,2,1\}$ arriving in $10$ different bins.
Since my "configurations" $\{p_1,p_2,\ldots,p_n\}$, with $p_1\ge p_2\ge p_3$ etc are similar to Young tableaux I thought counting tbut it's not clear at all how this would be useful. Moreover the pattern for case of $n=4$.
So you have $n$ objects labelled $1,2, \cdots, n$, whose value ranges in $[1,m]$ and might be repeated.
A) Disregarding the time sequence label, the different arrangements of the objects according to the value (frequency histogram) correspond to the number of way of arranging $n$ undistinguishable objects into $m$ distinguishable bins, or which is the same to the number of weak compositions of $n$ into $m$ parts, which is $$\binom{n+m-1}{n}$$. Asigning them the time labels correspond to make all the possible permutations of the $n$ objects which are $n!$ The total number thus comes out to be $$ \left( \matrix{ n + m - 1 \cr n \cr} \right)n! = {{\left( {n + m - 1} \right)^{\,\underline {\,n\,} } } \over {n!}}n! = \left( {n + m - 1} \right)^{\,\underline {\,n\,} } = m^{\,\overline {\,n\,} } $$ However, this way of counting is making distinction among the histograms for
For example, for two balls and two bins the $ 2^{\,\overline {\,2\,} } =6$ configurations are: $$ \eqalign{ & \left( {\left. {\matrix{ a \cr b \cr } } \right|\emptyset } \right), \;\left( {\emptyset \left| {\matrix{ a \cr b \cr } } \right.} \right), \;\left( {\left. a \right|b} \right), \cr & \left( {\left. {\matrix{ b \cr a \cr } } \right|\emptyset } \right), \;\left( {\emptyset \left| {\matrix{ b \cr a \cr } } \right.} \right), \;\left( {\left. b \right|a} \right) \cr} $$
B) Now consider the expansion of the multinomial of degree $n$ in $m$ variables $$ \eqalign{ & \left( {x_{\,1} + \,x_{\,2} + \, \cdots + \,x_{\,m} } \right)^{\,n} = \left( {x_{\,1} + \,x_{\,2} + \, \cdots + \,x_{\,m} } \right) \cdots \left( {x_{\,1} + \,x_{\,2} + \, \cdots + \,x_{\,m} } \right) = \cr & = \cdots \; + x_{\,k_{\,1} } x_{\,k_{\,2} } \cdots x_{\,k_{\,n} } + \; \cdots \quad \left| {\;k_{\,j} \in \left\{ {1, \cdots ,\,m} \right\}} \right. = \cr & = \sum\limits_{\left\{ {\matrix{ {0\, \le \,r_{\,j} \, \le \,n} \cr {r_{\,1} + r_{\,2} + \, \cdots + \,r_{\,m} \, = \,n} \cr } } \right.} {\left( \matrix{ n \cr r_{\,1} ,\,r_{\,2} ,\, \cdots ,\,r_{\,m} \cr} \right)x_{\,1} ^{\,r_{\,1} } x_{\,2} ^{\,r_{\,2} } \cdots x_{\,m} ^{\,r_{\,m} } } \cr} $$
The second line tells you that you have all the possible sequences of $n$ elements from the set $\{ {x_{\,1} ,\,x_{\,2} ,\, \cdots ,\,x_{\,m} } \} $ with repetition allowed (any, from $0$ to $n$).
The third lines gives you the number of ways to arrange the $n$ elements into a frequency histogram with occupation profile $\left( {r_{\,1} ,\,r_{\,2} ,\, \cdots ,\,r_{\,m} } \right)$, considered as an $m$-tuple, i.e. occurring exactly in that order.
The expansion of the multinomial consists in picking one of the $m$ values from the first parenthesis, one from the second, etc., which corresponds to take ball No. $1$ and assign it to one of the $m$ bins, and same for the second till the $n$th.
In this process the balls enter each bin naturally ordered according to their timing label, and we do not distinguish any more for the order inside a single bin.
The example $m=2,\, n=2$ now gives $m^n=4$ different arrangements as $$ \left( {\left. {a,b} \right|\emptyset } \right),\;\left( {\emptyset \left| {a,b} \right.} \right), \;\left( {\left. a \right|b} \right),\;\left( {\left. b \right|a} \right) $$ and $$ \left( \matrix{ 2 \cr 2,\,0 \cr} \right) = 1, \quad \left( \matrix{ 2 \cr 0,\,2 \cr} \right) = 1, \quad \left( \matrix{ 2 \cr 1,\,1 \cr} \right) = 2 $$ for each different $m$-tuple of the frequency profile.
C) The problem you pose is relevant to case B), but you are interested not just on a specific $m$-tuple, yet in any permutation of a given $m$-tuple.
Let's order the representative $m$-tuple in an increasing way (multiset) and let's count how many of its elements have value $0,1,\cdots,n$ $$ \left( {r_{\,1} ,\,r_{\,2} ,\, \cdots ,\,r_{\,m} } \right)\; \Rightarrow \; \left\{ {\underbrace {0, \cdots ,0}_{q_{\,0} }\;,\;\underbrace {1, \cdots ,1}_{q_{\,1} }\;,\,\; \ldots \;, \;\underbrace {n, \cdots ,n}_{q_{\,n\;} }\;} \right\}\quad \left| \matrix{ \;0 \le q_{\,j} \le n \hfill \cr \;q_{\,0} + q_{\,1} + \cdots + q_{\,n} = m \hfill \cr \;0q_{\,0} + 1q_{\,1} + \cdots + nq_{\,n} = n \hfill \cr} \right. $$
Now the number of ways to permute $n+1$ different objects, each replicated $q_j$ times (null included) for a total of $m$ is just the multinomial coefficient $binom{m}{\bf q}$.
Therefore the required No. of ways would be $$ \bbox[lightyellow] { \eqalign{ & N = \left( \matrix{ n \cr r_{\,1} ,\,r_{\,2} ,\, \cdots ,\,r_{\,m} \cr} \right) \left( \matrix{ m \cr q_{\,0} ,q_{\,1} , \cdots ,q_{\,n} \cr} \right) = \cr & = {{n!} \over {r_{\,1} !\,\;r_{\,2} !\,\; \cdots \,\;r_{\,m} !}}{{m!} \over {q_{\,0} !\;\;q_{\,1} !\; \cdots \;q_{\,n} !}} = \cr & = {{n!} \over {r_{\,1} !\,\;r_{\,2} !\,\; \cdots \,\;r_{\,m} !\;0! \cdots 0!}}{{n!} \over {q_{\,0} !\;\;q_{\,1} !\; \cdots \;q_{\,n} !}} = \cr & = {{n!} \over {\left( {0!} \right)^{\,q_{\,0} } \;\left( 1 \right)!\,^{\,q_{\,1} } \; \cdots \,\; \left( {n!} \right)^{\,q_{\,n} } }}{{m!} \over {q_{\,0} !\;\;q_{\,1} !\; \cdots \;q_{\,n} !}} \cr} }$$
In your example with $n=4, m=10$ $$ \eqalign{ & \left\{ {1,1,1,1} \right\}\; \Rightarrow \;{\bf r} = \left( {0, \cdots ,0,1,1,1,1} \right)\; \Rightarrow \;{\bf q} = \left( {6,4,0, \cdots ,0} \right) \Rightarrow \cr & \Rightarrow \;N = {{n!} \over {\left( {0!} \right)^{\,6} \;\left( 1 \right)!\,^{\,4} }}{{m!} \over {6!\;\;4!\;}} = {{10!} \over {6!}} = 10^{\,\underline {\,4\,} } = 5040 \cr & \left\{ {1,1,2} \right\}\; \Rightarrow \;{\bf r} = \left( {0, \cdots ,0,1,1,2} \right)\; \Rightarrow \;{\bf q} = \left( {7,2,1, \cdots ,0} \right) \Rightarrow \cr & \Rightarrow \;N = {{n!} \over {\left( {0!} \right)^{\,7} \;\left( 1 \right)!\,^{\,2} \;\left( 2 \right)!\,^{\,1} }} {{m!} \over {7!\;\;2!\;\;1!\;}} = {{4!10!} \over {7!\, \cdot 4}} = 6 \cdot 10^{\,\underline {\,3\,} } = 4320 \cr & \left\{ {1,3} \right\}\; \Rightarrow \;{\bf r} = \left( {0, \cdots ,0,0,1,3} \right)\; \Rightarrow \;{\bf q} = \left( {8,1,0,1,0 \cdots ,0} \right) \Rightarrow \cr & \Rightarrow \;N = {{n!} \over {\left( {0!} \right)^{\,8} \;\left( 1 \right)!\,^{\,1} \;\left( 3 \right)!\,^{\,1} }} {{m!} \over {8!\;\;1!\;1!\;}} = {{4!10!} \over {3!\, \cdot 8!}} = 4 \cdot 10^{\,\underline {\,2\,} } = 360 \cr & \left\{ {2,2} \right\}\; \Rightarrow \;{\bf r} = \left( {0, \cdots ,0,0,2,2} \right)\; \Rightarrow \;{\bf q} = \left( {8,0,2,0 \cdots ,0} \right) \Rightarrow \cr & \Rightarrow \;N = {{n!} \over {\left( {0!} \right)^{\,8} \;\left( 2 \right)!\,^{\,2} }}{{m!} \over {8!\;\;2!\;}} = {{4!10!} \over {4 \cdot 2\, \cdot 8!}} = 3 \cdot 10^{\,\underline {\,2\,} } = 270 \cr & \left\{ 4 \right\}\; \Rightarrow \;{\bf r} = \left( {0, \cdots ,0,0,4} \right)\; \Rightarrow \;{\bf q} = \left( {9,0,0,0,1,0 \cdots ,0} \right) \Rightarrow \cr & \Rightarrow \;N = {{n!} \over {\left( {0!} \right)^{\,9} \;\left( 4 \right)!\,^{\,1} }}{{m!} \over {9!\;\;1!\;}} = {{4!10!} \over {4! \cdot 9!}} = 1 \cdot 10^{\,\underline {\,1\,} } = 10 \cr & {\rm Tot} = 10000 = m^{\,n} \cr} $$