Element structure of symmetric groups - Revision history

Vipul: /* Based on number of fixed points */

2013-07-23T19:01:25Z

Based on number of fixed points

← Older revision		Revision as of 19:01, 23 July 2013
Line 106:		Line 106:
	{{further\|[[probability distribution of number of fixed points of permutations]], [[expected number of fixed points of permutation equals one]]}}		{{further\|[[probability distribution of number of fixed points of permutations]], [[expected number of fixed points of permutation equals one]]}}

	We can partition the set <math>S_n</math> based on the number of fixed points of each permutation. Since the number of fixed points depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in <math>S_n</math>. The number of fixed points can be any number <math>k</math>, with <math>0 \le r \le n</math> and <math>r \ne n - 1</math>.		We can partition the set <math>S_n</math> based on the number of fixed points of each permutation. Since the number of fixed points depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in <math>S_n</math>. The number of fixed points can be any number <math>r</math>, with <math>0 \le r \le n</math> and <math>r \ne n - 1</math>.

	* The number of elements with <math>r</math> fixed points is <math>\binom{n}{r}D_{n-r}</math> where <math>D_{n-r}</math> is the [[derangement number]], i.e., the number of permutations on a set of size <math>n - r</math> with no fixed points. {{further\|[[probability distribution of number of fixed points of permutations]]}}		* The number of elements with <math>r</math> fixed points is <math>\binom{n}{r}D_{n-r}</math> where <math>D_{n-r}</math> is the [[derangement number]], i.e., the number of permutations on a set of size <math>n - r</math> with no fixed points. {{further\|[[probability distribution of number of fixed points of permutations]]}}

Vipul: /* =Case n = 3 */

2013-07-23T18:35:18Z

=Case n = 3

