The Secret Santa Problem Continues

Rose-Hulman Undergraduate Mathematics Journal Rose-Hulman Undergraduate Mathematics Journal

Volume 18

Issue 1

Article 18

The Secret Santa Problem Continues The Secret Santa Problem Continues

Daniel Crane

Taylor University

Tanner Dye

Taylor University

Follow this and additional works at: https://scholar.rose-hulman.edu/rhumj

Recommended Citation Recommended Citation

Crane, Daniel and Dye, Tanner (2017) "The Secret Santa Problem Continues,"

Rose-Hulman Undergraduate

Mathematics Journal

: Vol. 18 : Iss. 1 , Article 18.

Available at: https://scholar.rose-hulman.edu/rhumj/vol18/iss1/18

Rose-

Hulman

Undergraduate

Mathematics

Journal

Sponsored by

Rose-Hulman Institute of Technology

Department of Mathematics

Terre Haute, IN 47803

[email protected]

scholar.rose-hulman.edu/rhumj

the secret santa problem

continues

Daniel Crane

Tanner Dye

Volume 18, No. 1, Spring 2017

Taylor University

Rose-Hulman Undergraduate Mathematics Journal

Volume 18, No. 1, Spring 2017

the secret santa problem continues

Daniel Crane Tanner Dye

Abstract. We explore the Secret Santa gift exchange problem. A group of n people

draws names at random, giving a gift to the person drawn. First, we examine the

probabilities of gift exchanges under various scenarios when everyone draws names at

once, similar to Montmort’s matching problem. We then consider the probabilities of

certain gift exchanges when people take turns drawing names and develop a strategy

to maximize the likelihood of receiving a gift from the most generous participant.

Acknowledgements: This work was partially funded by a Taylor University Faculty

Mentored Undergraduate Summer Scholarship. We would also like to thank Dr. Case for

advising us on our research.

Page 290 RHIT Undergrad. Math. J., Vol. 18, No. 1

1 Introduction

Secret Santa gift exchanges are a popular Christmas tradition. In a Secret Santa gift ex-

change, a group of n people draws names at random, with the requirement that a person

can not draw him or herself. Then each person gives a gift to the person drawn.

There are several ways to design a Secret Santa gift exchange. Previous work done on

these gift exchanges [2, 5, 6, 9, 10] usually operates under the assumption that everyone is

equally likely to give a gift to any other person in the gift exchange, which is true when

everyone draws a name at once. In Section 2, we summarize some of these results and also

apply results proven in other contexts to Secret Santa. We consider cases where everyone is

single, where all participants are in families of size k, and where participants are in families

of diﬀerent sizes. The probability of needing to redraw names depends on family size when

we do not allow family members to give gifts to each other. Rook polynomials allow for

calculation of this probability. Other techniques such as the inclusion-exclusion principle

and bounds on permanents of matrices can be used for studying he limiting behavior of

these probabilities when the number of participants in the gift exchange increases.

Next, in Section 3, we examine probabilities of allowed gift exchanges when names are

drawn one at a time as opposed to all at once as in Section 2, and we then determine

which kinds of exchanges are more likely than others. Speciﬁcally, we show that the order

of drawing names aﬀects to whom each participant is most likely to give a gift. In this type

of gift exchange, the probability of any one derangement can be written as a product of

terms involving an indicator function, and this allows us to compare the probabilities for

two diﬀerent giver-recipient pairs. We ﬁnd that each person is most likely to give to the

person drawing directly before him, with the ﬁrst person to draw being most likely to give

a gift to the last person to draw. Furthermore, we ﬁnd that the last person to draw is more

likely to give a gift to the second to last person than any other giver-recipient pair.

2 Drawing Names All at Once

In Secret Santa, nobody is allowed to give a gift to himself or herself. We might add the

additional constraint that if a participant is in a family of k people (for k ≥ 2), he may not

give to himself or to a family member. We will refer to a gift exchange where no one gives

to himself or a family member, as an allowed arrangement. When everyone draws names at

once, there is a chance that nobody will draw his own name or a family member’s name. The

