Preferential arrangements of set partitions

From Wikiversity
Jump to navigation Jump to search

This article is foremost a supplement to Formulas in predicate logic, because a formula with an n-place predicate is essentially a PA of an n-set together with a Boolean value.

Intuitively a preferential arrangement (PA) of a partition of a set is a ranking of the partition's blocks in a hierarchy (where several blocks may be in the same level of the hierarchy).
(As there is no risk of confusion, a PA of a partition of a set is simply called a PA of a set here.)

More abstractly: a PA of the set {1...n} is a partition of {1...n} with k parts, a partition of {1...k} with i parts and a permutation of (1...i)

- or in other terms: a partition of {1...n} with k parts and an ordered partition of {1...k}.
(So the PA correspnding to the finest partition 1∣...∣n are simply the ordered partitions of {1...n}.)

In the following illustrations for n=3 and n=4 every combination of a red partition, a green partition over it and a blue permutation left of it is a PA:

n=3[edit | edit source]

The 2*23 = 46 3-place formulas in a Hasse diagram
The 23 PA of the set {1,2,3}

n=4[edit | edit source]

The 175 PA of the set {1,2,3,4}

Number of PA[edit | edit source]

There are Sloane'sA083355(n) PA of an n-set.
The illustrations above indicate two ways to order them by a second property:
Sloane'sA232598(n,k) = S2(n,k) * oB(k) is the number of n-set PA with k blocks.
Sloane'sA233357(n,i) = S22(n,i) * i! with S22=Sloane'sA039810 is the number of n-set PA with i levels.

          A232598                                   A233357                                     A083355
          k = 1    2     3      4      5            i = 1     2      3      4       5              sums
1             1                                         1                                             1
2             1    3                                    2     2                                       4
3             1    9    13                              5    12      6                               23
4             1   21    78     75                      15    64     72     24                       175
5             1   45   325    750    541               52   350    660    480     120              1662