Thread: 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

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