Set of unordered set partitions - Revision history

Vipul: 6 revisions

2008-05-08T00:13:21Z

6 revisions

← Older revision	Revision as of 00:13, 8 May 2008
(No difference)

Vipul at 09:31, 11 May 2007

2007-05-11T09:31:18Z

← Older revision		Revision as of 09:31, 11 May 2007
Line 90:		Line 90:

	The map from <math>Bell</math> to <math>Part</math> is a map of APSes, viz it is compatible with the block concatenation.		The map from <math>Bell</math> to <math>Part</math> is a map of APSes, viz it is compatible with the block concatenation.

			==Analogues==

			The role that unordered set partitions play in the context of the symmetric group, is played by [[unordered direct sum decomposition]]s when we are working with the [[orthogonal group]] over a field.

Vipul at 09:28, 11 May 2007

2007-05-11T09:28:32Z

← Older revision		Revision as of 09:28, 11 May 2007
Line 60:		Line 60:

	Given an unordered integer partition, we can count the number of times 1 occurs as a part. Composing this with the map from unordered set partitions to unordered integer partitions, we get a map that counts the number of singletons in a partition of a set into subsets.		Given an unordered integer partition, we can count the number of times 1 occurs as a part. Composing this with the map from unordered set partitions to unordered integer partitions, we get a map that counts the number of singletons in a partition of a set into subsets.

			==APS structure==

			===Bell sets form an IAPS===

			Given two disjoint sets <math>A</math> and <math>B</math>, there is a natural injective map:

			<math>Bell(A) \times Bell(B) \to Bell(A \cup B)</math>

			Which partitions the <math>A</math>-part according to the component coming from <math>Bell(A)</math> and the <math>B</math>-part according to the component coming from <math>Bell(B)</math>.

			This thus defines maps:

			<math>Bell(m) \times Bell(n) \to Bell(m+n)</math>

			Under these maps the Bell sets form an injective APS. In particular this also shows that the cardinalities of the Bell numbers grow faster than exponentially.

			===The map from the symmetric group is a map of IAPSes===

			We know that there is a natural map:

			<math>Sym(A) \times Sym(B) \to Sym(A \cup B)</math>

			this commutes with the maps sending <math>Sym</math> to <math>Bell</math>. Thus the map from <math>Sym</math> to <math>Bell</math> is a map of IAPSes.

			===The map to unordered integer partitions is a map of APSes===

			We can give an APS structure to unordered integer partitions; however, this APS structure is not injective. The fact that we ''cannot'' give an injective structure is clear from the observation that the number of unordered integer partitions grows subexponentially.

			The map from <math>Bell</math> to <math>Part</math> is a map of APSes, viz it is compatible with the block concatenation.

Vipul: /* Number of parts map */

2007-05-11T09:19:20Z

Number of parts map

← Older revision		Revision as of 09:19, 11 May 2007
Line 52:		Line 52:
	which sends each unordered set partition to the number of subsets.		which sends each unordered set partition to the number of subsets.

	The inverse image of an integer <math>k</math> under this map is termed the [[Stirling set]]		The inverse image of an integer <math>k</math> under this map is termed the [[Stirling set] of the second kind] and is cardinality is termed the Stirling number of the second kind <math>S(n,k)</math>. Note that:

			* The inverse image of this in the symmetric group is the [[Stirling set of the first kind]] which is the set of all permutations having exactly <math>k</math> cycles.
			* The forward image of this in the[[ set of unordered integer partitions]] is the set of partitions into <math>k</math> parts

			===Number of singletons map===

			Given an unordered integer partition, we can count the number of times 1 occurs as a part. Composing this with the map from unordered set partitions to unordered integer partitions, we get a map that counts the number of singletons in a partition of a set into subsets.

Vipul at 09:14, 11 May 2007

2007-05-11T09:14:35Z

← Older revision		Revision as of 09:14, 11 May 2007
Line 23:		Line 23:
	which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, ''forgetting'' the cyclic ordering. For instance, the permutation with cycle decomposition <math>(135)(24)</math> gives rise to the unordered set partition into subsets <math>\{1,3,5\}</math> and <math>\{2,4\}</math>		which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, ''forgetting'' the cyclic ordering. For instance, the permutation with cycle decomposition <math>(135)(24)</math> gives rise to the unordered set partition into subsets <math>\{1,3,5\}</math> and <math>\{2,4\}</math>

	==Map to the set of unordered integer partitions==		===Map to the set of unordered integer partitions===

	To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition <math>2 + 3 + 3</math>.		To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition <math>2 + 3 + 3</math>.

