Monthly Archives: January 2016

Secret Santa solution with burritos

Posted on by
2

Introduction

You and a group of co-workers all ordered burritos for lunch, and it’s your job to go pick them up.  When you arrive at the restaurant, you are given a cardboard box with 22 foil-wrapped burritos: 1 veggie, 8 chicken, 6 steak, and 7 carnitas.

However, when you return to work and open the box, none of the burritos are labeled!  And because they are, well, burritos, you can’t determine what’s inside each one without opening it up or taking a bite.  So you just pass out burritos randomly and hope for the best.

How well should you expect this to work?  That is, how many co-workers will get what they ordered, in distribution and on average?  What is the probability of the worst-case scenario where no one gets what they ordered?

This is exactly the same “Dinner-Diner Matching Problem” described by Margolius in [1], just dressed up a little differently.  It is also exactly the same problem as the Secret Santa drawing with families described in the previous post, where the “bad” outcome of a person drawing the name of someone in his own immediate family (including himself) corresponds to the “good” outcome here of a co-worker getting one of the burritos that she ordered.  The solution approach is the same in either case, but since the holidays have come and gone, let’s talk about burritos instead.

The objective here is not just to describe the mathematics involved– that’s been done– but to provide Python code to perform the actual calculations.

Permutations with restricted positions

An assignment of exactly one burrito to each of the n=22 co-workers may be represented as a permutation, which we can visualize as a selection of n squares to place non-attacking rooks on an n \times n chess board.  Each row of the board represents a co-worker, and each column represents a specific burrito; a rook represents the corresponding co-worker receiving the corresponding burrito.  “Non-attacking” means nobody gets more than one burrito, and no two people have to share a single burrito.

In addition to the non-attacking requirement, we may impose further restrictions on which permutations are allowed: the figure below shows such a board, with the black squares indicating “restricted” positions corresponding to co-workers receiving their desired variety of burrito.  Note that the co-workers and burritos (rows and columns, respectively) have been conveniently ordered so that the restricted positions are square “sub-boards” along the diagonal.  We are interested in counting permutations that avoid these restricted positions.

Board representing restricted positions for the burrito problem.

Board representing “restricted” positions (shown in black) for the burrito problem.

(It seems backward to refer to someone getting their desired type of burrito as a restricted position.  This would have made more sense in the context of the Secret Santa drawing, where we really did want to avoid drawings within immediate families.  We could just as well “reverse” the board, changing white to black and black to white, and with some modified bookkeeping arrive at the same answer… but it will be useful to keep things as they are, as we will see shortly.)

Rook polynomials

In how many of the n! possible ways to hand out burritos does no one get what they ordered?  Using inclusion-exclusion, this number of permutations avoiding all restricted positions is

\sum\limits_{k=0}^n (-1)^k r_k (n-k)!

where r_k is the number of ways to place k non-attacking rooks on the board B of restricted positions; i.e., on the black squares in the above figure.

So how can we compute the r_k?  In general this is a hard problem, but in this special case we get a lot of help by representing the sequence of r_k as a generating function known as the rook polynomial of the board B:

R_B(x) = \sum\limits_{k=0}^\infty r_k x^k

There are two reasons why this is useful here.  First, if the board B happens to be a disjoint union of sub-boards that have no rows or columns in common, then the rook polynomial of B is the product of the rook polynomials of the sub-boards.  In this case, the sub-boards are the 1×1, 8×8, 6×6, and 7×7 “complete” boards of all-black squares along the diagonal.

Second, the rook polynomial for just such a complete m \times m board is easy to compute:

R_{m \times m}(x) = \sum\limits_{k=0}^m {m \choose k}^2 k! x^k

(Intuitively, we are choosing k of m rows and k of m columns, then placing non-attacking rooks on the resulting k \times k sub-board.)

Solution

Putting it all together, given n = m_1 + m_2 + ... + m_j co-workers ordering burritos (or family members in a Secret Santa drawing), made up of sub-groups of m_i people ordering the same type of burrito (or in the same immediate family), the rook polynomial for the corresponding block-diagonal board is

R_B(x) = \prod\limits_{i=1}^j R_{m_i \times m_i}(x)

And the coefficients r_k of the resulting polynomial may be used in the inclusion-exclusion formula above to compute the number of permutations where no one gets what they ordered (or no one draws the name of someone in his immediate family).

The following Python code implements these formulas:

import numpy as np
from numpy.polynomial import polynomial as P
import functools

def binomial(n, k):
    """Binomial coefficient n "choose" k."""
    if 0 <= k <= n:
        return (np.math.factorial(n) //
                np.math.factorial(k) // np.math.factorial(n - k))
    else:
        return 0

def rook_poly(m):
    """Rook polynomial for complete mxm board."""
    return np.array([binomial(m, k) ** 2 * np.math.factorial(k)
                     for k in range(m + 1)], dtype=object)

def secret_santa_burrito(groups):
    """Hit polynomial for permutations with block diagonal restrictions."""
    r = functools.reduce(P.polymul, [rook_poly(m) for m in groups])
    n = sum(groups)
    t_1 = np.array([-1, 1], dtype=object)
    return functools.reduce(P.polyadd, [P.polypow(t_1, k) * r[k] *
                                        np.math.factorial(n - k)
                                        for k in range(n + 1)])

print(secret_santa_burrito([1, 8, 6, 7]))

If you look closely, the last function does a bit more work than described so far.  It’s an exercise for the reader to show that we can actually compute the entire distribution of numbers of possible permutations according to the number k of “hits” on restricted positions (i.e., how many people get what they ordered?), as coefficients of the hit polynomial given by

N_B(t) = \sum\limits_{k=0}^n (t-1)^k r_k (n-k)!

where the inclusion-exclusion formula above is simply N_B(0).

Finally, note that derangements are a special case where m_1=m_2=...=m_n=1; that is, the board consists of single black squares along the diagonal.  As is well-known, the probability of a random permutation being a derangement is approximately 1/e.  This generalizes nicely; Penrice in [2] describes a bounding argument that, with n families each of size k, the probability of a successful Secret Santa drawing tends to e^{-k} as n grows large.

References:

  1. Margolius, B., The Dinner-Diner Matching Problem, Mathematics Magazine, 76(2) April 2003, p. 107-118 [JSTOR]
  2. Penrice, S., Derangements, Permanents, and Christmas Presents, American Mathematical Monthly, 98(7) August 1991, p. 617-620 [JSTOR]