Two letters need to be delivered to each of $n$ houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter?  Right now I have the total number to deliver two letters to $n$ houses as $N = \frac{(2n)!}{2^n}$. I know derangement is equal to $N - N_1 + N_2 - N_3 + ... + (-1)^kN_k$. I have $N_1 =\displaystyle{n \choose 1}\bigg[\frac{(2n-2)!}{2^{(n-1)}}\bigg]$ but I can't seem to find a pattern or find a solution.
122358
Two letters need to be delivered to each of n houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter?    I got stuck and don't now how to progress. Can someone provide hint?   1) $(2n)!/2^n$ is the number of all possible onto functions from our domain of houses to the codomain of letters.  2) Let $A_i$ be property that two delivered letters are correct. $ |A_1'   \cup A_2'   \cup...  \cup A_n'|=(2n)!/2^n-|A_1   \cap A_2   \cap...  \cap A_n|$    I tried everything I could come up with but I cannot find $|A_1   \cap A_2   \cap...  \cap A_n|$. I feel like I need to find union first but in order to do that I should find intersection. Really confused. Any hint would be appreciated.   Edit: Corrected mistake in the equation.
52953
Let $[n]$ be a set with $n$ elements. Two derangements of this set, $\sigma$ and $\psi$ satisfy the next condition.   $\forall i\in [n], \sigma(i)\neq \psi(i)$   This condition makes $\sigma$ also a derangement of $\psi$. A double derangement of $[n]$ is an (ordered) pair {$\sigma;\psi$} such that $\forall i\in[n], \sigma(i)\neq\psi(i)$. How many double derangements can there be?  I have been thinking about this problem since I learned about derangements. I tried to solve this problem by finding a recurrence formula and using inclusion–exclusion principle, but figured out that it is too complicated to solve by this method. Are there any better ideas to solve this problem?
113768
The number of words that can be made by permuting the letters of MATHEMATICS is   $1) 5040$  $2) 11!$  $3) 8!$  $4) 4989600$  First of all I do not understand the statement of the problem, I would like if some one tell me with an example.
40785
Looking please for any help! John emailed 128 people to invite them to the restaurant's inauguration party. He asked these guests to send the email to 5 others in exchange for participation in a lottery where a free meal for two is won. Based on the assumptions made below, how many of those who received the email are expected to come to the party? Assumptions •half of the 128 people emailed the other 5. •1/4 of these sent the email to 5 others. •1/8 of these sent the email to 5 others •1/16 of these sent the email to 5 others. • No one received the email more than once. • 10% of those who received the email will go to the party. My attempt was the following: 128: 2= 64    64+5=69 128:4= 32      32+5=37 128: 8= 16    16+5=21 128:16= 8      8+5=13 10% of 140= 14 person 14 person will go to the restaurant’s inauguration party.
82160
If we reverse the digits of $12$ we will get $21$. $12^{2}=144$. If we reverse its digits we will get $441$ which is $21^{2}$.  Here is the puzzle. How many such two digit numbers are there? Digits must be different.  We got an algebraic method to solve it if the square is a three digit number.It given here :  Let $a&gt;b$  $(10a+b)^{2}=100x+10y+z$ and $(10b+a)^{2}=100z+10y+x$  Difference between these two equations will lead to $a^{2}-b^{2}=x-z$  $x-z \leq 8$.Then  $a^{2}-b^{2} \leq 8$.  Since squares are of three digits $a &lt;4$.But since $a&gt;b ,a \neq 1$.  $b=1 \Longrightarrow a^{2} \leq 9$.Then $a=1,2,3$ but only possibilities are $2 $ and $3$.  $b=2 \Longrightarrow a^{2} \leq 12 \Longrightarrow a= 1,2,3$. But possibility is $a=3$. So next such pair will be $13,31$.  Higher values of $b$ will not work since $a$ cannot exceed 3. This is an explanation we obtained from a mathematics group.It works well if the square is a three digit number.What will happen if square is a 4 digit number... Or if we try to extend this problem for numbers having more than two digits ?
81042
let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people  determine $A_1, A_2, A_3$  So I have  $A_1 = 1$ way $A_2 = 4$ way $A_3 = 12$ way  But I am not sure if this is right... Can anyone confirm?  edit:  My way of getting this is  $A_1 = 1 $ because {P1} only has 1 way to sort  $A_2 = 4$ because {P1,P2} = {P1,P2},{P2,P1},{P1P2},{P2P1}  etc.
26561
I know that the partition of $2n$ items into $n$ pairs has something to do with double factorial, but I am not sure how many possibilities we exactly have.   We can choose such a partition into pairs by first choosing $n$ elements to be in one half and the remaining $n$ in the other half, which gives ${{2n} \choose n}$ possibilities. Then we can take a permutation of both sets and match them accordingly.   This gives $${{2n} \choose n} n! n!=\frac{(2n)! n! n!}{n! n!}=(2n)!$$ possibilities. But with this we overcount, since we do not want the pairs to be ordered. Each of the $n$ pairs is counted twice, wherefore we have to divide by 2 for every pair, hence $\frac{(2n)!}{2^n}$?   Well, another possiblity to do that is just to iteratively pick $2$ elements among the remaining ones, which gives ${{2n} \choose 2} {{2n-2} \choose 2} \dotsb {4 \choose 2}$  I am not sure, but I do not think that this is the same and also, I do not see the connection to double factorial. Would be very glad if you could help me with these 3 possiblities.   Thank you.
77336
If each suit is represented then we will have two cards from one suit and one card each from the remaining suits. So I am counting the ways this can happen like so -  ${52 \choose 1}$ ways of selecting the first card.  ${12 \choose 1}$ ways of selecting a card from the same suit as the first.  ${13 \choose 1}$ ways of selecting a card for each of the 3 remaining suits.  So I have -  $${52 \choose 1}{12 \choose 1}{13 \choose 1}{13 \choose 1}{13 \choose 1}$$  Then I have the sample space as $52 P 5$ as we are counting with regard to order on the numerator so we need to do the same for the denominator.  So I have $$\frac{{52 \choose 1}{12 \choose 1}{13 \choose 1}{13 \choose 1}{13 \choose 1}}{52P5}$$  Does that look correct?
13511
I was reading upon Biham and Shamir's paper and a fact has been presented over there: if $ P_1 = \bar P_2$ and I choose a key $K_1 = \bar K_2$ then in that case  $$T_1 = DES(P_1, K_1)$$ $$T_2 = DES(P_2, K_2)$$  then $T_1 = \bar T_2$ . Does this hold for only that particular combination of S-box or it will be same for any S-box combination. I mean if I change S-boxes randomly then will it still be same?  Also there is one more thing mentioned on the paper, but I am not able to get it. PFB the image.   Here output $T$ will be $\bar T_2$ only if I $P_2$ was inserted with $\bar K$. And clearly I am entering $P_1$ (which is $\bar P_2$) hence the output can never be $T_2$. Please correct.
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.
79867
How many arrangement of the letters in MISSISSIPPI have at least 2 adjacent S's?  I was thinking that I can glue two of the S's together, so there will be 9 letters plus the special letter SS, and the number of arrangements will be $10!/(2!2!4!)$, this is not the correct answer, but what is wrong with my reasoning.  (the correct answer is $11!/(4!4!2!)-7!/(4!2!)\binom{8}{4}$, I understand the solution)
119892
i know that|$S_n$|=$n!$ and |$A_n$|= $\frac{n!}{2}$ but i'm not sure where to go from there. Thanks.
75265
This is not for homework, but I am not great at counting arguments and would like some feedback.  The question asks     Let $n \in \mathbb{N}$. How many $\alpha \in S_n$ are there such that $\alpha^2 = 1$?   I know that, if $\alpha^2 = 1$, then either $\alpha = 1$ or $\alpha$ is the product of disjoint transpositions.  If $\alpha = (i, j)$ is a single transposition, then there are $\frac{1}{2^1 \cdot 1!} \binom{n}{2}$ such $\alpha$ (the $2^1$ and $1!$ are put in the denominator to help in noticing the pattern later).  If $\alpha = (i, j)(k, l)$ is the product of $2$ disjoint transpositions, then there are $\frac{1}{2^2 \cdot 2!} \binom{n}{2} \binom{n-2}{2}$ such $\alpha$, where the $2^2$ appears in the denominator to account for the cyclic permutations of each transposition, and the $2!$ appears to account for the permutation of the transpositions themselves.  If $\alpha$ is the product of $3$ disjoint transpositions, then there are $\frac{1}{2^3 \cdot 3!} \binom{n}{2} \binom{n-2}{2} \binom{n-4}{2}$ such $\alpha$.  Extrapolating from this, I find that the total number of $\alpha \in S_n$ such that $\alpha^2 = 1$ is $$ 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \frac{1}{2^i \cdot i!} \prod_{k=0}^{i-1} \binom{n-2k}{2}. $$  Does this look OK?  It looks like a rather ugly answer to me, so I have my doubts.  Any input would be welcomed.
114348
Problem Statement:- The number of zeroes at the end of the integer   $$100!-101!+\ldots-109!+110!$$   I am having a bit of a trouble in thinking how do I proceed. A little push in the right direction would be appreciated.   And if you are posting a full solution do use the spoiler tag, as sometimes I cant stop myself from seeing the whole solution and lose the chance of thinking through it by myself with a push in the right direction from you guys.  Also, I dont know whether I am using the right tag feel free to correct it if its wrong.
32480
Say, we have 4 red balls, 4 blue balls, 4 green balls, 4 yellow balls. How many ways are there to form a sequence of 10 balls such that every color of ball occurs at least twice?  My thought: r = red b = blue g = green y = yellow * = undetermined  Every arrangments should in this form: rrbbggyy**  Case 1: two * are same  $\frac{\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{1}10!}{4!2!2!2!}$  Case 2: two * are different  $\frac{\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{2}\binom{4}{2}10!}{3!3!2!2!}$  Result = Case 1 + Case 2  Any suggestions would be appreciated!
116273
In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three blanks. The columns are occupied by the number chosen from 1-9 (only nine), 10-19 (ten), 20-29 ... 70-79 and importantly 80-90 (eleven). Numbers in columns are ordered from top to bottom.  How many possible unnumbered card layouts are there?  How many possible numbered cards are there?  I have started to approach this problem by first choosing the blanks for the first two rows and then attempting to work out a compensating row. This was hard.  Next I begun to understand that there were a number of equivalence classes as columns could be reordered for the purposes producing different layouts.  Next I looked into the most convoluted card which had five numbers followed by four blanks in the first row and four blanks followed five number in the second. This satisfied the "no blank column" requirement. Now the final row could be arranged however it wanted, though there was one confusing overlap to deal with.   I considered another convoluted card which had as many columns of three as possible. It turns out it's possible have a maximum of three columns of three which also gives rise to the maximum of six columns of one. It also turns out you can have a maximum of six columns of two. I think the starting point might be to determine the classes of card initially by column combinations and then permute them.  Having gotten all muddled by the layouts, I turned to the numbers. With a single number, it was one of 9, 10 or 11 depending on the column and that was easy. For the two number case, let's say with a column of ten, the first ($i$) was chosen from 9 and the next from $10-i$. It suddenly occurred to me that it was just combinations, phew. How to fit that with the whole business of column choice lost me.  It seems possible that for each possible "set" of columns, there will be a way of determining the distribution of possible first columns and adding in an appropriate factor for the number combinations.  Frankly, it's all getting bigger than my coffee table.   Any simplifications from higher maths I'm missing?
714
What is wrong with my method of find the probability of a 2 pair?  For the first card we have 52 choices, one this is picked( call it A) we have 3 choices(different suite than A but this same value) for the second card, ( lets call this card B). Now we have AB, to we have to throw away 2 more cards so we don't have 3 of a kind or a four of a kind. Therefore one our third card we have 48 choices and on our fourth card we have 3 choices again similar to above.  On our last card we only have 44 choices left. So the probablity of getting a 2 pair should be (52*3*48*3*44)/(52 choose 5).  But this isn't correct.     Note: I edited this to "2 pair"; the original version was wrong.