Permutations and partitions in the OEIS

From Wikiversity
Jump to navigation Jump to search
OEISicon.svg
This article references
sequences from the OEIS.

Permutations of a finite set are often sorted lexicographically, but reverse colexicographical order gives an infinite order of finite permutations.
(In this order the inversion vector of the n-th permutation interpreted as a factorial number is n.)
The finite permutations are stored as rows of a triangle in A055089.

Partitions of a finite set and partitions of an integer are also often ordered lexicographically, but the sequences A231428 and A194602 define an infinite order.

These infinite orderings make it possible to define some mappings as sequences:

Each permutation corresponds to a set partition (A249618), and more importantly to an integer partition (A198380) called its cycle type.
(A set partition corresponds only to a finite number of permutations, but each cycle type > 0 corresponds to an infinite number of permutations.)
Each set partition corresponds to an integer partition (A249617) - and each integer partition > 0 to an infinite number of set partitions.

Furthermore each permutation and partition can be assigned a number that for simplicity's sake is called "blocks" in the diagram:
For permutations these are the cycles except fixed points (A055090), for set partitions the non-singleton blocks (A249615) and for integer partitions the non-one addends (A194548).

And of course they can be assigned the total number of elements in these "blocks": A055093, A249616 and a staircase like sequence that is too boring to be in the OEIS.


perm.
set part.
int. part.
Mappings between OEIS sequences related to permutations, set partitions and integer partitions

A198380
cycle type
of the n-th permutation

A055089
n-th permutation
as triangle row

A249618
set partition
of the n-th permutation

A231428
n-th set partition
interpreted as binary number

A249617
integer partition
of the n-th set partition

A194602
n-th integer partition
interpreted as binary number

A055090
number of cycles
in the n-th permutation

A055093
number of elements
moved by the n-th permutation

A249615
number of non-singleton blocks
in the n-th set partition

A249616
number of non-singleton elements
in the n-th set partition

A194548
number of non-one addends
in the n-th integer partition

a(0)=0; p=A000041; n≥1:
p(i−1)≤n<p(i) a(n)=i

sum of non-one addends
in the n-th integer partition

Equalities[edit]

pe2ip = sp2ip( pe2sp ) A198380 = A249617( A249618 )
pe2bl = sp2bl( pe2sp ) = ip2bl( sp2ip( pe2sp ) ) A055090 = A249615( A249618 ) = A194548( A249617( A249618 ) )
sp2bl = ip2bl( sp2ip ) A249615 = A194548( A249617 )
pe2el = sp2el( pe2sp ) = ip2el( sp2ip( pe2sp ) ) A055093 = A249616( A249618 ) = ip2el( A249617( A249618 ) )
sp2el = ip2el( sp2ip ) A249616 = ip2el( A249617 )

For simplicity's sake it is assumed that A231428 and A194548 have index 0 like all the other sequences, although at the moment they have index 1 in the OEIS.