← Older revision		Revision as of 18:35, 23 July 2013
Line 79:		Line 79:
	\|}		\|}

	====Case <math>n = 3</math>===		====Case <math>n = 3</math>====

	{{#lst:element structure of symmetric group:S3\|conjugacy class structure}}		{{#lst:element structure of symmetric group:S3\|conjugacy class structure}}

Vipul: /* Particular cases */

2013-07-23T18:02:50Z

Particular cases

← Older revision		Revision as of 18:02, 23 July 2013
Line 58:		Line 58:
	! Degree !! Number of conjugacy classes !! List of conjugacy class sizes !! Pairs of (partition,conjugacy class size) !! More details		! Degree !! Number of conjugacy classes !! List of conjugacy class sizes !! Pairs of (partition,conjugacy class size) !! More details
	\|-		\|-
	\| 1 \|\| 1 \|\| 1 \|\| ~~<math>~~(1,1)~~</math>~~ \|\| --		\| 1 \|\| 1 \|\| 1 \|\| (1,1) \|\| --
	\|-		\|-
	\| 2 \|\| 2 \|\| 1,1 \|\| ~~<math>~~(2,1), (1+1,1)~~</math>~~ \|\| --		\| 2 \|\| 2 \|\| 1,1 \|\| (2,1), (1+1,1) \|\| --
	\|-		\|-
	\| 3 \|\| 3 \|\| 1,2,3 \|\| ~~<math>~~(1+1+1,1), (3,2), (2+1,3)~~</math>~~ \|\| [[element structure of symmetric group:S3#Interpretation as symmetric group\|link]]		\| 3 \|\| 3 \|\| 1,2,3 \|\| (1+1+1,1), (3,2), (2+1,3) \|\| [[element structure of symmetric group:S3#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| ~~<math>~~(1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)~~</math>~~ \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]		\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| (1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8) \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| ~~<math>~~(1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),~~</math>~~<br~~><math~~>(3+1+1,20), (5,24), (4+1,30)~~</math>~~ \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]		\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| (1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),<br>(3+1+1,20), (5,24), (4+1,30) \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]		\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]

Vipul: /* Particular cases */

2013-07-23T18:02:05Z

Particular cases

@@ Line 78: / Line 78: @@
 | 10 || 42 ||  1, 45, 240, 630, 945, 1260, 3150, 4725, 5040, 6048, 8400, 18900, 18900, 22400, 25200, 25200, 25200, 25200, 50400, 50400, 50400, 56700, 56700, 56700, 60480, 72576, 75600, 86400, 90720, 120960, 120960, 151200, 151200, 151200, 172800, 181440, 201600, 226800, 226800, 259200, 362880, 403200 || Too long to list || [[element structure of symmetric group:S10#Interpretation as symmetric group|link]]
 |}
 ==Groupings of conjugacy classes==

Vipul at 03:32, 16 May 2011

2011-05-16T03:32:52Z

← Older revision		Revision as of 03:32, 16 May 2011
Line 30:		Line 30:
	\|-		\|-
	\| 8 \|\| 40320 \|\| [[symmetric group:S8]] \|\| [[element structure of symmetric group:S8]]		\| 8 \|\| 40320 \|\| [[symmetric group:S8]] \|\| [[element structure of symmetric group:S8]]
			\|-
			\| 9 \|\| 362880 \|\| [[symmetric group:S9]] \|\| [[element structure of symmetric group:S9]]
			\|-
			\| 10 \|\| 3628800 \|\| [[symmetric group:S10]] \|\| [[element structure of symmetric group:S10]]
	\|}		\|}
	==Conjugacy class structure and cycle type==		==Conjugacy class structure and cycle type==

Vipul: /* Particular cases */

2010-11-13T04:09:45Z

Particular cases

← Older revision		Revision as of 04:09, 13 November 2010
Line 69:		Line 69:
	\|-		\|-
	\| 8 \|\| 22 \|\| 1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]		\| 8 \|\| 22 \|\| 1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]
			\|-
			\| 9 \|\| 30 \|\| 1, 36, 168, 378, 756, 945, 1260, 2240, 2520, 2520, 3024, 3360, 7560, 7560, 9072, 10080, 10080, 11340, 11340, 15120, 15120, 18144, 18144, 20160, 24192, 25920, 25920, 30240, 40320, 45360 \|\| Too long to list \|\| [[element structure of symmetric group:S9#Interpretation as symmetric group\|link]]
			\|-
			\| 10 \|\| 42 \|\| 1, 45, 240, 630, 945, 1260, 3150, 4725, 5040, 6048, 8400, 18900, 18900, 22400, 25200, 25200, 25200, 25200, 50400, 50400, 50400, 56700, 56700, 56700, 60480, 72576, 75600, 86400, 90720, 120960, 120960, 151200, 151200, 151200, 172800, 181440, 201600, 226800, 226800, 259200, 362880, 403200 \|\| Too long to list \|\| [[element structure of symmetric group:S10#Interpretation as symmetric group\|link]]
	\|}		\|}

Vipul: /* Based on number of cycles */

2010-11-13T02:00:54Z

Based on number of cycles

← Older revision		Revision as of 02:00, 13 November 2010
Line 79:		Line 79:
	We can partition the set <math>S_n</math> based on the number of cycles of each permutation. Since the number of cycles depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in <math>S_n</math>. The number of cycles can be any number <math>k</math>, with <math>1 \le k \le n</math>.		We can partition the set <math>S_n</math> based on the number of cycles of each permutation. Since the number of cycles depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in <math>S_n</math>. The number of cycles can be any number <math>k</math>, with <math>1 \le k \le n</math>.

	* The number of elements of <math>S_n</math> with exactly <math>k</math> cycles is denoted <math>\|s(n,k)\|</math> and is termed the [[unsigned Stirling number of the first kind]] with parameters <math>n</math> and <math>k</math> ~~(this~~ is in contrast with the [[Stirling number of the second kind]], which is the number of partitions of a set of size <math>n</math> into <math>k</math> nonempty subsets. The probability of <math>k</math> cycles is thus <math>\|s(n,k)\|/n!</math>. {{further\|[[probability distribution of number of cycles of permutations]]}}		* The number of elements of <math>S_n</math> with exactly <math>k</math> cycles is denoted <math>\|s(n,k)\|</math> and is termed the [[unsigned Stirling number of the first kind]] with parameters <math>n</math> and <math>k</math>. This is in contrast with the [[Stirling number of the second kind]], which is the number of partitions of a set of size <math>n</math> into <math>k</math> nonempty subsets. The probability of <math>k</math> cycles is thus <math>\|s(n,k)\|/n!</math>. {{further\|[[probability distribution of number of cycles of permutations]]}}
	* The expected number of cycles in an element of <math>S_n</math> is the [[harmonic number]] <math>H_n,</math> defined as <math>1 + 1/2 + \dots + 1/n</math>. This is approximately <math>\log n</math> for lrage <math>n</math>. {{further\|[[expected number of cycles of permutation equals harmonic number of degree]]}}		* The expected number of cycles in an element of <math>S_n</math> is the [[harmonic number]] <math>H_n,</math> defined as <math>1 + 1/2 + \dots + 1/n</math>. This is approximately <math>\log n</math> for lrage <math>n</math>. {{further\|[[expected number of cycles of permutation equals harmonic number of degree]]}}

Vipul: /* Conjugacy class structure and cycle type */

2010-11-13T01:59:53Z

Conjugacy class structure and cycle type

← Older revision		Revision as of 01:59, 13 November 2010
Line 48:		Line 48:

	===Particular cases===		===Particular cases===

			{{symmetric group conjugacy class structure facts to check against}}

	{\| class="sortable" border="1"		{\| class="sortable" border="1"

Vipul: /* Particular cases */

2010-11-13T01:05:48Z

Particular cases

← Older revision		Revision as of 01:05, 13 November 2010
Line 60:		Line 60:
	\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| <math>(1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)</math> \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]		\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| <math>(1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)</math> \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| <math>\! (1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),</math><br><math>(3+1+1,20), (5,24), (4+1,30)</math> \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]		\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| <math>(1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),</math><br><math>(3+1+1,20), (5,24), (4+1,30)</math> \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]		\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 7 \|\| 15 \|\| 1,21,70,105,105,210,210,280,420, 420,504,504,630,720,840 \|\| Too long to list \|\| [[element structure of symmetric group:S7#Interpretation as symmetric group\|link]]		\| 7 \|\| 15 \|\| 1,21,70,105,105,210,210,280, 420,420,504,504,630,720,840 \|\| Too long to list \|\| [[element structure of symmetric group:S7#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 8 \|\| 22 \|\| 1,28,105,112,210,420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]		\| 8 \|\| 22 \|\| 1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]
	\|}		\|}

Vipul: /* Particular cases */

2010-11-13T01:04:52Z

Particular cases

← Older revision		Revision as of 01:04, 13 November 2010
Line 52:		Line 52:
	! Degree !! Number of conjugacy classes !! List of conjugacy class sizes !! Pairs of (partition,conjugacy class size) !! More details		! Degree !! Number of conjugacy classes !! List of conjugacy class sizes !! Pairs of (partition,conjugacy class size) !! More details
	\|-		\|-
	\| 1 \|\| 1 \|\| 1 \|\| <math>\! (1,1)</math> \|\| --		\| 1 \|\| 1 \|\| 1 \|\| <math>(1,1)</math> \|\| --
	\|-		\|-
	\| 2 \|\| 2 \|\| 1,1 \|\| <math>\! (2,1), (1+1,1)</math> \|\| --		\| 2 \|\| 2 \|\| 1,1 \|\| <math>(2,1), (1+1,1)</math> \|\| --
	\|-		\|-
	\| 3 \|\| 3 \|\| 1,2,3 \|\| <math>\! (1+1+1,1), (3,2), (2+1,3)</math> \|\| [[element structure of symmetric group:S3#Interpretation as symmetric group\|link]]		\| 3 \|\| 3 \|\| 1,2,3 \|\| <math>(1+1+1,1), (3,2), (2+1,3)</math> \|\| [[element structure of symmetric group:S3#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| <math>\! (1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)</math> \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]		\| 4 \|\| 5\|\| 1,3,6,6,8 \|\| <math>(1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)</math> \|\| [[element structure of symmetric group:S4#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| <math>\! (1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),</math><br><math>(3+1+1,20), (5,24), (4+1,30)</math> \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]		\| 5 \|\| 7 \|\| 1,10,15,20,20,24,30 \|\| <math>\! (1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20),</math><br><math>(3+1+1,20), (5,24), (4+1,30)</math> \|\| [[element structure of symmetric group:S5#Interpretation as symmetric group\|link]]
Line 64:		Line 64:
	\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]		\| 6 \|\| 11 \|\| 1,15,15,40,40,45,90,90,120,120,144 \|\| Too long to list \|\| [[element structure of symmetric group:S6#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 7 \|\| 15 \|\| 1,21,70,105,105,210,210,280,420,420,504,504,630,720,840 \|\| Too long to list \|\| [[element structure of symmetric group:S7#Interpretation as symmetric group\|link]]		\| 7 \|\| 15 \|\| 1,21,70,105,105,210,210,280,420, 420,504,504,630,720,840 \|\| Too long to list \|\| [[element structure of symmetric group:S7#Interpretation as symmetric group\|link]]
	\|-		\|-
	\| 8 \|\| 22 \|\| 1,28,105,112,210,420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]		\| 8 \|\| 22 \|\| 1,28,105,112,210,420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 \|\| Too long to list \|\| [[element structure of symmetric group:S8#Interpretation as symmetric group\|link]]