probability of this is equal to the number of allowed arrangements divided by total number

of arrangements, n!. As the number of people approaches inﬁnity, this probability converges

to diﬀerent values depending on the number of people in various family sizes.

2.1 The Simplest Case

When the only restriction is that nobody can draw his own name, the allowed exchanges

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 291

are called derangements. The number of possible derangements for n people is

= n!

i=0

(−1)

, (1)

which can be veriﬁed using the inclusion-exclusion principle. This allows for a simple proof

of our ﬁrst result by recognizing the Taylor series for e

−1

. In the following theorem we see

that the probability of a derangement approaches e

−1

as the number of people n increases.

Theorem 2.1. If d

is the number of derangements of length n, then

lim

n→∞

. (2)

This is a well known and easy to prove result known by multiple names, most notably as

Montmort’s Matching Problem [4].

2.2 Families of k people

Now suppose that all of the n people in a gift exchange are partitioned into families of

size k. In that case, the rules require that nobody can give to a member of his own family.

In this case, the number of allowed arrangements can be calculated using rook polynomials

[3] or using permanents of (0,1) matrices. The number of allowed arrangements is

(n) =

i=1

(−1)

∗ (n − i)!, (3)

where R

is the i

coeﬃcient of the rook polynomial

R(x) =

j=0





j!x

n/k

The i

coeﬃcient of a rook polynomial of degree d represents the number of ways to place

i non-attacking rooks, meaning no rooks share a row or column, on an d × d chessboard. In

this case, our problem can be represented as the number of ways to place k non-attacking

rooks each on n/k separate chessboards.

Alternatively, by letting A be a (0, 1) matrix with k × k blocks of 0s along the diagonal

and 1s everywhere else we can calculate the value F

(n) by taking the permanent of A. This

alternate method is used in the proof of out next theorem, which determines the limiting

behavior of the probability of an allowed arrangement as n increases.

Theorem 2.2. (Penrice [6]) If F

(n) represents the number of allowed arrangements for a

gift exchange with n people in families of k, then

lim

n→∞

(n)

= e

−k

. (4)

Page 292 RHIT Undergrad. Math. J., Vol. 18, No. 1

Penrice’s proof involves ﬁnding upper and lower bounds on the fraction F

(n)/n! using

inequalities from Minc and Van der Waerden for permanents of (0,1) matrices. Since both

of these bounds go to e

−k

, then the probability does as well.

2.3 The General Case

Of course, large collections of people are rarely all in families of equal size. More generally,

for n people, let p

be the proportion of the people who are individuals, p

be the proportion of

the people who are in families of two, and so on so that p

represents the proportion of people

in a family of i. Once again, we can calculate the number of allowed arrangements using

rook polynomials or permanents. Letting F

denote the number of allowed arrangements for

this case, we ﬁnd that

i=1

(−1)

∗ (n − i)!,

where R

is the i

coeﬃcient of the rook polynomial

R(x) =

k=1

j=0





j!x

and M denotes the largest family size in the collection of participants.

We then come to our next result which applies a known theorem to Secret Santa ex-

changes.

Theorem 2.3. If F

(n) represents the number of allowed arrangements for a gift exchange

with p

n people in families of size i for each i ∈ Z

∪ 0, then

lim

n→∞

(n)

= e

−x

(5)

where

x =

i=1

and M denotes the largest family size.

We see that this agrees with our previous results in section 2.2 when we let p

= 1 and

= 0 for i 6= k.

Proof. The proof follows from a special case of a result by Barton given in Margolius [4]

and proven by Barton [1]. In Barton’s proof, the problem is viewed as two decks of N cards

being matched up pairwise. There are S suits in each deck with n

cards of suit i in deck

one and m

cards of suit i in deck two. A match occurs if a card from deck 1 of suit i is

matched up with a card from deck 2 of the same suit.

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 293

For our purposes, each deck of cards corresponds to the participants in Secret Santa (one

being the givers and one being the receivers). Then n

= m

because the givers and receivers

are the same collection of people. Each of the S suits corresponds to an individual family of

people.

Barton proves that the distribution of the number of matching cards, or in our case the

number of people who drew their own name or a family member’s name, is asymptotic to a

Poisson distribution with parameter

λ =

i=1

For us, the parameter becomes

i=1

. It can be veriﬁed using our previous notation

that this becomes

λ =

i=1

= x.

So the probability distribution for the number of people j who draw their own or a family

member’s name is given by

−x

So the probability that nobody draws his own name or a family member’s name (j = 0)

becomes e

−x

3 Drawing One at a Time

We assumed in section 2 that each derangement was equally likely, but few gift exchanges are

set up so that everyone draws names at the same time. A more common method of drawing

is for everyone to take turns drawing names and for each person to redraw if he gets his own

name. In this section, we will assume that everyone is single. In this case, the only problem

that might arise is if the last person gets his own name. We will assume that if this happens,

then everyone will return the names drawn and they will redraw using the same method.

An interesting consequence of this method of drawing names is that diﬀerent arrangements

are no longer equally likely. We ﬁnd that the order in which people draw determines who

each person is most likely to draw.

3.1 Ranking Derangement Classes by Likelihood

First, we will introduce some notation. We use x → y to indicate that the x

person to

draw gives to the y

person. Similarly, we will let P (x → y) denote the probability that the

person gives to the y

person. Finally, if α is a derangement, we will let α(x) = y mean

Page 294 RHIT Undergrad. Math. J., Vol. 18, No. 1

that x → y for the speciﬁc derangement α.

Most of our proofs rely heavily on two ideas. The ﬁrst is our method for calculating

probabilities. One method of computing probabilities when names are drawn one at a time

is given by White [10]. We will employ simpler, more illustrative notation for these proba-

bilities.

Lemma 3.1. Let D

denote the set of all derangements (allowed gift exchanges) for n people.

For a given derangement α ∈ D

, the probability of α is given by

P (α) =

i=1

n − i + I

(i)

, (6)

where i runs over all of the n people, and I

(i) is an indicator function that is equal to 1

if the i

person’s name is drawn before i draws and equal to 0 if his name has not yet been

drawn. To avoid dividing by zero, we deﬁne I

(n) = 1.

Proof. The probability of person i drawing a speciﬁc name is 1 divided by the number of

names left in the hat which i could possibly draw. We ﬁnd that this number of names is

n − i + 1 if i has not been drawn and n − i otherwise. Then the probability associated

i → α(i) for a speciﬁc derangement α is

P (i → α(i)) =

n − i − I

(i)

The probability of the derangement as a whole is the product of such terms,

P (α) =

i=1

P (i → α(i)) =

i=1

n − i + I

(i)

For example, the probability where n = 5 people and the derangement

α = 1 → 5 → 4 → 2 → 3 → 1

(where 1 is ﬁrst to draw, 2 second, and so on) is (1/4)(1/3)(1/3)(1)(1) = 1/24.

The second idea we employ is the notion of “pairing up” derangements with each other.

We can ﬁnd a bijection between sets of derangements and compare the probabilities of these

derangements. If we can ﬁnd a bijection between arrangements where x → y and arrange-

ments where x → z and every individual arrangement where x → y is at least as likely as the

corresponding arrangement where x → z, then we can conclude that P (x → y) ≥ P (x → z).

We apply these ideas to prove the next several theorems. The ﬁrst one involves those

who draw names before the k

person.

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 295

Theorem 3.2. For n ≥ 3 participants, if i < i + 1 < k then P (k → i) ≤ P (k → i + 1).

In everyday language, this conjecture states that a participant is more likely to draw the

second person in a pair of consecutive people who had already drawn. A direct consequence

of this is that, of all the people who drew before him, he is most likely to draw the person

who drew right before him, second most likely to draw the person who drew two people

before him, and so on.

Proof. Let A be the set of derangements in D

where k → i and B be the set of derangements

where k → i + 1. Note that |A| = |B| by symmetry. We will set up a bijection from A to B

and compare each α ∈ A to its corresponding derangement β ∈ B.

There are three diﬀerent types of derangements in A (and in B). We will examine each

