2
$\begingroup$

This is a problem inspired by my job, I wonder if my boss has ever performed the calculation...

Suppose we are to divide $n$ people into groups of three (assume $n=3n'$ for some $n' \geq 3$), and that $n/3 \leq k < n$ of them are distinguished in some manner. In how many ways can the $n$ people be divided into groups of three so that there is at least one distinguished person in each group?

I'm afraid I don't have anything of my own to contribute to solving this, but I think about it every time I work so I'd really appreciate it if someone would solve this; my knowledge of combinatorics is nil so hints wouldn't really help :P Thanks!

$\endgroup$
1
$\begingroup$

I'm not sure if this has a simple solution.

Let $m=n/3$

Let $S_{m,k}$ be the number of ways of partitioning a set of $n$ (distinct) elements -including a subset of $k$ "special" elements- in $m$ (distinct) groups of size 3, such that each group has at least one of the "special" elements. Then

$$S_{m,k}=0 \hskip{1cm} {\rm if}\hskip{2mm} k<m \hskip{2mm}$$ $$S_{1,k}=1$$

We can compute some special values:

$$S_{k,k}=\frac{k! \, (n-k)!}{2^k}$$

(Explanation: as we have $k$ special elements and $k$ groups, one goes in each groups, what gives $k!$ permutations; afterwards we must place $n-k$ elements in $k$ boxes, two in each: for the first we have $n-k \choose 2$, for the next $n-k-2 \choose 2$ and so on, that is, a multinomial: $ {n-k \choose 2}{n-k-2 \choose 2} \cdots {2 \choose 2}=\frac{(n-k)!}{2^k}$ )

$$S_{m,k}= \frac{(3m)!}{(3!)^m}, \hskip{1cm} 3(m-1) < k \le 3 m $$

I general, the following recursion holds:

$$S_{n,k}= k {n-k \choose 2} S_{m-1,k-1}+{k \choose 2} (n-k) S_{m-1,k-2}+{k \choose 3} S_{m-1,k-3}$$

This allows for numerical computation:

 m  k   s
 2  2   12
 2  3   18
 2  4   20
 2  5   20
 2  6   20
 3  3   540
 3  4   1080
 3  5   1440
 3  6   1620
 3  7   1680
 3  8   1680
 3  9   1680
 4  4   60480
 4  5   151200
 4  6   237600
 4  7   302400
 4  8   342720
 4  9   362880
 4  10  369600
 4  11  369600
 4  12  369600
 5  5   13608000
 5  6   40824000
 5  7   74088000
 5  8   105840000
 5  9   131544000
 5  10  149688000
 5  11  160776000
 5  12  166320000
 5  13  168168000
 5  14  168168000
 5  15  168168000

An easy approximation (probably an asymptotic) for large $n$ can be obtained by probabilistic argument, assuming independence:

$$ S_{m,k}\approx\frac{(3m)!}{(3!)^m} \left( 1- \left(1 -\frac{k}{3m}\right)^3\right)^m $$

$\endgroup$
  • $\begingroup$ Thanks. I'm not sure how this solves the problem, could you explain a bit more? The notation $S_{n,k}$ confuses me since, to me, that's Stirling numbers of the second kind. Also this: "including a subset of $k$ "special" elements". The $n$ persons include all $k$, not a proper subset of the $k$. It is also assumed that $m \leq k < n$, whence the situation $S_{m,k}=0$ cannot occur. I can't let this problem go so I've opened my combinatorics book now :D $\endgroup$ – Erik Vesterlund Jan 16 '14 at 17:03
  • $\begingroup$ 1) $S_{n,k}$ is just an arbitrary function, use another letter if you prefer. 2) I meant that the full set (size $n$) includes a subset of size $k$ ($k \le n$) (no reason to exclude also the case $k =n$). Do you agree at least with the numerical values? $\endgroup$ – leonbloy Jan 16 '14 at 17:12
  • $\begingroup$ Well I'm still not sure about the notation; you write $S_{m,k}$ for the number of ways to partition a set of $n$ members into $m$ groups, do you mean $S_{n,m}$ then? $\endgroup$ – Erik Vesterlund Jan 16 '14 at 17:36
  • $\begingroup$ The counting involves three parameters ($n,m,k$), but actually $m$ and $n$ are not independent parameters (one gives the other via $n=3m$) so I just write $S_{m,k}$ , parametrizing on $m$ and $k$. For example, the line "2 5 20" in my listing means that there are 20 ways of divinding $2\times 3=6$ elements (having $5$ special) into 2 groups (having 3 elements each). $\endgroup$ – leonbloy Jan 16 '14 at 17:41
  • $\begingroup$ Ah ok. About the numbers, I can't really wrap my head around what you're doing, what with the recursion and all (again, $k>n$ isn't possible). But let's look at the case where there are two groups and two special persons, i.e. $S_{2,2}$. In some manner the boxes (let's do balls and boxes instead, with the special balls being the balls numbered $1,...,k$) are now distinct. Choosing any two balls for the remaining spots in box 1 (the one with ball 1) immediately determines the configuration in box 2. How many ways can we choose the balls that go into box 1? $4\cdot 3/2=6$ ways. $\endgroup$ – Erik Vesterlund Jan 16 '14 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.