NonCrossingPartitions
The partitions of with no two blocks whose consecutive-element arcs cross.
Wikipedia
Noncrossing partitionWikidataQ7049245OEISA000108SageMathsage.combinat.set_partition.SetPartition.is_noncrossingNonCrossingPartitions(n)the partitions of with no two blocks whose consecutive-element arcs crossTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<set_partition> | combinatorics | always |
Details
- Count is the Catalan number (A000108).
Definition
Epsil, as the implementation runs it.
count(_n)
Apply((bd: integer) => 0 if 2 * _n < 0 || (2 * _n - 0) % 2 == 1 else Binomial(2 *
_n, bd) -
(0 if bd ==
0 else Binomial(2 * _n, bd - 1)), (2 * _n -
0 - (2 *
_n - 0) %
2) / 2)unrank(_n, _r)
Apply(
(tz: list<integer>) => Apply((tlab: list<integer>) => Map(
Function(Filter(
Range(1, _n, 1),
Function(tlab[p] == j, p),
), j),
Range(
0,
tz[2] -
1,
1,
),
), Drop(tz, 3 +
tz[3])),
Apply((ts_init: list<integer>) => Fold((ts: list<integer>, ti) => Apply(
(ts_next: list<integer>) => ts_next,
Apply((tu: list<integer>) => Apply((tr: integer) => Apply((tb: integer) => Apply((ta: integer) => Apply((tt: integer) => Apply(
(tl: list<integer>) => Apply((tw: list<integer>) => Apply(
(to: integer) => Join([tr, tb + 1, ta + 1], tl, [tb], tw, [tb]) if tr < to else Apply(
(tf: list<integer>) => Apply((tj: integer) => Apply((tc: integer) => Apply((tk: list<integer>) => Join([tf[1], tb, Length(tk) + 1], tk, [tc], tw, [tc]), Take(tl, tj - 1)), tl[tj]), tf[2]),
Apply((tg_init: list<integer>) => Fold((tg: list<integer>, tq) => Apply(
(tg_next: list<integer>) => tg_next,
tg if 0 < tg[2] else Apply(
(tx: integer) => [tg[1], tq] if tg[1] < tx else [tg[1] - tx, 0],
_tables[(tt - 1) *
(_n + 2) + tq + 1],
),
), tg_init, Range(1, ta, 1)), [tr - to, 0]),
),
_tables[(tt - 1) *
(_n + 2) +
ta + 1 +
1],
), Drop(tu, 3 + ta)),
Take(Drop(tu, 3), ta),
), _n + 1 -
ti), tu[3]), tu[2]), tu[1]), ts),
), ts_init, Range(1, _n, 1)), [_r, 0, 0]),
)rank(_n, _x)
Apply((lb: list<integer>) => Apply(
(pr: list<integer>) => Fold(Function(
Apply((ru: list<integer>) => Apply((rp: integer) => Apply((ra: integer) => Apply(
(rt: integer) => Apply((rl: list<integer>) => Apply(
(rj: integer) => Join(ru, [ri]) if rp == 0 else Join([ru[1] +
_tables[(rt - 1) *
(_n + 2) +
ra + 1 +
1] +
Fold(Function(rw +
_tables[(rt - 1) *
(_n + 2) + rk + 1], rw, rk), 0, Range(1, rj - 1, 1))], Take(rl, rj - 1), [ri]),
1 +
Count(Filter(rl, Function(rv < rp, rv))),
), Drop(ru, 1)),
_n + 1 -
ri,
), Length(ru) - 1), pr[ri]), rs),
rs,
ri,
), [0], Range(1, _n, 1))[1],
Map(Function(
Fold(Function(
ez if lb[ez] ==
lb[ei] else ea,
ea,
ez,
), 0, Range(
1,
ei -
1,
1,
)),
ei,
), Range(1, _n, 1)),
), 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)) && Apply(
(lb: list<integer>) => Apply(
(pr: list<integer>) => Fold(
Function(ok_vi &&
Fold(Function(ok_vk &&
!(0 < pr[vi] &&
0 < pr[vk] &&
pr[vi] < pr[vk] &&
pr[vk] < vi &&
vi < vk), ok_vk, vk), True, Range(1, _n, 1)), ok_vi, vi),
True,
Range(1, _n, 1),
),
Map(
Function(Fold(
Function(ez if lb[ez] == lb[ei] else ea, ea, ez),
0,
Range(1, ei - 1, 1),
), ei),
Range(1, _n, 1),
),
),
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),
),
)tables(_n)
Fold(
Function(
Join(
g_t,
Fold(
Function(
ReplaceAt(
g_row,
g_c + 1,
(g_t[(g_s - 1) * (_n + 2) + g_c +
1 +
1] if g_c + 1 < _n + 2 else 0) +
Fold(
Function(
gs + g_t[(g_s -
1) *
(_n +
2) +
gm + 1],
gs,
gm,
),
0,
Range(1, g_c, 1),
),
),
g_row,
g_c,
),
Map(Function(0, g_z), Range(0, _n + 2 - 1, 1)),
Range(0, _n + 2 - 1, 1),
),
),
g_t,
g_s,
),
Fold(
Function(ReplaceAt(g_row, g_c + 1, 1), g_row, g_c),
Map(Function(0, g_z), Range(0, _n + 2 - 1, 1)),
Range(0, _n + 2 - 1, 1),
),
Range(1, _n + 1 - 1, 1),
)Statistics
On SetPartition, called as CombinatorialStat(x, "Name").
- AntisingletonsSt000248Elements i with i + 1 in the same block, counting n + 1 as 1.
- BlockMajorIndexSt000565The sum over blocks i of i times the elements of block i above the least element of block i + 1.
- BlocksSt000105The number of blocks.
- BlocksAndAntisingletonsSt000250Blocks plus antisingletons.
- BlocksAtLeastTwoSt000251Blocks containing at least two elements.
- BlockSizeSpanLargest block size minus smallest.
- BlocksSizeTwoBlocks containing exactly two elements.
- BlocksWithEvenMinimumSt001153Blocks whose smallest element is even.
- BlocksWithOddMinimumSt001151Blocks whose smallest element is odd.
- CloserBeforeLargerPairsSt000577Pairs a < b in different blocks with a the greatest element of its block.
- CloserBeforeOpenerPairsSt000576Pairs a < b in different blocks with a the greatest and b the least element of its block.
- CloserBeforeSingletonPairsSt000575Pairs a < b in different blocks with a the greatest element of its block and b a singleton block.
- CrossingNestingTotalCrossings plus nestings.
- CrossingNumberSt000253The largest number of arcs that mutually cross.
- CrossingsSt000232Pairs of arcs a < b < c < d with a~c and b~d.
- DepthIndexSt001094The sum of n - i over the arcs i, less the depth of each element, plus the depth of each arc.
- DimensionExponentSt000572The sum over blocks of span minus (size - 1).
- DimensionIndexSt000229The sum over blocks of largest minus smallest element, plus one.
- DistinctBlockPairsSt000564Pairs of elements in different blocks.
- FirstAtomicComponentBlockCountSt000695The least l for which the first l blocks hold exactly 1 .. m.
- FirstBlockCardinalitySt000504The size of the block containing 1.
- FirstBlockSecondOrSmallestNonsingletonMaximumSt001784The smaller of the second element of the block holding 1 and the smallest closer; 1 when {1} is a block.
- FlattenedAscentTopsAfterSmallerSt001641Ascent tops of the flattened word with every smaller element earlier.
- FlattenedMajorIndexSt000748The major index of the permutation listing the blocks in order, each ascending.
- HuangRhoadesMajorIndexSt000747The major index of the flattened permutation, plus for each block ending before the next begins the elements so far beyond each block's first.
- InterlacingNumberSt001781Pairs of blocks whose i-th arcs interlace, each block closed by an arc to infinity.
- InternalPointsSt000562Elements with an earlier and a later element whose blocks open after theirs does.
- IntertwiningNumberSt000490Pairs a < b in different blocks with no element of either block between them.
- LargestBlockSt001062The size of the largest block.
- LargestElementInFirstBlockSt000505The largest element of the block containing 1.
- LargestOpenerSt000839The largest of the blocks' smallest elements.
- LastBlockSizeThe size of the final block.
- LeftCloserBiggerSt000497Pairs of a closer j and a smaller element i of a later block.
- LeftCloserSmallerSt000498Pairs of a closer j and a larger element i of a later block.
- LeftOpenerSmallerSt000493Pairs of an opener j and a larger element i of a later block.
- MahonianWordDescentsSt001840Descents of the Mahonian word.
- MahonianWordExcedancesSt001839Excedances of the Mahonian word.
- MahonianWordInversionsSt001841Inversions of the Mahonian word.
- MahonianWordMajorIndexSt001842The major index of the Mahonian word.
- MahonianWordZIndexSt001843The major indices of the Mahonian word restricted to each pair of letters, summed.
- MaximalArcLengthSt000730The length of the longest arc; 0 when there is no arc.
- MaximalBlockDifferenceSt000503The largest difference between two elements of one block.
- MinimalArcLengthSt000729The length of the shortest arc; the number of elements when there is no arc.
- NestingNumberSt000254The largest number of arcs that mutually nest.
- NestingsSt000233Pairs of arcs a < b < c < d with a~d and b~c.
- OccurrencesOf12Over3St000554Occurrences of the pattern 12/3: a < b in one block and c > b in another.
- OccurrencesOf12Over34St000560Occurrences of the pattern 12/34: a < b < c < d with a, b in one block and c, d in another.
- OccurrencesOf13Over2St000555Occurrences of the pattern 13/2: a < c in one block with b between them in another.
- OccurrencesOf13Over24St000559Occurrences of the pattern 13/24: a < b < c < d with a, c in one block and b, d in another.
- OccurrencesOf13Over2Closers2St000610Occurrences of the pattern 13/2 with 2 the greatest element of its block.
- OccurrencesOf13Over2Closers2Arc13St000585Occurrences of the pattern 13/2 with 2 the greatest element of its block and 1 and 3 consecutive in one block.
- OccurrencesOf13Over2Openers1St000602Occurrences of the pattern 13/2 with 1 the least element of its block.
- OccurrencesOf13Over2Openers12Arc13St000594Occurrences of the pattern 13/2 with 1 and 2 the least elements of their blocks and 1 and 3 consecutive in one block.
- OccurrencesOf13Over2Openers1Arc13St000600Occurrences of the pattern 13/2 with 1 the least element of its block and 1 and 3 consecutive in one block.
- OccurrencesOf13Over2Openers1Closers2St000581Occurrences of the pattern 13/2 with 1 the least element of its block and 2 the greatest element of its block.
- OccurrencesOf13Over2Openers1Closers3Arc13St000582Occurrences of the pattern 13/2 with 1 the least element of its block, 3 the greatest element of its block and 1 and 3 consecutive in one block.
- OccurrencesOf13Over2Openers2Closers3Arc13St000613Occurrences of the pattern 13/2 with 2 the least element of its block, 3 the greatest element of its block and 1 and 3 consecutive in one block.
- OccurrencesOf1Over23St000556Occurrences of the pattern 1/23: b < c in one block and a < b in another.
- OccurrencesOf1Over23Arc23St000599Occurrences of the pattern 1/23 with 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Closers1St000611Occurrences of the pattern 1/23 with 1 the greatest element of its block.
- OccurrencesOf1Over23Closers13Arc23St000606Occurrences of the pattern 1/23 with 1 and 3 the greatest elements of their blocks and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Closers1Arc23St000589Occurrences of the pattern 1/23 with 1 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Closers3Arc23St000605Occurrences of the pattern 1/23 with 3 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers1St000595Occurrences of the pattern 1/23 with 1 the least element of its block.
- OccurrencesOf1Over23Openers12St000609Occurrences of the pattern 1/23 with 1 and 2 the least elements of their blocks.
- OccurrencesOf1Over23Openers12Arc23St000601Occurrences of the pattern 1/23 with 1 and 2 the least elements of their blocks and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers12Closers3Arc23St000598Occurrences of the pattern 1/23 with 1 and 2 the least elements of their blocks, 3 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers1Arc23St000612Occurrences of the pattern 1/23 with 1 the least element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers1Closers3Arc23St000614Occurrences of the pattern 1/23 with 1 the least element of its block, 3 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers2St000586Occurrences of the pattern 1/23 with 2 the least element of its block.
- OccurrencesOf1Over23Openers2Arc23St000597Occurrences of the pattern 1/23 with 2 the least element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers2Closers1Arc23St000590Occurrences of the pattern 1/23 with 2 the least element of its block, 1 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over23Openers2Closers3Arc23St000607Occurrences of the pattern 1/23 with 2 the least element of its block, 3 the greatest element of its block and 2 and 3 consecutive in one block.
- OccurrencesOf1Over2Over3St000557Occurrences of the pattern 1/2/3: a < b < c in three different blocks.
- OccurrencesOf1Over2Over3Closers1St000592Occurrences of the pattern 1/2/3 with 1 the greatest element of its block.
- OccurrencesOf1Over2Over3Closers13St000615Occurrences of the pattern 1/2/3 with 1 and 3 the greatest elements of their blocks.
- OccurrencesOf1Over2Over3Closers2St000591Occurrences of the pattern 1/2/3 with 2 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers1St000587Occurrences of the pattern 1/2/3 with 1 the least element of its block.
- OccurrencesOf1Over2Over3Openers12St000593Occurrences of the pattern 1/2/3 with 1 and 2 the least elements of their blocks.
- OccurrencesOf1Over2Over3Openers12Closers3St000608Occurrences of the pattern 1/2/3 with 1 and 2 the least elements of their blocks and 3 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers13Closers2St000588Occurrences of the pattern 1/2/3 with 1 and 3 the least elements of their blocks and 2 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers1Closers3St000584Occurrences of the pattern 1/2/3 with 1 the least element of its block and 3 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers23St000603Occurrences of the pattern 1/2/3 with 2 and 3 the least elements of their blocks.
- OccurrencesOf1Over2Over3Openers2Closers3St000580Occurrences of the pattern 1/2/3 with 2 the least element of its block and 3 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers3Closers1St000596Occurrences of the pattern 1/2/3 with 3 the least element of its block and 1 the greatest element of its block.
- OccurrencesOf1Over2Over3Openers3Closers12St000583Occurrences of the pattern 1/2/3 with 3 the least element of its block and 1 and 2 the greatest elements of their blocks.
- OccurrencesOf1Over2Over3Openers3Closers2St000604Occurrences of the pattern 1/2/3 with 3 the least element of its block and 2 the greatest element of its block.
- OpenerBeforeCloserPairsSt000574Pairs a < b in different blocks with a the least and b the greatest element of its block.
- OverlappingBlockPairsSt000563Pairs of blocks A, B with min A < min B < max A < max B.
- RightCloserBiggerSt000499Pairs of a closer j and a smaller element i of an earlier block.
- RightCloserSmallerSt000496Pairs of a closer j and a larger element i of an earlier block.
- RightOpenerBiggerSt000492Pairs of an opener j and a smaller element i of an earlier block.
- RightOpenerSmallerSt000491Pairs of an opener j and a larger element i of an earlier block.
- RotationOrbitSizeSt000163The number of distinct partitions rotation i -> i + 1 (mod n) makes of this one.
- SameBlockPairsSt000558Pairs of elements in one block.
- SameBlockTriplesSt000561Triples of elements in one block.
- SetPartitionDimensionSt000728The sum of the lengths of the arcs, taking for each block its largest element minus its smallest.
- SetPartitionRankSt000211The number of elements minus the number of blocks.
- SingletonBeforeCloserPairsSt000573Pairs a < b in different blocks with a a singleton block and b the greatest element of its block.
- SingletonBeforeLargerPairsSt000578Pairs a < b in different blocks with a a singleton block.
- SingletonBlocksSt000247Blocks containing exactly one element.
- SingletonsAndAntisingletonsSt000249Singleton blocks plus antisingletons.
- SmallerBeforeCloserPairsSt000579Pairs a < b in different blocks with b the greatest element of its block.
- SmallestBlockSt001075The size of the smallest block.
- SmallestCloserSt000971The smallest of the blocks' largest elements.
- SuccessionsSt000502Elements i with i + 1 in the same block.
- SumOfBlockMaximaSt000231The sum of the largest elements of the blocks.
- SumOfBlockMinimaSt000230The sum of the smallest elements of the blocks.
- TerminalClosersSt001050Closers e with every larger element also a closer.
- TopologicallyConnectedComponentsSt000925The topologically connected components of the arc diagram: blocks joined when an arc of one crosses an arc of the other.
- UnsplittableFactorCountSt000823The number of unsplittable factors of the set partition under the split product.
Maps
Into and out of SetPartition, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From SetPartition
- ArcRepresentationSetPartition → EndofunctionEach position linked to the next in its block, or to itself when last.
- AssociatedStandardTableauSetPartition → StandardTableauSurjectionMp00258The standard tableau whose j-th column holds the j-th smallest elements of the blocks, in increasing order.
- BlockSizeCompositionSetPartition → IntegerCompositionsurjectionSurjectionGraded mapMp00128The block sizes of a set partition, its blocks taken in order of their least elements.
- BlockSizePartitionSetPartition → IntegerPartitionsurjectionSurjectionGraded mapMp00079The partition of n a set partition's block sizes form, largest first.
- CallanSwitchSetPartition → SetPartitionBijectionGraded mapInvolutionMp00249Callan's involution: switches the first closer with the lesser of the least closer and the second element of the block of 1.
- ComplementSetPartition → SetPartitioninvolutionBijectionGraded mapInvolutionMp00112Each element i replaced by n + 1 - i: the set partition seen from the other end.
- DecreasingRotationSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00176Every element lowered by one, cyclically: 1 becomes the largest.
- DualMajorIndexToIntertwiningSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00174The inverse of IntertwiningToDualMajorIndex: read the growth word as an intertwining word and rebuild the blocks.
- IncreasingCyclePermutationSetPartition → PermutationInjectionGraded mapMp00080The permutation whose cycles are the blocks, each cycle increasing: every element goes to the next larger in its block, the largest to the least.
- IncreasingRotationSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00091Every element raised by one, cyclically: the largest becomes 1.
- IntertwiningToDualMajorIndexSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00171The set partition whose growth word is the intertwining word: a bijection taking the intertwining number to the dual major index.
- InverseWachsWhiteSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00216The set partition joined by the arcs of the rook placement that Wachs and White's bijection gamma assigns to the set partition.
- InverseWachsWhiteRhoSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00218The set partition joined by the arcs of the rook placement that Wachs and White's bijection rho assigns to the set partition.
- InverseYipSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00219The set partition joined by the arcs of the rook placement that Yip's bijection psi assigns to the set partition.
- KasraouiZengSetPartition → SetPartitionBijectionGraded mapInvolutionMp00115The Kasraoui-Zeng involution: exchanges the number of crossings with the number of nestings.
- RestrictedGrowthStringSetPartition → RestrictedGrowthStringinverseA set partition's restricted growth string: each position labelled with its block's index, from 0.
- WachsWhiteSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00215The set partition whose arcs, read as a rook placement, Wachs and White's bijection gamma carries to a set partition.
- WachsWhiteRhoSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00217The set partition whose arcs, read as a rook placement, Wachs and White's bijection rho carries to a set partition.
- YipSetPartition → SetPartitionbijectioninverseBijectionGraded mapMp00220The set partition whose arcs, read as a rook placement, Yip's bijection psi carries to a set partition.
To SetPartition
- CyclePartitionPermutation → SetPartitionsurjectionSurjectionGraded mapMp00151The orbits, as a set partition of the positions.
- NoncrossingPartitionDyckPath → SetPartitionInjectionGraded mapMp00138Biane's noncrossing set partition: the up steps whose matching downs lie in one run of downs form a block.
- RowSetPartitionStandardTableau → SetPartitionInjectionGraded mapMp00284The set partition whose blocks are the rows of the tableau.
- SetPartitionRestrictedGrowthString → SetPartitioninverseThe set partition a restricted growth string labels: block j holds the positions labelled j.
- UnderlyingSetPartitionSetComposition → SetPartitionsurjectionSurjectionGraded mapMp00285The set partition with the same blocks, the order of the blocks forgotten.
- WeakExceedancePartitionPermutation → SetPartitionSurjectionGraded mapMp00240The coarsest set partition containing every arc from i to π(i) with i ≤ π(i).
Enumeration
Examples
1 more kept as data, checked against the oracles See also: SetPartitions, NonNestingPartitions, DyckPaths