Happy Hour

The idea here is that when we first see this question, an "easier" alternative is to first consider when none of them are in the correct spot. Digressing, I would first like to consider this alternative.

~~~~~~~~~~~~~~~~~~~~~

In fact, I first came across a question as follows: What is the number of permutations such that if $n$ letters labelled $1, \ldots, n$ is placed randomly into $n$ letterboxes labelled $1, \ldots, n$ such that there is $1$ letter in every letterbox and letter $i$ is not in letterbox $i$ ?

Phrasing the above question in mathematical terms, it asks us to count the number of derangements. We will first obtain a recurrence for this problem and see how this ties back to our original problem. Also, we will denote the number of derangements of a set with $n$ elements as $!n$ . Basically, now we consider $!(n+1)$ . Suppose that letterbox $1$ receives letter $i \neq 1$ . There are $n$ ways for this to happen because there are $n$ possibilities for $i$ . Now we have 2 scenarios:

(i) If letterbox $i$ now receives letter $1$ , the set $\{1, i\}$ has itself been deranged; then this means that the remaining $(n-1)$ letters must also be deranged independently of what happens to letters $1$ and $i$ , so we have $!(n-1)$ ways such that this can happen.

(ii) If letterbox $i$ does not receive letter $1$ , we need to count the number of ways that the $n$ remaining letters can be ordered so that letter $1$ does not end up in letterbox $i$ , and for all $k \neq i$ , we have that letter $k$ does not end up in letterbox $k$ . However, notice that this is in fact equivalent to deranging $n$ letters, whence the number of ways it can happen is $!n$ .

So writing everything in mathematical symbols, we have:

$!(n+1) = n(!n + !(n-1))$ .

Also remember the starting values of $!0 = 1$ and $!1 = 0$ .

~~~~~~~~~~~~~~~~~~~~~

Back to the problem. As we have seen above, we have already solved the case when none of the people are at their correct desks. This is just $!6$ which can be calculated easily with the recurrence as $265$ .

We have still yet to consider the case when $1$ of them is in the correct spot. This is easy to implement. We use the same reasoning we have used in the "digression" above. Suppose $a$ is in seat $a$ (remark that there are 6 possible values of $a$ ), now, the remaining $5$ people cannot be in their designated seats since then they would violate the condition, whence $!5$ . Considering the different choices of $a$ , we easily see that the number for this case is $6 \times !5 = 6 \times 44 = 264$ .

In conclusion, the total number of ways is 265 + 264 = 529

The number of ways she could have got gentlemen's hat, without restrictions, are obviously $6!$ . In order to obtain the requested number, I've to subtract the number of ways she could got exactly $x$ gentlemen's hat incorrectly, with $x$ within 0 and 5. She can get exactly 0 gentlemen's hat incorrectly in $1$ ways. She can get exactly 1 gentlemen's hat incorrectly in $0$ ways. She can get exactly 2 gentlemen's hat incorrectly in $\displaystyle \binom{6}{2}$ ways. She can get exactly 3 gentlemen's hat incorrectly in $\displaystyle 2\binom{6}{3}$ ways because when you've chosen the three hat that has to be got incorrectly, you've $2$ ways to permute them without making any of them matched with the correct person. She can get exactly 4 gentlemen's hat incorrectly in $\displaystyle 9\binom{6}{4}$ ways because when you've chosen the three hat that has to be got incorrectly, you've $9$ ways to permute them without making any of them matched with the correct person. Thus, the total number of ways she can got exactly 0,1,2,3 or 4 gentelmen's hat uncorrectly is $\displaystyle1+0+\binom{6}{2}+2\binom{6}{3} +9\binom{6}{4}$ and, making the succitate subtraction, we get the solution, that is $\displaystyle 6!-\left[ 1+0+\binom{6}{2}+2\binom{6}{3} +9\binom{6}{4} \right]$

Let $!n$ denote the number of ways to arrange $n$ numbers such that the $i$ th number is not $i$ . Using the principle of inclusion-exclusion, we see that this is $n!-\binom n1\cdot(n-1)!+\binom n2(n-2)!+\cdots+\binom nn$ . (Counting this way, each permutation with $i$ fixed points, $i>0$ is counted $\binom i0-\binom i1+\binom i2-\cdots +\binom ii=0$ times.) Our desired answer is then $!6+6\cdot!5=720-720+360-120+30-6+1+\\6(120-120+60-20+5-1)=\boxed{529}$ .

