Hi all,


given (a1,...,an) formed by distinct letters, it's a well known problem to count the number of permutations with no fixed element.


I've been trying to solve a generalization of this problem, when we allow repetition of the letters.


I was able only to partially solve the problem when we have only repetition of a single letter.


If we have n letters and only one of them is repeated p times, then the number O(n,p) of permutations with no fixed element is given by the following recursive relation:


$O(n,0)=O(n,1)=\mbox{Derangement}(n)$


$O(p+1,p)=\dots=O(2p-1,p)=0, O(2p,p)=p!$


$O(n,p)={n-p\choose p} p!\sum\_{k=0}^p{p \choose k}O(n-p-k,p-k)$


Does anybody know where this problem have been studied before? Does anybody know a general solution for this problem?


Thanks in advance.



Derangements with repetition
The formula based on Inclusion-Exclusion for the usual number $D(n)$ of derangements of $n$ objects can be generalized. The result is the following.


Fix $k\geq 1$. Let $\mathbb{N}=\lbrace 0,1,2,\dots\rbrace$. For $\alpha=(\alpha\_1,\dots,\alpha\_k)\in\mathbb{N}^k$, let $D(\alpha)$ be the number of fixed-point free permutations of the multiset with $\alpha\_1$ 1's, $\alpha\_2$ 2's, etc. Write $x^\alpha = x\_1^{\alpha\_1}\cdots x\_k^{\alpha\_k}$. Then
 $$ \sum\_{\alpha\in\mathbb{N}^k} D(\alpha)x^\alpha =
 \frac{1}{(1+x\_1)\cdots (1+x\_k)\left(1-\frac{x\_1}{1+x\_1}-\cdots -
 \frac{x\_k}{1+x\_k}\right)} $$
 $$ = \frac{1}{1-\sum\_S
 (|S|-1)\prod\_{i\in S}x\_i}, $$ 
where $S$ ranges over all nonempty subsets of $\lbrace 1,2,\dots,n\rbrace$. 


This result appears as Exercise 4.5.5 in Goulden and Jackson, *Combinatorial Enumeration*. It can be used to obtain a lot of information about $D(\alpha)$.


