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.

Printable View

- Jan 21st 2010, 06:45 PMGodwinCircular 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. - Jan 22nd 2010, 01:50 AMemakarov
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!).

- Jan 22nd 2010, 05:13 AMGodwin
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!(Clapping)