of these three cases.

Case 1: Suppose that α(y) = i + 1 for some y < i. In other words, i + 1 was drawn

before i’s turn for the derangement α.

In this case, we will map α to the β ∈ B such that α and β are identical except for the

two diﬀerences that β(k) = i + 1 and β(y) = i,. Thus, P (α) and P (β) (which are both just

products of probabilities of the form 1/(n − i + I

(x))) will agree with each other except

possibly at the terms 1/(n − i + I

(i)) and 1/(n − (i + 1) + I

(i + 1)).

These terms will be diﬀerent for the two derangements. For α, i + 1 drew after he was

drawn so I

(i + 1) = 1. Meanwhile i drew before he was drawn, so I

(i) = 0.

On the other hand, since i drew after he was drawn in β, then I

(i) = 1 and I

(i+1) = 0

because he drew a name before his name was drawn.

Thus we have (note that I

(j) = I

(j) for j 6= i, i + 1)

P (α) =

(n − i)

(n − (i + 1) + 1)

j=1,j6=i,j6=i+1

n − j + I

(j)

whereas

P (β) =

(n − i + 1)

(n − (i + 1))

j=1,j6=i,j6=i+1

n − j + I

(j)

Then by inspection, we see that P (β) > P (α).

Case 2: Now suppose α is such that α(i) = i + 1 and α(i + 1) = y for some y ∈ {1, ...n}.

Then map this α to a β ∈ B such that α = β except for the following alternations: β(k) =

i + 1, β(i) = y and β(i + 1) = i.

For α, i draws before he has been drawn (by k) so I

(i) = 0 and i + 1 draws after he has

been drawn (by i). So I

(i + 1) = 1. Thus,

P (α) =

(n − i)

(n − (i + 1) + 1)

j=1,j6=i,j6=i+1

n − j + I

(j)

For β, i + 1 draws before he has been drawn (by k) so I

(i + 1) = 0 and i also draws

before his name is drawn (by i + 1). So I

(i) = 0. Thus,

Page 296 RHIT Undergrad. Math. J., Vol. 18, No. 1

P (β) =

(n − i)

(n − (i + 1))

j=1,j6=i,j6=i+1

n − j + I

(j)

Once again, we see that P (β) > P (α).

Case 3: Now suppose that α(k) = i, α(m) = i + 1 where m ∈ {i + 1, ...n}; (i.e i + 1

draws before his name was drawn).

We will map α in this case to the β equal to α except that β(k) = i + 1 and β(m) = i.

In α, i+1 draws before he was drawn so I

(i+1) = 0. The same is true for i so I

(i) = 0.

Thus,

P (α) =

(n − i)

(n − (i + 1))

j=1,j6=i,j6=i+1

n − j + I

(j)

Now for β, both i and i + 1 drew before they were drawn (by m and k) so I

(i) =

(i + 1) = 0 Thus,

P (β) =

(n − i)

(n − (i + 1))

j=1,j6=i,j6=i+1

n − j + I

(j)

Note that these probabilities are equal so P (α) = P (β) for case 3.

We now show that our mapping is a bijection. For β ∈ B, β will have one of the forms

described by the three cases above. Then our mapping is invertible and must be a bijection.

Then P (α) < P (β) in cases 1 and 2 and P (α) = P (β) in case 3. Therefore P (k → i) =

P (α

) ≤

P (β

) = P (k → i + 1).

We ﬁnd that when this inequality is strict whenever we have at least 3 people in our gift

excange.

Corollary 3.3. The inequality in Theorem 3.2 is a strict inequality for n ≥ 3.

Proof. Consider, n = 3 people and 3 → 1. Then we must have 1 → 2 and 2 → 3. Thus, only

case 2 in Theorem 4 holds for n = 3 people which shows the inequality proved in Theorem 3.2

must be strict for n = 3. For n ≥ 3, there certainly exists a derangement described by case

2. So there will never be a case where only case 3 holds. This completes the proof.

From this we see that person k is more likely to give a gift to the k − 1

person than to

anyone else drawing a name before k.

In the following proof, we consider those who draw names after the k

