In a Youtube video on the channel @blackpenredpen, the number of  derangements of the word &quot;PURPLE&quot; is calculated as $$\frac{!6 \,- \,!5\, -\, !5\, - \,!4}{2!}$$ I don't understand two things:  Why is $!4$ being subtracted rather than being added, according to the Inclusion-Exclusion principle?  Why is the answer being divided by $2!$ despite the fact that the two Ps are accounted for already?
25622
I am wondering how to calculate the number of derangements for the word BOTTLE. I understand how to actually do the formula for derangements already. My issue is what do you do with repeated letters. Obviously, I will be over counting if I do the typical formula. Makes me think it is the number of derangements with the letter T in their original space, but I am not sure. Can anyone help, as I am wondering if I am supposed to use PIE to solve this. Thanks.
43482
I can't really understand how the recursive formula for derangements is derived, i.e I can’t see how the patterns of it occur.  From Wikipedia:      Suppose that there are $n$ persons who are numbered $1, 2, \ldots, n.$   Let there be $n $hats also numbered $1, 2, \ldots, n$. We have to find the   number of ways in which no one gets the hat having same number as   his/her number. Let us assume that the first person takes hat $ i$.   There are $n − 1$ ways for the first person to make such a choice.   There are now two possibilities, depending on whether or not person $i$   takes hat $1$ in return:      Person $i$ does not take the hat $1$. This case is equivalent to   solving the problem with $n − 1$ persons and $n − 1$ hats: each of the   remaining $n − 1$ people has precisely 1 forbidden choice from among   the remaining $n − 1$ hats (i's forbidden choice is hat 1). Person $i$   takes the hat $1$. Now the problem reduces to $n − 2$ persons and  $n − 2$    hats. From this, the following relation is derived:      $!n = (n - 1) (!(n-1) + !(n-2)). $          In this particular example I do not understand why we take care of the case when person $i$ takes hat $1$ or not. When I think about derangements I see that the first person has $n-1$ choices, so the rest of the people, but, and here's another conceptual problem, how do we know that if we continue to count like this   the last person, as it's only and one choice, won’t have a hat of the same number?  Also, how would one calculate derangements with the formula above? I am a visual learner, so if you can provide some kind of mental images to help the understanding of the concept I would appreciate more.  (I've checked if this question was a duplicate but i didn't find other questions asking for some kind of intuitive argument for derangements.)
75749
0 choices for the 1st person.  17 choices for the 2nd person (must exclude 1st and his/her two neighbours)   For 2 of these choices of 2nd person, there is one shared neighbour, so 15 remaining choices. (e.g. if they are numbered 1 to 20 in a circle, 1st person is #1, 2nd is #3, then people 20,1,2,3,4 are excluded).  For the other 15 choices of 2nd person, there are no shared neighbors, so 14 remaining choices.   So if order matters, total is $20 \cdot (2 \cdot 15 + 15 \cdot 14) $ but since order does not matter, divide by $3! = 6$ to account for the permutations in order of the 3 people.  So total = $20 \cdot \frac{2 \cdot 15 + 15 \cdot 14}{6}$  just redid it; does this make any sense?
74644
If $l$ and $n$ are any positive integers, is there a  proof of the identity     $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$   which uses the Inclusion-Exclusion Principle?  (If necessary, restrict to the case where $l\ge n$.)    This question is closely related to   and also
122842
I perfectly understand the permutations formula i.e. if you have $n$ things how many ways can you rearrange it if taken $k$ at a time (or if you have $k$ slots)? So you draw the following tree. And the formula comes out naturally. $$^nP_k = \frac{n!}{(n-k)!}$$  I get that it is including all of the duplicates, too. And to get rid of them we use the combinations formula: $$^nC_k = \frac{n!}{k!(n-k)!}$$ Can somebody explain why we have to divide by the &quot;number of ways to re-arrange the slots&quot; to get rid of the duplicates? I understand that it works and the division is used to scale a number down but I am not getting that &quot;aha moment&quot; of why we do it. Can somebody explain it?
30096
Verify that $4(29!)+5!$ is divisible by $31$  I know I have to use Wilsons theorem: $(p-1)!=-1\pmod p$ but I'm not really sure how to apply this theorem. Step by step explanation please? Thank you!
123574
I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4....  I understand that I should look at the reminders, and build pigeonholes from them.  If one of the numbers has a 0 reminder obviously the entire set is divisible, so the possible reminders go from 1 to (n-1). i have n numbers hence one of the reminders repeats. the sums of the reminders go from 1 to n*(n-1)....  And that's it...  Any and all help would be appreciated.    Of course I mean non empty set...
53476
Given $n$ objects with values $\{x_1,x_2,x_3,\dots,x_n\},$ and $m$ pairs $a_k = \{x_i,x_j\}$. Let $\{p_1,p_2,p_3,\dots,p_n\}$ be a permutation of objects. The question is to find number of permutations of objects such that none of the pairs $\{p_i,p_{i+1}\} \in a_k\ \forall i \in (1,n-1)$.  I tried to use inclusion-exclusion principle, first I took all the objects without any constraint. Then I picked number a pair $a_k$ and removed it from the total answer using inclusion-exclusion. But I was not able to solve it.  I don't assume the solution has a compact form, so I expect a procedure rather than an answer.
2928
If the all S,P are separated in the word MISSISSIPPI then the total possible arrangements are $k\frac {10!}{4!.4!} $ then value of k is? Now all S,P are separated so we can have slash method. Thus they can be placed alternatively in $6! $ ways and rest 5 can be placed in $5! $ ways. Thus we equate to get $$6!.5!=k\frac {10!}{4!.4!} $$  to get $k=13.7$ while $k=4/3$ .Where is my mistake Thanks
28149
• $C_n =$ this number of bit strings  • A binary string with no adjacent 0s is constructed by   Adding “1” to any string w of length $n-1$ satisfying the condition, or Adding “10” to any string v of length $n-2$ satisfying the condition   I still don't find that intuitive at all. Why adding up $C_{n-1} + C_{n-2}$ results in $C_n$? I have tried my best and asked my friends for help, but they find the formula unintuitive as well. Could anyone here come up with a clear explanation? Thanks!
38689
If I multiply $a$ by $0$, it means $a$ is added $0$ times, but I am not able to visualize $0$ times!
38863
The recurrence relation for Derangement is as follows:  Let $D_n$ denote the number of derangements of a set $\{1,2,3,\ldots,n\}$. Then,  $$D_n=(n-1)D_{n-1}+(n-1)D_{n-2}.$$  Can someone give an intuitive explanation on how we come to find this result?
21903
How many words with or without meaning can be made from the letters of the word CONCENTRATIONS by taking $4$ letters at a time?  There are  $14$ letters total present in the word. $4$ letters can be picked in $14\choose 4$ ways. $4$ letters can be arranged in $4!$ ways. So ideally answer has to be ${14\choose 4} * 4!$. But I know this answer is wrong because some letters are repeating. How do I solve this then? I appreciate any help.
33832
I was reading an example from my book, and I need further clarification because I don't understand some things. I'm just going to include the $f_1$ part in full detail because $f_2$ and $f_3$ are identical.   Consider the following problem.  Once upon a time, a band of seven pirates seized a treasure chest containing some gold coins (all of equal value). They agreed to divide the coins equally among the group, but there were two coins left over. One of the pirates took it upon himself to throw the extra coins overboard to solve the dilemma. Another pirate immediately dived overboard after the sinking coins and was never heard from again. After a few minutes, the six remaining pirates redivided the coins and found that there were three coins left. This time a fight ensured and one pirate was killed. Finally, the five surviving pirates were able to split the treasure evenly. What was the least possible number of coins in the treasure chest to begin with?   If x represents the original number of coins, then the first division can be represented by the congruence   $x \equiv 2 $ (mod $7)$ [I understand this part because originally we had 7 pirates and 2 left over coins]  The second and third division give the congruences  $x - 2 \equiv 3$ (mod $6$) and $x-2 \equiv 0 $ (mod $5$).  [The second division is the 2 coins that were thrown overboard, the pirate jumping into the ocean is the new mod, and there are 3 coins leftover. The third division is the original 2 coins thrown overboard, the 5 surviving pirates, and nothing is left over].  So the system of congruences is $x \equiv 2$ (mod 7), $x \equiv 5$ (mod 6), and $x \equiv 2$ (mod 5)  We solve the system by letting $x= 2f_1+5f_2+2f_3$  where $f_1,f_2$, and $f_3$ (to be determined soon ) satisfy   $f_1 \equiv 1$ (mod 7) $f_2 \equiv 0$ (mod 7) $f_3 \equiv 0$ (mod 7)  $f_1 \equiv 0$ (mod 6) $f_2 \equiv 1$ (mod 6) $f_3 \equiv 0$ (mod 6)  $f_1 \equiv 0$ (mod 5) $f_2 \equiv 0$ (mod 5) $f_3 \equiv 1$ (mod 5)  [Where are they getting this from?]  To compute $f_1$ we set $f_1 = 6 \times 5 \times b_1$ where $b_1$ satisfies the single congruence $ 6 \times 5 \times b_1 \equiv 1$ (mod 7)  [Ok. That 6 and 5 comes from mod 6 and mod 5, but why is there a 1 at the end of the equation?]  Note that $f_1$ is necessarily divisible by 6 and by 5 and is congruent to 1 modulo 7. Thus $f_1 \equiv 1$ (mod 7), $f_1 \equiv 0$ (mod 6), and $f_1 \equiv 0$ (mod 5)  To solve the congruence, reduce $ 6 \times 5$ modulo 7 to get $2b_1 \equiv 1$ (mod 7) [ $ 6 \times 5 = 30 $, so if I divide 30 by 7, I would get a remainder of 2 because $ 7 \times 4 = 28$ and $ 30-28=2$.   Note that $b_1 = 4$ is a solution. [WAIT! Where did that 4 come from? Now I'm really confused. What are the steps?]
82550
Find the number of ways a string of numbers (that may contain similar items) can be deranged, so that a number is not placed in the same place as it or its similar numbers were placed. For example, $\{0,0,0,1,1,1\}$ can be arranged in only one way, and that is $\{1,1,1,0,0,0\}$. $\{0,0,0,1,1,1,1\}$ cannot be arranged in any way. $\{1,2,2,14\}$ can be arranged in $2$ ways, i.e $\{2,1,14,2\}$, $\{2,14,1,2\}$. $\{1,1,2,2,14\}$ can be arranged in $5$ ways, i.e $\{2,2,1,1,14\}$, $\{14,2,1,1,2\}$, $\{2,2,14,1,1\}$, $\{2,2,1,14,1\}$, $\{2,14,1,1,2\}$.  Please do try and respond. Thanks in advance.
108191
I was looking at a 10x10 multiplication table, and I decided to count the unique products. There are 42 out of a possible 100 numbers represented. I had to wonder, why 42? I counted the 58 non-listed numbers -- most of them are either primes >10 or multiples of those primes. I couldn't figure out a satisfying reason like that for 75, 84, 96 and 98. I feel like the number 42 should be calculable from the natural log of 100 and 10, or something, but I can't really figure it out.  Also, I counted the frequency of all the numbers represented. They all have either 1, 2, 3, or 4 instances. The six numbers that have only 1 instance are all squares -- those of 1, 5, 7, 8, 9, and 10. This makes sense -- squares don't fall into that 4x5 = 5x4 redundancy. The 23 numbers with 2 instances are kind of the default I guess. The four with 3 are the remaining squares -- 4, 9, 16, and 36. 4 and 9 make sense to me, as they are squares within the basic range of the times table, so they are hit by themselves, their square root, and 1. I'm having trouble accounting for why 16 and 36 have three representatives. I'm also having trouble seeing the pattern (or patterns) in the numbers with four representatives.  I ultimately want to find a way to, given a times table of any size, calculate whether a given number will appear, and how many times.  Also, I'm pretty sure that for times tables 7x7 and below, more than half of the possible numbers are represented on the table, but for times tables above 7x7, less than half are represented. Why is 7 the turning point?
23966
One common math puzzle I've seen around asks for how many zeros are in the product of "100!"  Usually, the solution everyone gives goes something like try to match pairs of 5s and 2s that factor out of the numbers, which ends up being 24 zeroes (you can factor a 5 out of 20 of the numbers, and factor 2 5s out of 4 of the numbers; you can factor more than  24 2s out).   This however as far as I know gives the number of trailing zeroes at the end of the number, but does not account for the zeroes that are within the number. My question is, is this answer correct anyways? Can there be zeroes that aren't trailing that are inside? Why or why not and if there can be can we somehow figure out how many are within the product?   Thanks