Hello,

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

Thanks for the answers

boony

Printable View

- November 24th 2011, 03:18 PMboonyNumber 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 - November 24th 2011, 05:41 PMAnnatalaRe: 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 elements with exactly disjoint cycles:

Definition by recursion (defined only when ):

if :

if :

(That last one implies anytime the answer is .)

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