person. We will

ﬁnd that person k is more likely to draw the last person’s name than he is to draw the name

of anyone else after k. It is important to note that this is diﬀerent from our other proofs

in that it compares conditional probabilities in which we know information about previous

draws.

Theorem 3.4. For k < i < n, P (k → n) ≥ P (k → i).

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 297

Proof. Instead of comparing individual derangements, we will compare diﬀerent ways that

the ﬁrst k − 1 people could draw and look at who k is most likely to draw. By k’s turn,

there are three possible cases.

Case 1: If both i and n have already been drawn, then P (k → i) = P (k → n) = 0.

Case 2: If neither i nor n have been drawn, then k is equally likely to draw either. But if

k → i, then there is a chance that n → n, causing a redraw. So for this case P (k → n) >

P (k → i).

Case 3: The ﬁnal case is if only one of the two had been drawn. In this case, we can

deﬁne a bijection from the ways i could be drawn ﬁrst to the ways that n could be drawn

ﬁrst by switching which one was drawn ﬁrst and leaving all other draws the same (note that

we are pairing up ways the ﬁrst k people could draw, not complete derangements). From

equation 6, corresponding ways of the ﬁrst k people drawing have equal probabilities, so

P (k → i) = P (k → n) for this case.

Therefore, P (k → n) ≥ P (k → i).

The next theorem tells us that the k

person is more likely to draw the ﬁrst person than

he is to draw the last person. Combined with our previous theorems, this tells us that each

person is most likely to draw the name of the person right before him. The one special case

is the ﬁrst person, who is most likely to draw the last person’s name.

Theorem 3.5. For 1 < k < n, P (k → 1) ≥ P (k → n).

Proof. By symmetry, there are the same number of derangements where k → n as there

are where k → 1. We will pair these up bijectively by splitting them up into two separate

cases. We will let A be the set of derangements where k → 1 and let B denote the set of

derangements where k → n.

Case 1: Suppose that for some α ∈ A, α(i) = n for some 1 < i < n. We can map this α

to the derangement β ∈ B identical to α except that β(k) = n and β(i) = 1 From equation

(6), we see that P (α) = P (β).

Case 2: Now suppose α(1) = n and α(n) = x for some 1 < x < n. In this case, we can

map this α to the derangement β ∈ B such that the only diﬀerence between α and β is that

β(1) = x, β(k) = n, and β(n) = 1. From equation 6, we see that

P (α) =



n − x



j=1,j6=x

n − j + I

(j)

and

P (β) =



n − x + 1



j=1,j6=x

n − j + I

(j)

So P (α) > P (β) for this case.

Since every derangement in A has a probability greater than or equal to the corresponding

derangement in B, then the sum of the probabilities for A is greater than or equal to that

of B. Therefore, P (k → 1) ≥ P (k → n).

Page 298 RHIT Undergrad. Math. J., Vol. 18, No. 1

The previous three theorems tell us that the k

person to draw is most likely to draw

the k − 1

person (and the ﬁrst person is most likely to draw the last person). However,

numerical simulations appear to indicate that the n

person is more likely to draw the n−1

person than any other person is to draw the person before him. We will prove this in the

next two theorems. Theorem 3.7 is the main result and Theorem 3.6 takes care of a special

case. We prove the special case ﬁrst because it is simpler and involves fewer subcases. The

main result follows from a similar proof.

Theorem 3.6. If there are n participants, then P (n → n − 1) > P (1 → n). This means

that the last person is more likely to give to the second to last person than the ﬁrst person is

to give to the last person.

Proof. Let A be the set of derangements where n → n − 1 and let B denote the set of

derangements where 1 → n. Now suppose that α ∈ A. We will map α to some β ∈ B based

on which of the following cases describes α.

Case 1: If α(1) = n, then α = β for some β ∈ B. In this case, we map α to this β.

Clearly, P (α) = P (β).

Case 2: Suppose that α(y) = n for some 1 < y < n − 1. Suppose α(1) = x. Then we

can map α to the corresponding derangement β ∈ B where β is identical to α except that

