Counting permutations without fixpoint

Question

Let $n$ be a positive integer.

Consider an ordered set $S_n = [1,2,3,...,n]$ where the $j$ th element from the left equals $j$.

Now consider a function defined on $S_n$ as a permutation of that set.

$$ f(S_n) = P(S_n) $$

Now iterating the function $f$ means iteratively rearranging the set like the permution $f$ does.

In notation

$$f^m(S_n) = f( f^{m-1}(S_n)) = P ( f^{m-1}(S_n)) = P^m(S_n)$$

--

Let $f$ be a "good" function IFF it does not map any $a$ in $S_n$ to it same position.

Let $G(n,b) $ denote the cardinality of functions $f$ for $S_n$ such that $f,f^2,...f^b$ are all good functions.

What is known about $G(n,b)$ ?

Can it be given in closed form ?

Does it have an integral representation ?

I can not help thinking about binomial and euler numbers but im confused. Maybe this is wrong, maybe not.

This seems to me like a very simple question, so maybe the answer is very well known and the result is named ?

Sounds to me like you are counting, with $G(n,m)$, the number of $n\times m$ Latin rectangles. — N. Shales, Apr 19 '17 at 17:12
No, it has to be less than the number of Latin rectangles since the iteration part is not taken into account. — mick, Apr 19 '17 at 17:32
It looks like Jorge's answer is on the right lines then. For $G(n,m)$ you want to count all permutations of ${1,2,\ldots , n}$ with cycles longer than $m$. — N. Shales, Apr 19 '17 at 18:48

Asinomás · Answer 1 · 2017-04-20T14:47:41.617

1

I think a good way to look at this is through the cycle representation of the permutation. What we want is the number of permutations such that each cycle has size at least $b+1$.

One possible way to count them is to run through all number partitions of $n$ into parts of size at least $b+1$ (so running through all possible cycle types). For each cycle type we can find the number of permutations with this simple formula.

Iterating through all possible number partitions can be done rather easily if we order them increasingly and go through them lexicographically.

edited Apr 20 '17 at 14:47

answered Apr 19 '17 at 16:57

Asinomás

105,651

Im not sure what to think, but it sounds intresting. Im No expert in the stuff you mention... – mick Apr 19 '17 at 17:36

Counting permutations without fixpoint

1 Answers1