Ordered partition of a set

Ordered partition of a set

In combinatorial mathematics, an ordered partition O of a set S is a sequence

A1, A2, A3, ..., An

of subsets of S, with union is S, which are non-empty, and pairwise disjoint. This differs from a partition of a set, in that the order of the Ai matters.

For example, one ordered partition of { 1, 2, 3, 4, 5 } is

{1, 2} {3, 4} {5}

which is equivalent to

{1, 2} {4, 3} {5}

but distinct from

{3, 4} {1, 2} {5}.

The number of ordered partitions Tn of { 1, 2, ..., n } can be found recursively by the formula:

T_n=\sum_{i=0}^{n-1} {n \choose i} T_i.

Furthermore, the exponential generating function is

\sum_n {T_n \over n!} x^n = {1 \over 2-e^x}.

An ordered partition of "type k_1+\cdots+k_m" is one in which the ith part has ki members, for i = 1, ..., m. The number of such partitions is given by the multinomial coefficient

{n \choose k_1, \dots, k_m} = {n! \over k_1!\cdots k_m!}.

For example, for n = 3:

  • type 1+1+1: 6
  • type 2+1: 3
  • type 1+2: 3
  • type 3: 1

Together this is the ordered Bell number 13.

See also

  • Partitions of a set


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • List of partition topics — This is a list of partition topics, in the mathematical sense. Partition (disambiguation) lists meanings in other fields. In mathematics, a partition may be a partition of a set or an ordered partition of a set, or a partition of a graph, or a… …   Wikipedia

  • Ordered geometry — is a form of geometry featuring the concept of intermediacy (or betweenness ) but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundamental geometry forming a common framework for affine, Euclidean,… …   Wikipedia

  • Partition of Ireland — The partition of Ireland (Irish: críochdheighilt na hÉireann) was the division of the island of Ireland into two distinct territories, now Northern Ireland (a part of the United Kingdom) and the Republic of Ireland (an independent state).… …   Wikipedia

  • Noncrossing partition — A noncrossing partition of ten points In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory of free probability. The set of all noncrossing… …   Wikipedia

  • Strong partition cardinal — In Zermelo Fraenkel set theory without the axiom of choice a strong partition cardinal is an uncountable well ordered cardinal k such that every partition of the set [k] ^kof size k subsets of k into less than k pieces has a homogeneous set of… …   Wikipedia

  • Dominance-based Rough Set Approach — (DRSA) is an extension of rough set theory for Multi Criteria Decision Analysis (MCDA), introduced by Greco, Matarazzo and Słowiński Greco, S., Matarazzo, B., Słowiński, R.: Rough sets theory for multicriteria decision analysis. European Journal… …   Wikipedia

  • Dominance-based rough set approach — (DRSA) is an extension of rough set theory for multi criteria decision analysis (MCDA), introduced by Greco, Matarazzo and Słowiński. [1][2][3] The main change comparing to the classical rough sets is the substitution of the indiscernibility… …   Wikipedia

  • Interval chromatic number of an ordered graph — In mathematics, the interval chromatic number X …   Wikipedia

  • Rough set — A rough set originated by prof. Zdzisław I. Pawlak is a formal approximation of a crisp set (i.e., conventional set ) in terms of a pair of sets which give the lower and the upper approximation of the original set. The lower and upper… …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”