β(1) = n, β(n) = x, and β(y) = n − 1. Then, from equation (6), P (α) and P (β) have the

form (since I

(j) = I

(j) for j 6= x, n − 1)

P (α) =





n − x + 1



j=1,j6=x,n−1

n − j + I

(j)

and

P (β) =





n − x



j=1,j6=x,n−1

n − j + I

(j)

Since x < n − 1, then algebra gives us

2(n − x)

n − x + 1

Then P (α) > P (β) for this case.

Case 3: Our last case is if α(n − 1) = n. Suppose α(y) = 1 and α(1) = x (note that it

is possible that x = y). In this case, we will map α to the β ∈ B such that β is identical to

α except that β(1) = n, β(y) = n − 1, β(n − 1) = x, and β(n) = 1. Since applying equation

(6) gives us the same equations for P (α) and P (β) as in case 2, then P (α) > P (β) for this

case as well.

Therefore, P (n → n − 1) ≥ P (1 → n).

Theorem 3.7. For any 1 < k < n, P (n → n − 1) ≥ P (k → k − 1).

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 299

We already know that the k

person is most likely to give a gift to the k − 1

person.

This proof shows that it is more likely that the last person gives a gift to the next to last

person than it is for any other person k to give to the k − 1

person.

Proof. We will give an outline for the proof of this theorem. The proof is similar to that

for Theorem 7, but with 2 extra cases. Let A = {α ∈ D

: α(n) = n − 1} and let

B = {β ∈ D

: β(k) = k − 1}. The ﬁve cases for mapping α to a β are:

Case 1: If α(k) = k − 1, then β = α. Then P (α) = P (β).

Case 2: If α(k) 6= n, n − 1, k − 1 and α(y) = k − 1 for some y 6= k − 1, n − 1, then we map

α to the β identical to α except that β(k) = k − 1, β(n) = α(k) and β(y) = n − 1. In this

case we ﬁnd that P (α) ≥ P (β).

Case 3: This is similar to case 2 except that α(k) = n and β(n) = k. To ensure a one-to-one,

onto map we let β

−1

(n) = α

−1

(k). For this case, P (α) ≥ P (β).

Case 4: If α(n − 1) = k − 1 and α(k) 6= n, then we map α to a β such that β(k − 1) =

n − 1, β(n − 1) = α(k − 1), and β(n) = α(k). Once again, P (α) ≥ P (β).

Case 5: This is the same as case 4 except that α(k) = n. We make a similar change in

the mapping as we did to change from case 2 to case 3. As in the previous three cases,

P (α) ≥ P (β).

Using similar reasoning to our previous proofs, we ﬁnd that P (α) > P (β) or P (α) = P (β)

for each of these cases, so P (n → n − 1) ≥ P (k → k − 1).

3.2 Summary

To summarize our results, we have shown that for the k

person to draw, the order from

most likely person for him to draw to least likely is the following:

k − 1, k − 2, k − 3, ...3, 2, 1, n, ( then k + 1 to n − 1 in some order).

We also know that the most likely event in a gift exchange is for the last person to draw

the next to last person. As an application, if some (slightly greedy) participant k has a very

generous friend g whom k would like to receive a gift from, k may maximize the probability

of being selected by g by letting g draw a name last and letting himself draw second to last.

We can verify that this is true for the case n = 4.

Derangement Probability Derangement Probability Derangement Probability

2143 1/9 3412 1/12 4321 1/12

2413 1/9 3142 1/12 4312 1/12

2341 1/18 3421 1/12 4123 1/6

In the above table, we have used the notation WXY Z to imply that 1 → W , 2 → X, 3 → Y ,

and 4 → Z. The three most likely derangements all involve the last person giving to the

third person, so this is clearly the most likely giver-recipient pair.

Page 300 RHIT Undergrad. Math. J., Vol. 18, No. 1

4 Further Work

More work may be done on the Secret Santa problem, particularly in the instance where

people draw one at a time. We are conﬁdent, but have yet to prove that the k

person is

more likely to draw person i than he is to draw person i+1 when i and i+1 draw somewhere

