Preferential arrangements of set partitions
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.)
Example {1,2}{3}{4} |
---|
The blocks of the partition {1,2}{3}{4} can be assigned to levels in the following ways - with the colon ":" as a separator between two levels: The above syntax is used on the OEIS pages linked below. Here this will be written in the following way, to harmonize with abbreviations in Formulas in predicate logic: Sometimes (especially in variables - like here) parentheses are not allowed, so something like this may be the solution: |
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
Examples | ||||||
---|---|---|---|---|---|---|
|
n=4
edit
Examples | ||||||
---|---|---|---|---|---|---|
|
Number of PA
editThere are A083355(n) PA of an n-set.
The illustrations above indicate two ways to order them by a second property:
A232598(n,k) = S2(n,k) * oB(k) is the number of n-set PA with k blocks.
A233357(n,i) = S22(n,i) * i! with S22= A039810 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 n 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