# Number of permutations without a cycle of length k

Printable View

• Nov 24th 2011, 02:18 PM
boony
Number of permutations without a cycle of length k
Hello,

how many permutations in S_n are there without any cycle of length k?

Thanks for the answers

boony
• Nov 24th 2011, 04:41 PM
Annatala
Re: Number of permutations without a cycle of length k
From Wikipedia, the unsigned Stirling number of the first kind counts the number of permutations of \$\displaystyle e\$ elements with exactly \$\displaystyle c\$ disjoint cycles:

Definition by recursion (defined only when \$\displaystyle e\$ \$\displaystyle \geq\$ \$\displaystyle c\$ \$\displaystyle \geq\$ \$\displaystyle 1\$):
if \$\displaystyle e = 1\$: \$\displaystyle s(e, 1) = (e-1)!\$
if \$\displaystyle e > 1\$: \$\displaystyle s(e, c) = s(e-1, c-1) + s(e-1, c) * (e-1)\$

(That last one implies anytime \$\displaystyle e = c,\$ the answer is \$\displaystyle 1\$.)

EDIT: This doesn't actually answer your question, I now notice. (Doh) But the Wikipedia page should help, I think. To figure out the number of permutations without cycles of length k, it's probably easiest to calculate the number of permutations that do have cycles of length k (or of length at least k, depending on how it's worded), and subtract that from the total number of permutations.