Another kind of derangement?

Question

I reading about derangements, and the following question came to my mind.

Suppose in an office, there work 5 teams, each consisting of 1 head and 3 staff (so there is a total of 15 staff). If the company wants to rearrange the staffs such that each staff is assigned to a different head, how many ways can it be done?

I thought about this, but I don't understand how this can be solved. Can anyone help?

Answer 1

The Python code below counts the number of possible assignments for $m$ teams of size $n$. It recursively assigns staff members to new teams, keeping track of how many empty slots and unassigned members there are for each team, and aggressively caching partial results.

For $n=1$, this is just the number of derangements of $m$ elements. For $n>1$, many of these sequences appear to be in the OEIS as "card-matching numbers" or "dinner-diner matching numbers". For instance, your case (teams of size $3$) appears as OEIS:A059703. The answer to the original question ($5$ teams of size $3$) is $6699824$.

Note that a decent approximation can be obtained by counting the number of ways to assign the staff to the $5$ teams in sets of $3$ (this is $15! / (3!)^5$), and then multiplying this by a rough probability that no one is assigned to his old team (each person is on a new team with probability $4/5$, so we can try $(4/5)^{15}$ for the overall probability). This gives $$ \frac{15!}{(3!)^5}\left(\frac{4}{5}\right)^{15} \approx 5900000, $$ or about $10\%$ less than the correct figure.

---

def assignOne(curr, i, j):
   '''Assign one of old team i to new team j.'''
   asLists = list(map(list, curr))
   (src, dst) = (asLists[i], asLists[j])
   if src[0] == 0 or dst[1] == 0: return None
   src[0] -= 1
   dst[1] -= 1
   asLists.sort()
   return tuple(map(tuple, asLists))

def count(curr, cache={}):
   if max(map(max, curr)) == 0: return 1
   if cache.has_key(curr): return cache[curr]
   allNext = {}
   nn = len(curr)
   for j in xrange(nn-1):
      key = assignOne(curr, nn-1, j)
      if key: allNext[key] = allNext.get(key, 0) + 1
   ret = sum([allNext[nxt] * count(nxt, cache) for nxt in allNext.keys()])
   cache[curr] = ret
   return ret

def countWays(numTeams, teamSize):
   curr = [(teamSize, teamSize)] * numTeams
   curr = tuple(map(tuple, curr))
   return count(curr)

>>> [countWays(x, 1) for x in xrange(2, 12)]
[1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570]

>>> [countWays(x, 2) for x in xrange(2, 9)]
[1, 10, 297, 13756, 925705, 85394646, 10351036465]

>>> [countWays(x, 3) for x in xrange(2, 9)]
[1, 56, 13833, 6699824, 5691917785, 7785547001784, 16086070907249329]

Answer 2

Given the clarification that the teams may split up, it takes some work. Let the heads label the new teams. Assign three people to the first head. They might be all from the same team, so you have a similar problem for four teams (but there are fewer constraints). They might be from three separate teams, or two might come from the same team. Each possibility sprouts a different tree. Having chosen the pattern for the first team (which you can compute the number of ways to make that pattern) I would note that $12!=479,001,600$ is a reasonable number of iterations and just check each one.