No. of combinations possible with restrictions

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!

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$$

• 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 – Erik Vesterlund Jan 16 '14 at 17:03
• 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? – leonbloy Jan 16 '14 at 17:12
• 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? – Erik Vesterlund Jan 16 '14 at 17:36
• 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). – leonbloy Jan 16 '14 at 17:41
• 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. – Erik Vesterlund Jan 16 '14 at 18:01