Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 14 down vote accepted

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)$.

share|improve this answer
add comment

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.