between k + 1 and n − 1 (inclusive). Another interesting problem would be to explore how

probabilities change drawing one at a time when people are in families of various sizes. A

third problem would be to study the value R(n) =

P (n→n−1)

1/(n−1)

for n people, which represents

how many times more likely the last person is to draw the second to last than you would

expect if all outcomes were equally likely. Calculations of P (n → n − 1) for up to 11 people

and approximations from simulations for up to 10000 people suggest that R(n) increases as

n increases and that R(n) → 2 as n → ∞. Furthermore, it appears (tentatively) that as

n → ∞,

P (n−k→n−k−1)

1/(n−1)

→ (k + 2)/(k + 1) for any 0 ≤ k ≤ n − 2. But at this point, all we

have are numerical values from computer simulations that support this conjecture.

Finally, it might be possible to ﬁnd alternative proofs that are simpler than those we have

given for when people draw one at a time. One possible method might be using permanents

of matrices to represent the probabilities. Let

A =







0 1/(n − 1) 1/(n − 2) ... 1/4 1/3 1/2 1

1/(n − 1) 0 1/(n − 2) ... 1/4 1/3 1/2 1

1/(n − 1) 1/(n − 2) 0 ... 1/4 1/3 1/2 1

1/(n − 1) 1/(n − 2) 1/(n − 3) ... 1/4 1/3 1/2 1

1/(n − 1) 1/(n − 2) 1/(n − 3) ... 0 1/3 1/2 1

1/(n − 1) 1/(n − 2) 1/(n − 3) ... 1/3 0 1/2 1

1/(n − 1) 1/(n − 2) 1/(n − 3) ... 1/3 1/2 0 1

1/(n − 1) 1/(n − 2) 1/(n − 3) ... 1/3 1/2 1 0







Also, we will let M

i,j

represent the matrix formed by removing the i

row and the j

column of A. We will let A

i,j

denote the element in the i

row and the j

column of A.

We ﬁnd that the probability of some derangement α on the ﬁrst draw (allowing the last

person to draw his own name) is equal to

P (α) =

i=1

i,α(i)

Since permanents are used to calculate the sum of all permutations, it follows that

P (i → j) =

i,j

∗ P er(M

i,j

)

P er(A)

In addition to allowing easier computation of probabilities, this might allow for cleaner proofs

using known properties of permanents instead of the lengthy proofs using our method.

RHIT Undergrad. Math. J., Vol. 18, No. 1 Page 301

References

[1] Barton, D.E., “The Matching Distributions: Poisson Limiting Forms and Derived Meth-

ods of Approximation”. Journal of the Royal Statistical Society. Series B, 20(1): 73-92,

1958.

[2] Boyd, A.V., and J.N. Ridley, “The Return of Secret Santa”. The Mathematical Gazette,

85(503):307-311, 2001.

[3] Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. 4th ed. Boston: Addison

Wesley Longman, 1998.

[4] Margolius, Barbara H. “The Dinner-Diner Matching Problem”. Mathematics Magazine,

76(2): 107-118, 2003.

[5] McGuire, Kelly M., George Mackiw, and Christopher H. Morrell. “The Secret Santa

Problem”. The Mathematical Gazette, 83(498):467-472, 1999.

[6] Penrice, Stephen G., “Derangements, Permanents, and Christmas Presents”. The Amer-

ican Mathematical Monthly, 98(7): 617-620, 1991.

[7] Schrijver, A. ”A Short Proof of Minc’s Conjecture.” Journal of Combinatorial Theory

Series A, 25(1978) 80-83.

[8] Van Lint, J.H. ”Notes on Egoritchev’s Proof of the Van der Waerden Conjecture.” Linear

Algebra and Its Applications, 39(1981) 1-8.

[9] Ward, Tony, “Diﬀerence Equations, Determinants and the Secret Santa Problem”. The

Mathematical Gazette, 89(514):2-6, 2005.

[10] White, Matthew J., “The Secret Santa Problem”. Rose-Hulman Institute of Technology

Undergraduate Math Journal, 7(1) (Paper 5), 2006.