Results 1 to 2 of 2

Math Help - Number of permutations without a cycle of length k

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    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?

    Thanks for the answers


    boony
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    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 e elements with exactly c disjoint cycles:

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

    (That last one implies anytime e = c, the answer is 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. number of permutations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 13th 2011, 06:26 AM
  2. Replies: 1
    Last Post: October 23rd 2011, 07:14 AM
  3. Number of permutations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 18th 2011, 11:52 AM
  4. Number of lottery permutations?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 18th 2009, 01:00 AM
  5. cycle decomposition of permutations
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: September 9th 2009, 10:40 AM

Search Tags


/mathhelpforum @mathhelpforum