# Practical Inevitability of Clustering

### N. N. Taleb's General Solution

We start with the general. The compositions of a positive integer $n$ into $d$ ordered parts treating $0$ as a significant addend (e.g. $0+3$ is different from $3+0)$ is given by the vector $C_{p,k}$. The number of compositions will be:

$\displaystyle \frac{(d+n-1)!}{(d-1)! n!}$

More specifically

$\displaystyle \mathcal{M}_{(n,\overset{\rightharpoonup }{p})}(\overset{\rightharpoonup }{\chi _i})= n! \prod _{j=1}^d \frac{p_j^{(\overset{\rightharpoonup }{\chi _i})_j}}{(\overset{\rightharpoonup }{\chi _i})_j!}$

We finally have

$\displaystyle \mathbb{P}(M\geq m)=\sum _{i=1}^{\frac{(d+n-1)!}{(d-1)! n!}} \mathbb{1}_{\max \overset{\rightharpoonup }{\chi _i}\geq m}\mathcal{M}_{\left(n,\overset{\rightharpoonup }{p}\right)}\left(\overset{\rightharpoonup }{\chi _i}\right)$

On our example, using Mathematica code with the package Combinatorica:

\displaystyle \chi =\text{Compositions}(8,16);\\ \begin{align} \sum _{i=1}^{\text{Length}[\chi ]} \text{Boole}[\max (\chi [[i]])&\geq 3] \text{PDF}[\text{MultinomialDistribution}[8,p],\chi [[i]]]\\ &\approx 0.169376. \end{align}

### Long Huynh Huu's Enumerative Combinatorics

We compute the probability $p'$ that every square has $\lt m$ darts, then find $p = 1-p'.$ Let's say we're given a vector $(k_1,\ldots,k_d)$ saying that $k_i$ darts hit the $i^{th}$ square. Then we can compute its class $(n_0,\ldots ,n_{m-1})$ where $n_i = |\{j\mid k_j = i\}|$ counts the number of squares with $i$ darts. The probability that $k_i$ darts hit the $i^{th}$ square then is

\begin{align} \binom{n}{k_1;\ldots ;k_d}n^{-d} = \frac{n!}{0!^{n_0}\cdot \ldots \cdot (m-1)!^{n_{m-1}}}n^{-d}, \end{align}

so it depends only on the class. The set of all classes is

$\displaystyle \mathfrak{C}(d,n,m) := \{ (n_0,\ldots ,n_{m-1}) \in \mathbb{N}_0^m \mid \sum_i n_i = d, \sum_i in_i = n \}$

For instance

$\mathfrak{C}(16,8,3) = \{(8,8,0),(9,6,1),(10,4,2),(11,2,3),(12,0,4)\}$

For each class $(n_0,\ldots ,n_{m-1})$ there are $\binom{d}{n_0;\ldots ;n_{m-1}}$ distributions of darts $(k_1,\ldots ,k_d).$ We get

$\displaystyle p' = \sum_{(n_0,\ldots ,n_{m-1})\in\mathfrak{C}(d,n,m)} \binom{d}{n_0;\ldots ;n_{m-1}} \frac{n!}{\displaystyle \prod_{i=0}^{m-1} (i!)^{n_i}}d^{-n}.$

        import Data.Ratio

classes d 0 1 = [[d]]
classes d n 1 = []
classes d n m =
let r = div n (m-1)