# Thread: Number of permutations without a cycle of length k

1. ## Number of permutations without a cycle of length k

Hello,

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

boony

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