Vipul: /* =Map to the set of unordered integer partitions */

2007-05-11T09:12:29Z

=Map to the set of unordered integer partitions

← Older revision		Revision as of 09:12, 11 May 2007
Line 23:		Line 23:
	which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, ''forgetting'' the cyclic ordering. For instance, the permutation with cycle decomposition <math>(135)(24)</math> gives rise to the unordered set partition into subsets <math>\{1,3,5\}</math> and <math>\{2,4\}</math>		which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, ''forgetting'' the cyclic ordering. For instance, the permutation with cycle decomposition <math>(135)(24)</math> gives rise to the unordered set partition into subsets <math>\{1,3,5\}</math> and <math>\{2,4\}</math>

	===Map to the set of unordered integer partitions==		==Map to the set of unordered integer partitions==

	To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition <math>2 + 3 + 3</math>.		To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition <math>2 + 3 + 3</math>.

Vipul at 08:58, 11 May 2007

2007-05-11T08:58:10Z

New page

{{combinatorial APS object}}

==Definition==

For any integer <math>n</math>, the set of unordered set partitions for size <math>n</math> is defined as follows: take any set of size <math>n</math>, and consider all the partition of this set into subsets (with no ordering among or between the subsets). This set is termed the set of unordered set partitions for size <math>n</math>.

The cardinality of this set is termed the [[Bell number]] for <math>n</math> and is denoted as <math>B_n</math>. Thus, we shall also call the set of unordered set partitions as the '''Bell set''' and denote it as <math>Bell(n)</math>. If we want to focus on the set itself, we write <math>Bell(S)</math> where <math>S</math> is the set.

==Facts==

===Independent of the choice of set===

Give two sets <math>A</math> and <math>B</math> of the same cardinality, and a bijection <math>f:A \to B</math>, we get an induced bijcetion from the set of unordered set partitions of <math>A</math> to the set of unordered set partitions of <math>B</math>. Thus, the set of unordered set partitions is independent of the choice of labelling.

Further, this also shows that the symmetric group on a set acts on its set of unordered set partitions, by permuting the labels.

===Map from the symmetric group===

To every element of the symmetric group there is a corresponding unordered set partition. In other words, there is a natural map, for any set <math>S</math>:

<math>Pr: Sym(S) \to Bell(S)</math>

which takes as input a permutation and outputs a set partition as follows. It looks at te cycle decomposition of the permutation, and for each cycle, picks the corresponding subset, ''forgetting'' the cyclic ordering. For instance, the permutation with cycle decomposition <math>(135)(24)</math> gives rise to the unordered set partition into subsets <math>\{1,3,5\}</math> and <math>\{2,4\}</math>

===Map to the set of unordered integer partitions==

To every unordered set partition, we can associate a corresponding unordered integer partition, which basically just sends each subset to its size. For instance, an unordered set partition into one subset of size 2, and two subsets of size 3, gives an unordered integer partition <math>2 + 3 + 3</math>.

More formally we get a map:

<math>Bell(S) \to Part(|S|)</math>

where <math>Part(n)</math> denotes theset of unordered integer partitions of the integer <math>n</math>.

Note that the composite of the map from <math>Sym(S)</math> to <math>Bell(S)</math> and the map from <math>Bell(S)</math> to <math>Part(|S|)</math> is the [[cycle type map]].

===Map from the set of ordered set partitions===

Given an ordered set partition, we can obtain from that an unordered set partition, by ''forgetting'' the ordering.

===All these maps are covariant under the action of the symmetric group===

The symmetric group acts on itself by conjugation, as well as on the set of ordered as well as unordered set partitions. Its action on the set of unordered integer partitions is trivial. All the maps between these combinatorial structures described above, are covariant under the action of the symmetric group, viz they commute with the action.
==Decompositions of this set==

===Number of parts map===

Given any unordered integer partition, we can define the ''number of parts'' of that partition. Composing this with the map from unordered set partitions, we get a map:

<math>Bell(S) \to \{1,2,3,\ldots,n\}</math>

which sends each unordered set partition to the number of subsets.

The inverse image of an integer <math>k</math> under this map is termed the [[Stirling set]]