Derangement is the arrangements of none of the objects stay in their original position. Derangement can be defines as $!n$ = $\frac{n!}{e}$ where the natural logarithm $e = 2.718281828$

Next, the number of ways such that none of them are sit in the correct spot: $!6$ = $\frac{720}{2.718281828}$ = $265$

Then, such that at most 1 of them is in the correct spot: $6 \times !5$ = $6 \times 44 = 264$

Hence, $265 + 264 = \boxed{529}$

We are looking for the number of permutations with 0 or 1 fixed points on a set with 6 elements. A permutation with no fixed points is called a derangement and I will use $!n$ to refer to the number of derangements on a set with $n$ elements. This can be calculated with $!n = (n-1)(!(n-1)+!(n-2))$ together with the starting values $!0 = 1$ and $!1 = 0$ .

We can split this problem up into two cases:

case 1: No Fixed Points

This is simply $!6 = 265$ .

case 2: One Fixed Point

We can choose any of the 6 elements to be our fixed point. Once that fixed point has been chosen, there are $!5$ ways of positioning the other 5 elements. Therefore, the number of 6 element permutations with 1 fixed point is $6 * !5 = 6 * 44 = 264$ .

The final answer is the sum of these two values: $265 + 264 = \boxed{529}$ .

We have 6 persons and their corresponding hats, so we have to basically derange these hats so that none or at maximum one gets his own hat. It can be solved via two ways but basic remains the same: 1. Basic Approach: We have a total of 6! possible ways to distribute the hats. But our concerned no ways have to exclude the number of ways in which we can distribute the hats all right( =1 ), give 4 persons right hats(= ${6 \choose 4}*1$ ), give 3 persons their hats(= ${6 \choose 3} \times 2$ ) and also give 2 person their right hats( = ${6 \choose 2} \times 9$ . (9= $3 \times {3 \choose 1}$ is number of ways to give 4 person incorrect hats (we can give any one persons three wrong hats and select any of three persons and give the hat of person earlier selected and then we only one way to give rest 2 persons to give incorrect hats) ) =720-1-15-40-135=529 2. Derangement Formula: a) Give all incorrect hats = $6! \times (1-1+{\frac 1 {2!}}-{\frac 1 {3!}}+{\frac 1 {4!}}-{\frac 1 {5!}}+{\frac 1 {6!}})$ b) Give one person correct hat and other incorrect ones = ${6 \choose 1} \times 5! \times (1-1+{\frac 1 {2!}}-{\frac 1 {3!}}+{\frac 1 {4!}}-{\frac 1 {5!}})$

Total=a)+b)=264+265=529

Let there be $n$ gentlemen visiting the club. Let $S_n$ denote the number of ways such that every gentlemen receives the wrong hat.

There are $n!$ ways for the lady to distribute the hats randomly. Next, we must subtract the ways such that one person receives the correct hat. There are $\binom{n}{1}(n-1)!$ ways to do so. However, we have undercounted the number of ways that two people received the correct hat (once in $n!$ and twice in $\binom{n}{1}(n-1)!$ , so we must add $\binom{n}{2}(n-2)!$ back in. Similarly, we now have overcounted the number of ways for three people to get the correct hat. Continuing this process, we find that

$S_n=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-...+(-1)^n\binom{n}{n}0!$

or

$S_n=\displaystyle\sum^{n}_{k=0}(-1)^k\binom{n}{k}(n-k)!$

In this problem, if no gentlemen receives the correct hat, there are $S_6$ ways to do so. If one gentlemen receives the correct hat, there are $\binom{6}{1}$ ways to choose that person, and then $S_5$ ways to distribute the remaining hats. Hence, our answer is $S_6+6S_5=\boxed{529}$ .

First we consider cases "(A) all gentlemen got wrong hats" and "(B) 1 gentleman got his hat".

(A) :

It is clear from the problem statement that the hats must be 'passed' in loops formed by 2 or more people, i.e. each person takes the hat of 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 _4)(^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 _4)(^4 C _2)}{3!})(1!)(1!)(1!) = 265$ .

(B) :

First we note that to choose the 1 gentleman who got his hat right, we have 6 choices, then to shuffle the remaining 5 hats, similarly, we consider cases of loops :

• (1) 1 loop of 5

• (2) 1 loop of 3, 1 loop of 2

Case (1):

• Number of ways to choose loop of 5: 1

• Number of ways to choose order of cycle of loop of 5: 4!

Case (2):

