A Combinatorics Problem About Structuring a Team

A Combinatorics Problem About Structuring a Team

I have a team responsible for maintaining nn services. I want to split responsibility for these services to 3 sub-teams. How many ways are there to split these services such that each team bears responsibility for n/3±ϵn/3 \pm \epsilon services?

It’s immediately clear that the number of options is less than 3n3^n. With a bit more thought, it’s also clear that the count is less than S2(n,3)∼3n/3!\text{S2}\big(n, 3) \sim 3^n/3!. To get a better upper bound, let’s first get a lower bound by assuming ϵ=0\epsilon = 0. I’ll use Stirling’s approximation to get the count of ways to partition nn items into two groups of size n/3n/3 and 2n/32n/3, and then count the ways to partition the group of 2n/32n/3 into two groups of n/3n/3 each.

a0=(n2n/3)∼1πn⋅3n⋅2−2n/3,a1=(2n/3n/3)∼1πn⋅22n/3,a0⋅a1∼3nπn\begin{eqnarray} a_0 = { n \choose 2n/3 } \sim \frac{1}{\sqrt{\pi n}} & \cdot 3^{n} \cdot 2^{-2n/3} \ , \qquad a_1 = { 2n/3 \choose n/3 } \sim \frac{1}{\sqrt{\pi n}} \cdot 2^{2n/3} \ , \qquad a_0 \cdot a_1 \sim \frac{3^n}{\pi n} \end{eqnarray}

Thus, the number of ways to partition nn items into 3 groups is 𝒪(3n/n)\mathcal{O}\big(3^n/n). Because we allow “almost-equal” groups, we must consider the number of ways to partition the nn services into groups of size within ϵ\epsilon of n/3n/3. This count grows quadratically with ϵ\epsilon and leaves us with 𝒪(ϵ23n/n)\mathcal{O}\big(\epsilon^2 3^n/n) as an upper bound.

𝐍.𝐁\textbf{N.B} — I’m using S2(n,k)\text{S2}\big(n, k) to mean the Stirling number of the second kind, i.e. the number of ways to partition nn items into kk non-empty subsets. I’m using the Wikipedia approximation to get this first (loose) upper bound.

Using a little intuition, I’d conjecture that this upper bound generalizes to 𝒪(ϵm−1⋅mn⋅n−m+12)\mathcal{O}\big(\epsilon^{m-1} \cdot m^n \cdot n^\frac{-m+1}{2}) for mm sub-teams and nn services. Just for good measure, let’s confirm this with the multinomial theorem.

(nn/k,…,n/k)=n!⋅(nm!)−m≈m(n+m2)⋅n−m+12\begin{eqnarray} \binom{n}{n/k, \ldots, n/k} = n! \cdot \left(\frac{n}{m}!\right)^{-m} \approx m^{\left(n\ +\frac{m}{2}\right)}\ \cdot\ n^{\frac{-m+\ 1}{2}}\\ \end{eqnarray}