Number of even letter permutations is divisible by $p$ Suppose that $w$ is a sequence of letters and $N(w)$ denotes the number of permutations of $w$'s letters such that no letter is in its original place. For example $N(ab)=1$ and $N(aa)=0$. 


*

*How can I compute $N(aabbccdd)$?

*If $p$ is a prime, $w$ has $2p+2$ letters and each of the $p+1$ letters appears exactly twice, why $p\mid N(w)?$


I have only little intuition how to solve this problem. By 2. I can see that $3\mid N(aabbccdd).$ Are there any better ideas that computer search for the case 1.?
 A: The second part is actually easier (although it took me a while to see it.)  In fact the use of a prime $p$ is a red herring.  If $w$ has $n$ distinct letters, each with the same multiplicity, then there are $n-1$ choices for the first letter, since it cannot be the first letter of $w$.  By symmetry, there are the same number of allowed words starting with each letter that is not $a$.  This means we can divide the number of allowed words into $n-1$ equal parts, so $n-1$ divides $N(w)$.
This kind of word can be thought of as a "generalized derangement".  We can solve this with inclusion-exclusion.  It might help if you've seen the problem of counting derangements first, that is, finding the number of permutations that do not have any fixed points.  This is usually the first example given in any explanation of the inclusion-exclusion principle.
To make things easier, let's first label the letters so that the two $a$'s, for example, are distinguishable.  Thus we'll consider a word $w$ to be a permutation on the set $a_1, a_2, b_1, b_2, \ldots, x_1, x_2$, where $x$ is the $n$th letter.  We'd like to count the number of "derangements", that is, words $w$ with no letter $s_1$ mapping to $s_1$ or $s_2$ and no $s_2$ mapping to $s_2$ or $s_1$.  Then we can divide by $2^n$ to count the arrangements with out the labels.
Consider the set $S$ of conditions $s_i \mapsto s_j$, where $s$ is one of the $n$ letters and $i,j = 1,2$.  We'll call $s_i$ the input, $s_j$ the output.  By inclusion-exclusion, $$\sum_{T \subseteq S} (-1)^{|T|} f(T)$$ is the number of derangements of  $w$, where $f(T)$ is the number of words obeying the conditions $T$, with no restriction on the other letters.  Note that some of these conditions will be incompatible, that is, $f(T) = 0$. For example, if $a_1 \mapsto a_2$ and $a_1 \mapsto a_1$ are both in $T$, then $f(T) = 0$.  But if the conditions are compatible, then $f(T) = (2n - |T|)!$ since the remaining letters can represent any bijection from the $2n-|T|$ remaining inputs to the $2n-|T|$ remaining outputs.  We can thus rewrite this as $$\sum_k (-1)^k N(k) (2n - k)!$$ where $N(k)$ is the number of compatible subsets of $T$ with size $k$.  So it remains to find $N(k)$.
For a $T \subset S$, let $i$ be the number of the $n$ distinct letters so that both labeled versions have their outputs fixed by $T$.  For example, if $T$ is the set of conditions $a_2 \mapsto a_1$, $b_1 \mapsto b_1$, $c_1 \mapsto c_2$,$c_2 \mapsto c_1$,$d_1 \mapsto d_1$,$d_2 \mapsto d_2$, then $i = 2$ for the $c$ and $d$ conditions.  Let's count how many compatible $T$ with $k$ letters that have a specified $i$.  First we choose one of ${n \choose i}$ subsets with $i$ letters, and then for each of these letters $s$ we can choose either the condition $s_1 \mapsto s_1$, $s_2 \mapsto s_2$, or $s_1 \mapsto s_2$, $s_2 \mapsto s_1$.  This gives a factor of $2^i$.  Now there are $k -2i$ more conditions to choose, each which must have distinct inputs.  Choose one of ${n - i \choose k-2i}$ set of letters $s$ to put conditions on; for each of these chosen letters $s$, we must choose between the four choices $s_i \mapsto s_j$, $i,j = 1,2$.  Putting this all together gives
$$\frac{1}{2^n}\sum_{k=0}^{2n} \sum_{i=0}^{\lfloor k/2 \rfloor} (-1)^k {n \choose i}2^i{n - i \choose k - 2i} 4^{k - 2i}(2n -k)!.$$
This sequence is in Sloane's.  More generally, Even and Gillis showed how to solve this problem for any word $w$ using Laguerre polynomials, and Jackson later showed this result can be found with Rook theory.  I'll let you Google these names to find the relevant references.