• Number of ways to choose loop of 3: $^5 C _3$ (Note that loop of 2 will be fixed from this already)

• Number of ways to choose order of cycle of loop of 3: 2!

• Number of ways to choose order of cycle of loop of 2: 1!

Hence, we conclude that the total number of ways = $6[(1)(4!) + (^5 C _3)(2!)(1!)] = 6[44] = 264$ .

Conclusion :

Total ways = 265 + 264 = 529.

Let's first investigate the case when none of the officers are at their original positions. We are simply looking for the number of permutations of a $6$ -element set such that no element is in its original position. This is also known as a derangement . For a $6$ -element set, the number of derangements is $D_6= 6! \left ( 1-\frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} \right ) = 255$ Let's now see the case when exactly $1$ officer is at his own table. We can fix this officer in $\binom{6}{1}= 6$ ways. We now need to permute the remaining $5$ officers such that no officer is in his original position. The number of such derangements is $D_5= 5! \left (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} \right ) = 44$ Thus this case produces $44 \times 6= 264$ more results. Summing them up, our total answer is $255+264= \boxed{529}$ .

If no people are in the right seat, then each possibility is a derangement . There are 265 derangements of 6 elements.

If one person is is in the right seat, the number of ways to seat the other 5 people is the number of derangements of 5 elements, which is 44. There are 6 ways to choose who is in the right seat.

The answer is $265+6\cdot 44=529$ .

The desired number of ways for the lady to deliver the hats is equal to the number of ways in which she gets none of the hats correct plus the number of ways in which she gets exactly one hat correct.

The first case is simply !6, the derangements of 6 elements. A derangement !n calculates the number of partitions of $n$ terms in which no term has its original position. We calculate !6 with the formula !6=[6!/e]=265.

For the second case, we have $6$ ways to choose the one hat that is delivered correctly, and !5 to distribute the remaining hats. It follows that there are 6*[5!/e]=264 configurations for this case.

Hence, the total number of ways is 265+264=529.

A derangement is a permutation of the elements of a set such that none of the elements appear in their original position. In terms of derangements, the given problem is asking for the number of derangements of 6 elements (the cases where no hat is correct), plus 6 times the number of derangements of 5 elements (since there are 6 ways for the lady to get exactly 1 hat correct, and for each of these 6 choices of the correct hat, the number of ways to distribute the remaining 5 hats is the number of derangements of 5 elements)

One can compute that the number of derangements of 6 elements is 265, and the number of derangements of 5 elements is 44. So the answer to the given problem is 265 + (6*44), which is 529.

There are two methods that one can use to compute these derangements. They can easily be found online, and I will not repeat them here. One involves the inclusion-exclusion principle, and the other involves writing a recursive formula for the number of derangements.

Recall the inclusion-exclusion formula for the number of derangements on $n$ elements: $D_n = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + \frac{(-1)^n}{n!} \right)$ . We easily calculate $D_3 = 2$ , $D_4 = 4D_3 + 1 = 9$ , D 5 = 5D 4 - 1 = 44) and $D_6 = 6 D_5 + 1 = 265$ .

There are exactly $265$ ways to get no hats correct, and $6D_5 = 264$ ways to get exactly one correct (pick one lucky gentleman and then get the other five wrong), for a total of $529$ .

There are $!6$ ways to get $0$ hats correct, and $6 \times !5$ ways to get $1$ hat correct. Summing gives $529$ .

At most 1 hat correct means that none of the hats or exactly 1 of the hats came back to its owner

There are !6 (subfactorial)=265 ways that none of the hats will come back to its owner. Now, the number of ways there are for the lady to get 1 gentlemen’s hat correct is 6*(!5)=264. That's because if we fix that the owner number 1 received his hat, there are !5 ways to derange the other five hats. We can do it 6 times since there are 6 owners. So 265+264=529.

This is simply $!6+6\times!5=\boxed{529}.$

To solve this problem, the arrangement could have one of two possible properties: 1, Everybody has moved desks 2. One person has the same desk, everybody else has moved. For 1, we need to find the derangement of six items (i.e. people), which comes to 265. Then, for 2, we need to find the derangement of five items, because we are ignoring the person staying in the same place for now, which is 44. Now, because any of the six people can stay in the same place, we multiply this number by 6.

So in total, there are $529$ possible arrangements.

There are two cases to look at: (1) everyone is in the wrong spot or (2) one person is in the right spot.

