SetCompositions
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Compositions of a set: an ordered sequence of blocks partitioning it.
✓ checked against that system · ! checked, with disagreements (hover a chip)OEIS
A000670✓A034172✓SageMathOrderedSetPartitions(n)SetCompositions(n)Compositions of a set: an ordered sequence of blocks partitioning it.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<set_composition> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
Fold(Function(fa + _tables[_n * (_n + 1) + fc + 1], fa, fc), 0, Range(0, _n, 1))unrank(_n, _r)
[] if _n == 0 else Apply(
(cf: list<integer>) => Apply((ck: integer) => Apply(
(cl: list<integer>) => Map(Function(Filter(
Range(1, _n, 1),
Function(cl[p] == j, p),
), j), Range(1, ck, 1)),
Apply(
(surj: list<integer>) => Drop(Fold(Function(Apply(
(sw: list<integer>) => Apply((sm: integer) => Apply((sl: integer) => Apply(
(sc: list<integer>) => Join([sc[1], sc[3]], sw, [sc[2]]),
Fold(Function(sf if 0 < sf[2] else Apply(
(sn: integer) => [sf[1], c, sm if Contains(sw, c) else sm - 1] if sf[1] < sn else [sf[1] - sn, 0, sm],
surj[sl *
(ck + 1) + sm + 1] if Contains(sw, c) else surj[sl *
(ck + 1) +
(sm - 1) +
1] if 0 < sm else 0,
), sf, c), [su[1], 0, sm], Range(1, ck, 1)),
), _n - si), su[2]),
Drop(su, 2),
), su, si), [cf[1], ck], Range(1, _n, 1)), 2),
Fold(
Function(Join(
j_t,
Fold(
Function(ReplaceAt(
j_row,
j_c + 1,
(j_c *
j_t[(j_s - 1) *
(ck + 1) +
(j_c - 1) +
1] if 0 < j_c else 0) +
(ck - j_c) *
j_t[(j_s - 1) *
(ck + 1) + j_c + 1],
), j_row, j_c),
Map(
Function(0, j_z),
Range(0, ck + 1 -
1, 1),
),
Range(0, ck + 1 -
1, 1),
),
), j_t, j_s),
Fold(
Function(ReplaceAt(j_row, j_c + 1, 1 if j_c == 0 else 0), j_row, j_c),
Map(
Function(0, j_z),
Range(0, ck + 1 -
1, 1),
),
Range(0, ck + 1 -
1, 1),
),
Range(1, _n + 1 -
1, 1),
),
),
), cf[2]),
Fold(
Function(ff if 0 < ff[2] else Apply(
(fn: integer) => [ff[1], fk] if ff[1] < fn else [ff[1] - fn, 0],
_tables[_n *
(_n +
1) +
fk +
1],
), ff, fk),
[_r, 0],
Range(1, _n, 1),
),
)rank(_n, _x)
Apply(
(cl: list<integer>) => Apply((ck: integer) => Fold(
Function(fa +
_tables[_n *
(_n +
1) +
fc +
1], fa, fc),
0,
Range(1, ck - 1, 1),
) + Apply(
(surj: list<integer>) => Fold(Function(Apply(
(sp: list<integer>) => Apply((sm: integer) => Apply((sl: integer) => [sr[1] +
Fold(Function(sb +
(surj[sl *
(ck + 1) + sm + 1] if Contains(sp, c) else surj[sl *
(ck + 1) +
(sm - 1) +
1] if 0 < sm else 0), sb, c), 0, Range(1, sx - 1, 1)), sm if Contains(sp, sx) else sm - 1, sr[3] + 1], _n - sr[3]), sr[2]),
Take(cl, sr[3] - 1),
), sr, sx), [0, ck, 1], cl)[1],
Fold(
Function(Join(
j_t,
Fold(
Function(ReplaceAt(
j_row,
j_c + 1,
(j_c *
j_t[(j_s - 1) *
(ck + 1) +
(j_c - 1) +
1] if 0 < j_c else 0) +
(ck - j_c) *
j_t[(j_s - 1) *
(ck + 1) + j_c + 1],
), j_row, j_c),
Map(
Function(0, j_z),
Range(0, ck + 1 -
1, 1),
),
Range(0, ck + 1 -
1, 1),
),
), j_t, j_s),
Fold(
Function(ReplaceAt(
j_row,
j_c + 1,
1 if j_c == 0 else 0,
), j_row, j_c),
Map(
Function(0, j_z),
Range(0, ck + 1 -
1, 1),
),
Range(0, ck + 1 -
1, 1),
),
Range(
1,
_n + 1 -
1,
1,
),
),
), Length(_x)),
Map(
Function(Fold(Function(
la + (lj if Contains(_x[lj], lx) else 0),
la,
lj,
), 0, Range(1, Length(_x), 1)), lx),
Range(1, _n, 1),
),
)valid(_n, _x)
Apply((flat: list<integer>) => Length(flat) == _n &&
Fold(Function(
ok_blk && Length(blk) >= 1,
ok_blk,
blk,
), True, _x) && Fold(
Function(ok_x &&
Contains(flat, x), ok_x, x),
True,
Range(1, _n, 1),
), Flatten(_x))tables(_n)
Fold(Function(Join(
f_t,
Fold(Function(ReplaceAt(
f_row,
f_c + 1,
0 if f_c == 0 else f_c * (f_t[(f_s -
1) *
(_n +
1) +
f_c +
1] +
f_t[(f_s -
1) *
(_n +
1) +
(f_c -
1) +
1]),
), f_row, f_c), Map(
Function(0, f_z),
Range(0, _n + 1 -
1, 1),
), Range(0, _n + 1 -
1, 1)),
), f_t, f_s), Fold(
Function(ReplaceAt(
f_row,
f_c + 1,
1 if f_c == 0 else 0,
), f_row, f_c),
Map(
Function(0, f_z),
Range(0, _n + 1 - 1, 1),
),
Range(0, _n + 1 - 1, 1),
), Range(1, _n + 1 - 1, 1))Maps
Into and out of SetComposition, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From SetComposition
- BlockConcatenationSetComposition → PermutationsurjectionSurjectionGraded mapMp00286The permutation that lists the blocks in order, each sorted increasingly.
- BlockSizeCompositionSetComposition → IntegerCompositionsurjectionSurjectionGraded mapMp00287The block sizes of a set composition, its blocks taken in order.
- ComplementSetComposition → SetCompositioninvolutionGraded mapInvolutionMp00289Each element i replaced by n + 1 - i, the blocks staying in their order.
- CyclicShiftSetComposition → SetCompositioninverseBijectionGraded mapMp00292The first block moved to the end.
- InverseCyclicShiftSetComposition → SetCompositioninverseBijectionGraded mapMp00291The last block moved to the front.
- ReverseSetComposition → SetCompositioninvolutionGraded mapInvolutionMp00288The blocks in the opposite order.
- SurjectionSetComposition → SurjectioninverseA set composition as a surjection: each position labelled with its block's index, from 1.
- UnderlyingSetPartitionSetComposition → SetPartitionsurjectionSurjectionGraded mapMp00285The set partition with the same blocks, the order of the blocks forgotten.
To SetComposition
- SetCompositionSurjection → SetCompositioninverseThe set composition a surjection labels: block j holds the positions labelled j.
1 more in FindStat, not implemented here
- Mp00290ParkingFunction → SetCompositionSurjectionGraded mapto ordered set partition