Derangements with repetition 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.
 A: For the particular case you asked about, in which we're computing fixed-point free permutations of the word 0...012...n (where 0 appears p times):
We choose the positions for the 0s in $\binom{n}{p}$ ways.  Given this choice, the permutations in question are equivalent to permutations of [n] in which the first n - p values are not fixed points.  The OEIS (specifically, sequence A047920) and/or a simple argument by inclusion-exclusion gives $\sum_{ j\geq 0} (-1)^j \binom{n - p}{j}\cdot (n-j)!$ for this value; the OEIS also gives $\sum_{j = 0}^{p} D_{n-j}\cdot \binom{p}{j}$ (where $D_m$ is a derangement number).
Another case that might be of interest is the case in which each letter appears the same number of times.  This is discussed in http://academic.csuohio.edu/bmargolius/homepage/dinner/dinner/cardentry.htm and has several associated OEIS entries (e.g., A000459, A059072 and A059073).
A: 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)$.