Case 1 is just the number of derangements for six objects which is $!6=265$

Case 2 is six times the number of derangements for 5 objects which is $6\cdot!5=6\cdot44=264$ . This works because each of the six could be the one in the right spot and then the other 5 need to be in the wrong spot.

In total we then have $265+264=\boxed{529}$ ways.

Using derangement principal......the value should be D(6) + 6*D(5) = 529.

By the Inclusion-Exclusion principle we have the numbers of permutations of {1,2,...,n} that have no fixed point is $n!\sum {r=0}^{n} \frac{(-1)^r}{r!}$ Case 1: The set {1,2,3,4,5,6} has no fixed point. There are $6!\times \sum {r=0}^{6} \frac {(-1)^r}{r!}=265$ ways. Case 2:The set {1,2,3,4,5,6} has only one fixed point. There are 6 ways to choose this fixed point i. The set {1,2,3,4,5,6}{i} has no fixed point. In this case,there are $6\times 5!\sum_{r=0}^{5}\frac{(-1)^r}{r!}=264$ Answer: 264+265=529

The number of derangements of $n$ objects is equal to the number of ways $n$ objects can be given to their $n$ owners so that none of the owners get their own object; they get someone else's. The number of derangements of $n$ objects can be expressed as $!n$ (which looks kind of like $n!$ , the number of ar rangements of an object).

The number of derangements of 6 objects is equal to 265 (we can calculate this by listing the cases out, which would take forever, using a very complicated formula, which I will not explain (but feel free to look it up yourselves), or typing in '!6' into WolframAlpha or something of the sort.) This is equal to the number of ways that the six people can sit at their six desks such that each person does not sit at his/her own desk. (Do you see why?)

We also want to calculate the number of ways that exactly one person sits at his/her own desk. Let's say that Sue sits in her own desk and the other five people do not. The number of ways this can happen is equal to $!5$ (the number of derangements of five objects), which turns out to be 44.

However, the 44 only accounts for the number of ways that Sue sits in her correct spot and the rest of the people do not. There are 44 more ways for Sam to sit in his desk and the others don't, 44 ways for Pete, and so on. This is a total of $44\cdot6$ .

Adding up our values, we have $265+44\cdot6=265+264=\boxed{529}$

Number of ways that no one is sitting at correct spot is simply derangment of 6, which is $!6 = 265$

Number of ways that one person is sitting at correct spot while no one else is, can be counted by putting that person in her spot and counting the derangement of 5. There are 6 persons thus we will get one such derangement of 5 for each one of them. Thus we get $6 \times !5 = 6 \times 44 = 264$

Therefore, we get total answer as $265 + 264 = \boxed{529}$

Reference Link: http://en.wikipedia.org/wiki/Derangement#Counting_derangements

If no one in the correct sit, then total possibilities is $6! \times [\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}]=265$ . If only one in the correct sit, then total possibilities is $6\times 5! \times [\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}]=264$ . So total possibility is $529$

Total number of ways of distributing 6 hats among the gentlemen = 6! = 720.

Number of ways of distributing 6 hats such that everyone gets their respective hat = 1.

Number of ways of distributing 6 hats such that exactly 4 of them get their respective hat (6C4)*9=135.

Number of ways of distributing 6 hats such that exactly 3 of them get their respective hat = (6C3)*2 = 40.

Number of ways of distributing 6 hats such that exactly 2 of them get their respective hat = (6C2)*1=15.

Therefore, number of ways of distributing hats such that at most 1 gentlemen gets correct hat = 720 – (135 + 40 + 15 +1) = 529

Note: Multiplication factor 9, 2 and 1 are basically the number of ways 4, 3 and 2 persons hat distributed among them such that nobody gets their respective hat.

Total number of ways of distributing 6 hats amongst the people =6!=720
Multiplication by 9,2,1, 0, 1 are the number of ways 4,3 2, 1 and 0 persons hat distributed among them and no one gets their own hat.

Number of ways of distributing hat such that all get their own hat $=6C6 * 1 = 1$ .
Number of ways of distributing hat such that 5 get their own hat $= 6C5*0 = 0$ .
Number of ways of distributing hat such that 4 get their own hat $=6C4*1=15$ .
Number of ways of distributing hat such that 3 get their own hat $=6C3*2=40$ .
Number of ways of distributing hat such that 2 get their own hat $=6C2*9=135$ .

Therefore the number of ways such that at most 1 person gets his hat correctly=720-(135+40+1+15)=529.