Results 1 to 3 of 3

Math Help - Circular Permutations of a Multiset

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    2

    Circular Permutations of a Multiset

    Hi there. Can anyone prove the following:
    S is a multiset with k types, each repeating in n_1, ...., n_k times. n_1 = 1. n = n_1 + n_2 + .... + n_k. Prove that S has

    {n!} / {n_2! n_3! .... n_k!}

    circular permutations.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,515
    Thanks
    769
    I am not sure about circular permutations, but this problem seems similar to the well-known question about the number of anagrams (i.e., all permutations) of a word. For example, "mathematics" has 11 letters, so if all of them were different, there would be 11! permutations. However, it has 2 a's, 2 t's and 2 m's. Therefore, those 11! permutations have to be broken into equivalence classes. If two words belong to the same class, they may differ by the order of a's, t's and m's -- they are still the same word because we don't distinguish two a's. Each class has 2!*2!*2! words, so the number of classes is 11!/(2!*2!*2!).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    2
    I have made mistake in the problem! n = n_2 + .... n_k ,i.e. there is no n_1 there.
    I just noticed it when rereading the problem a second ago.
    Now it makes sense. If u have a circular permutation, then the total of the linear permutations must be divided by n+1, the total number of elements. This is because every single circular arrangement corresponds to n+1 linear ones!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Circular Permutations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 20th 2011, 06:25 AM
  2. circular permutations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 26th 2011, 11:39 AM
  3. circular permutations
    Posted in the Statistics Forum
    Replies: 1
    Last Post: January 16th 2011, 07:49 AM
  4. Multiset
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 21st 2009, 03:41 AM
  5. Multiset
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 27th 2008, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum