Secret Santa

Let us denote the 6 people as $A, B, C, D, E, F$ . The total number of ways of giving gifts (including receiving one's own gift) is $6! = 720$ .

We need to calculate the number of ways where A does not receive his own gift and so on for B to F. To make it easier, we will calculate the number of ways where at least one person receives his own gift and subtract this value from 720.

When we fix k points out of n (that is, n people receive their own gifts), the number of ways is ${n \choose k}(n - k)!$ (because we need to choose k points to fix and arrange the remaining n - k points).

Using the principle of inclusion and exclusion, the total number of ways that satisfy the question is:

No. of ways = total permutations - permutations fixing 1 point + permutation fixing 2 points - ... + permutations fixing 6 points $= 6! - {6 \choose 1}5! + {6 \choose 2}4! - ... + {6 \choose 6}1! = 6!\displaystyle \sum_{k=0}^6 \frac {(-1)^k}{k!} = 265$

Note: this kind of arrangement is called "derangement". The number of derangements for n objects is $n!\displaystyle \sum_{k=0}^n \frac {(-1)^k}{k!}$ .

Let's just say the number of different ways to do this with $n$ persons is $f(n)$ . It's obvious that $f(1) = 0$ and $f(2) = 1$ .

Consider the case with $n$ persons, with $n\geq2$ Let's just say the first person got a gift from person $x$ . There are two cases:

A. $x$ got his gift from the first person. In this case, we just need to arrange the other $n-2$ persons. Therefore, the number of ways is $f(n-2)$ .

B. $x$ got his gift from a person other than the first person. In this case, we can simplify the problem by thinking that $x$ 's gift is the first person's gift. (We can do this, since it would be the same problem anyway, $x$ can't get the first person's gift). So, there are $f(n-1)$ ways to do this.

Because there is $n-1$ ways to choose $x$ , $f(x)=(n-1)(f(n-1)+f(n-2))$ . From this, we can calculate $f(3) = 2$ , $f(4)=9$ , $f(5)=44$ , and finally $f(6)=265$ .

It is clear from the problem statement that the gifts must be passed in loops formed by 2 or more people, i.e. each person passes his gift to the next person in a cyclic fashion along this loop . We consider the cases of possible loops formed, which can be easily deduced:
(1) 1 loop of 6
(2) 1 loop of 4, 1 loop of 2
(3) 2 loops of 3
(4) 3 loops of 2

Case (1): -
Number of ways to choose loop of 6: 1.
Number of ways to choose order of cycle of loop of 6: 5!

Case (2): -
Number of ways to choose loop of 4: $^6 C _4$ (Note that loop of 2 will be fixed from this already)
Number of ways to choose order of cycle of loop of 4: 3!
Number of ways to choose order of cycle of loop of 2: 1!

Case (3): - Number of ways to choose 2 loops of 3: $\frac{^6 C _3}{2!}$
Number of ways to choose order of cycle of loop of 3: 2!
Number of ways to choose order of cycle of loop of 3: 2!

Case (4): -
Number of ways to choose 3 loops of 3: $\frac{(^6 C _2)(^4 C _2)}{3!}$
Number of ways to choose order of cycle of loop of 2: 1!
Number of ways to choose order of cycle of loop of 2: 1!
Number of ways to choose order of cycle of loop of 2: 1!

Hence, we conclude that the total number of ways = $(1)(5!) + (^6 C _4)(3!)(1!) + (\frac{^6 C _3}{2!})(2!)(2!) + (\frac{(^6 C _2)(^4 C _2)}{3!})(1!)(1!)(1!) = 265$ .

The problem is just asking for the number of derangements on 6 elements, i.e. a permutation which has no fixed points. Denote $!n$ the number of derangements on $n$ elements. To calculate this is clear:

Say the first element gets mapped to element $i$ . Now look at element $i$ . There are $n-1$ elements it can go to. If it maps to the first element, there are clearly $!(n-2)$ ways to choose the rest of the mappings. If person $i$ does not map to the first element, remark the number of ways to determine the rest of the mappings is just $!(n-1)$ then because it is as if the first element did not exist and mapping an element onto element $1$ is mapping an element onto element $i$ . Thus we get the recursion $!n = (n-1)(!(n-1) + !(n-2))$ .

Using this we can arrive at: $!1 = 0$ obviously, $!2 = 1$ . Then $!3 = 2$ , $!4 = 9$ , $!5 = 44$ , $!6 = 265$ as desired.

We solve the general problem for $n$ persons. Suppose the number of ways is $D(n)$ . Suppose first person receives gift from person $i$ , there are $n-1$ ways to do that. Then we have two possibilities:

1. Person $i$ receives gift from first person. In this case the problem reduces to $n-2$ persons, so number of ways is $D(n-2)$

2. Person $i$ does not receive gift from first person. In this case the problem reduces to $n-1$ persons, since each person has exactly one gift which he cannot receive (person $i$ cannot receive gift from first person, the rest cannot receive gift from themselves). So number of ways is $D(n-1)$ .

Therefore we have this recurrence relation $D(n) = (n-1)(D(n-1)+D(n-2))$ . Since $D(1) = 0$ and $D(2) = 1$ , we have $D(3) = 2, D(4) = 9, D(5) = 44, D(6) = 265$ . So the answer for this problem is $265$ .

Let $P: A^n \to A^n$ the function that maps who gives with who receives. $P$ is an injection (they each give one gift) and a surjection (they each receive one gift), therefore $P$ is a permutation. They are not allowed to give their gift to themselves, so we must consoder only permutations in which none of the elements is mapped to itself (derangements). There are different ways to count derangements, for this small case it's very easy to build $\mathcal{D}(6)$ from smaller values:
$\mathcal{D}(1)=0$ , $\mathcal{D}(2)=1$ are trivial cases.
$\mathcal{D}(3)=2$ , becouse for the first gift there are two possible choices, for next items the choice is forced.
$\mathcal{D}(5)=9$ , becouse from the $4!$ possible permutations, we have to discard:
$\binom{4}{1}\mathcal{D}(3)=4\cdot2$ permutations with a single match and a derangement of the remaining three elements,
$\binom{4}{2}\mathcal{D}(2)=6\cdot1$ permutations with 2 matches and 2 derangements, no permutations with exactly 3 matches and finally a permutation with 4 matches (identity).

similarly,
$\mathcal{D}(5)=5!-\sum_{k=1}^5\binom{5}{k}\mathcal{D}(5-k)=44$ $\mathcal{D}(6)=6!-\sum_{k=1}^6\binom{6}{k}\mathcal{D}(6-k)=265$

We divide in cases:

(Note: (a, b, c) means that is divided into 3 groups of a, b and c persons respectively)

• Case 1: They give one gift by pairwise. (2, 2, 2)

We can choose the first pair of ${6 \choose 4} = 15$ ways, the second pair of ${4 \choose 2} = 6$ ways and the third is determined.

Therefore, we obtain $15 \times 6 \times 1 = 90$ but is the same case if the pairs are (AB, CD, EF) and (AB, EF, CD), then we divide by 6. Then we obtain 15 ways.

• Case 2: (3, 3)

We can choose the first group of ${6 \choose 3} = 20$ ways and the second is determined. In each group, we have 2 forms in each group for give a gift. (If the people are A,B,C the 2 forms are A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A or A $\rightarrow$ C $\rightarrow$ B $\rightarrow$ A).

Therefore, we obtain $20 \times 4 = 80$ but is the same case if the groups are (ABC, DEF) and (DEF, ABC), then we divide by 2. Then, we obtain 40 ways.

*Case 3: (4, 2)

We can choose the pair of ${6 \choose 2} = 15$ ways and the other group is determined. In the 4-group, we have 6 distribution forms: A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D $\rightarrow$ A, A $\rightarrow$ B $\rightarrow$ D $\rightarrow$ C $\rightarrow$ A, A $\rightarrow$ C $\rightarrow$ B $\rightarrow$ D $\rightarrow$ A, A $\rightarrow$ C $\rightarrow$ D $\rightarrow$ B $\rightarrow$ A, A $\rightarrow$ D $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A and A $\rightarrow$ D $\rightarrow$ C $\rightarrow$ B $\rightarrow$ A.

Therefore, we obtain $15 \times 6 \times 1 = 90$ ways.

• Case 4: (6) in a circle

We obtain 5! = 120 ways, because if A is fixed, the other guys can permute of 5!.

(The cases with one-person-groups is not possible because this person don't give a gift with herself)

Finally, we obtain 15 + 40 + 90 + 120 = 265 ways.

Consider a set $J=\{1, 2, 3, . . ., n\}$ . We say that a permutation $\sigma$ of $J$ is chaotic when the $i^{th}$ element on the identity permutation is not the $i^{th}$ element on $\sigma$ .

That said, we have that the number $D_n$ of chaotic permutations of a set with $n$ elements is:

$D_n = n! \times \left[{\displaystyle \sum_0^{i=n}} \dfrac{(-1)^i}{i!}\right]$

so, knowing that the none of the 6 people can end with their own present, we have a chaotic permutation on a set with 6 elements, $D_6$ , if you may.

Then we have:

$D_6 = 6! \times \left[{\displaystyle \sum_0^{i=6}} \dfrac{(-1)^i}{i!}\right]$

$= 6! \left[\dfrac{1}{0!} - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dfrac{1}{4!} - \dfrac{1}{5!} + \dfrac{1}{6!}\right]$

$= 265$

There are $265$ different ways to distribute the presents.

if n things are arranged in a row then number of ways in which they can be arranged so that none of them occupy original place is

n!(1-(1/(1!))+(1/(2!))-..+(-1)^n(1/(n!)))

hence weget for n=6 265

The problem ask how many differents ways can we make a chaotic permuation of 6 elements.We have just to aplly the formula(Dn) N=6!(1/0!-1/1!+1/2!-1/3!+1/4!-1/5!+1/6!) N=265

Using derangement theorem

total ways = n!{ $\frac {1}{2!}$ + $\frac {1}{3!}$ + $\frac {1}{4!}$ + ................+ $\frac {1}{n!}$ }

where n! = n factorial

putting n = 6 we get total ways = 265

Technique: Derangement

The number of giving gift to someone, and since they are not allowed to receive their own gift, the number of ways to exchange is

$!6$

$=6!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+\frac{1}{6!})$

$=256$

This problem called Dearrangement problem we can solve this problem with recursive , that is : Dn = (n-1)*(Dn-1+Dn-2) with base case : D1 = 0 and D2 = 1 so we cand find that D6 is 265

Ok, I knew the formula for this but for getting it, we need to do it by Induction I guess. Suppose we do it for 2 people. The answer is obvious, its 1 way. We can also write 2 ways as $2! - [{2 \choose 1}\times (2-1)!] + [{2 \choose 2}\times (2-2)!]$ $\Rightarrow 2! - \frac {2!}{1!} + \frac {2!}{2!}$

Now, going on with 3 people, its 2 ways. We can also write 2 ways as $3! - [{3 \choose 1}\times (3-1)!] + [{3 \choose 2}\times (3-2)!] - [{3 \choose 3}\times (3-3)!]$ $\Rightarrow 3! - \frac {3!}{1!} + \frac {3!}{2!} - \frac {3!}{3!}$

Therefore, If we generalize for N people we get, $N! - \frac {N!}{1!} + \frac {N!}{2!} - \frac {N!}{3!}... \pm \frac {N!}{N!}$ where $\frac {N!}{R!}$ is no. of ways to distribute the gifts to each other such that atleast R out of N people gift themselves.

It is the factorial 6

The answer is simply the 6th subfactorial number: 265.