IntegerCompositions
The compositions of : ordered sequences of positive parts summing to .
✓ checked against that system · ! checked, with disagreements (hover a chip)Wikipedia
Composition (combinatorics)MathWorldCompositionWikidataQ3302331OEISA011782✓A131577✓A000079✓A320487✓A166444✓A034008✓SageMathCompositions(n)mathlib4Composition nIntegerCompositions(n)the ordered compositions of Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<composition> | combinatorics | always |
Details
- Count is for
- Unlike IntegerPartitions, order matters
Definition
Epsil, as the implementation runs it.
count(_n)
1 if _n == 0 else 2 ^ (_n - 1)unrank(_n, _r)
[] if _n == 0 else Map(
Function(
Join(
[0],
Filter(
Range(1, _n - 1, 1),
Function(
(2 ^ (_n - 1) - 1 - _r -
(2 ^ (_n - 1) - 1 -
_r) % 2 ^ (_n - 1 - i)) / 2 ^ (_n - 1 - i) %
2 == 1,
i,
),
),
[_n],
)[j + 1] - Join(
[0],
Filter(
Range(
1,
_n - 1,
1,
),
Function(
(2 ^ (_n -
1) -
1 - _r -
(2 ^ (_n -
1) -
1 - _r) %
2 ^ (_n -
1 -
i)) / 2 ^
(_n -
1 -
i) %
2 == 1,
i,
),
),
[_n],
)[j],
j,
),
Range(1, Length(Join(
[0],
Filter(
Range(1, _n - 1, 1),
Function((2 ^ (_n - 1) - 1 -
_r - (2 ^ (_n - 1) -
1 - _r) % 2 ^
(_n -
1 -
i)) /
2 ^ (_n - 1 - i) % 2 == 1, i),
),
[_n],
)) - 1, 1),
)rank(_n, _x)
0 if _n == 0 else 2 ^ (_n - 1) - 1 - Fold(
Function(acc + 2 ^ (_n - 1 - Fold(
Function(acc2 + _x[t], acc2, t),
0,
Range(1, i, 1),
)), acc, i),
0,
Range(1, Length(_x) - 1, 1),
)valid(_n, _x)
Fold(Function(acc2 + _x[t], acc2, t), 0, Range(1, Length(_x), 1)) == _n && Fold(
Function(ok &&
_x[j] >= 1, ok, j),
True,
Range(1, Length(_x), 1),
)Statistics
On IntegerComposition, called as CombinatorialStat(x, "Name").
- AbsoluteVariationSt000089The sum of |c(i+1) - c(i)|.
- AscentsSt000761Positions i with c(i) < c(i+1).
- AscentVariationSt000091The sum of c(i+1) - c(i) over the positions where it is positive.
- AsymmetryDegreeSt001673Pairs of mirror positions holding different parts.
- BargraphHalfPerimeterSt000806Up steps plus horizontal steps of the bargraph.
- BargraphPeakCountSt000805Peaks of the bargraph with bars of these heights: a rise, level steps, then a fall.
- BargraphUpStepCountSt000808Up steps of the bargraph.
- BargraphValleyHeightSumSt000807The sum of the heights of the valleys of the bargraph.
- CompositionMajorIndexSt000008The sum of the descents of the composition: its partial sums, the total left out.
- CompositionNakayamaGlobalDimensionSt001235The global dimension of the linear Nakayama algebra whose Kupisch series is c_1 + 1, ..., 2, c_2 + 1, ..., 2, ..., 1.
- ConstantRunCountSt000767Maximal runs of equal parts.
- DistinctMultiplicitiesSt000905How many different multiplicities the part sizes have.
- DistinctPartsSt000903How many distinct part sizes occur.
- DualImmaculateMonomialColumnSumSt000817The sum of the entries in the column of the composition in the matrix from the dual immaculate to the monomial quasisymmetric functions.
- DyckPathsAboveBouncePathCountSt001312Dyck paths of semilength n that stay weakly above the bounce path of the composition: their area sequences are at least 0 .. c_1 - 1, 0 .. c_2 - 1, ....
- FirstPartSt000382The first part.
- InverseDescentParkingFunctionCountSt000285Parking functions of size n whose diagonal reading word has the inverse descent composition c.
- InversionsSt000766Pairs i < j with c(i) > c(j).
- LargestMultiplicitySt000904The largest number of parts of one size.
- LargestPartSt000381The largest part.
- LastPartSt000383The last part.
- LongestConstantRunSt000899The length of the longest run of equal parts.
- LongestDecreasingSubsequenceSt000760The length of a longest strictly decreasing subsequence of the parts.
- LongestStaircaseSt000758The greatest l with parts at positions i_1 < ... < i_l such that part i_m is at least m.
- LongestWeaklyIncreasingSubsequenceSt000757The length of a longest weakly increasing subsequence of the parts.
- MajorIndexSt000769The sum of the positions i with c(i) > c(i+1).
- PartsEqualToReversedPartSt001675Positions i where the part equals the part at the mirror position.
- PeaksSt000768Interior positions with c(i-1) < c(i) > c(i+1).
- RibbonCornerCountSt001486Corners of the ribbon: its inner and outer corners together.
- RotationOrbitSizeSt000820The number of distinct compositions obtained by rotating the parts.
- SeaweedIndexSt001263Twice the cycles plus the paths, less one, of the meander of the composition over the single block: the index of the maximal parabolic seaweed algebra.
- ShortestConstantRunSt000900The length of the shortest run of equal parts.
- SmallestMultiplicitySt000902The smallest number of parts of one size, among the sizes that occur.
- SmallestPartSt000657The smallest part.
- StandardCompositionTableauCountSt000816Standard composition tableaux of the shape: fillings of 1 .. n with rows decreasing, the first column increasing, and the triple rule.
- StandardImmaculateTableauCountSt000047Standard immaculate tableaux of the shape: fillings of 1 .. n increasing along the rows and down the first column.
- StandardRibbonTableauCountSt000277Standard fillings of the ribbon whose rows have these lengths: the permutations of 1 .. n with these partial sums as their descents.
- StrongRecordCountSt000764Parts greater than every part before: the first part and each new maximum.
- StrongRecordPositionSumSt000763The sum of the positions of the strong records.
- VariationSt000090The signed sum of c(i+1) - c(i): the last part less the first.
- WeakDescentCountSt001777Positions i with c(i) >= c(i+1).
- WeakMajorIndexSt001931The sum of the positions i with c(i) >= c(i+1).
- WeakRecordCountSt000765Parts at least as great as every part before.
- WeakRecordPositionSumSt000762The sum of the positions of the weak records.
Maps
Into and out of IntegerComposition, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From IntegerComposition
- CodeWordIntegerComposition → BinaryWordInjectionGraded mapMp00094The word that writes each part i as a one followed by i - 1 zeros.
- ComplementIntegerComposition → IntegerCompositioninvolutionBijectionGraded mapInvolutionMp00039The composition cut exactly where this one is not: its cut set complemented.
- CompositionBouncePathIntegerComposition → DyckPathInjectionGraded mapMp00231The Dyck path that bounces off the diagonal once for each part: a run of that many ups, then as many downs.
- CutWordIntegerComposition → BinaryWordinverseA composition of n as the binary word of length n - 1 marking where it is cut.
- CyclicShiftIntegerComposition → IntegerCompositioninverseBijectionGraded mapMp00173Rotate the parts one place to the left: the first part moves to the end.
- DeltaMorphismIntegerComposition → IntegerCompositionSurjectionMp00133The lengths of the maximal runs of equal parts, left to right.
- FoataInversionsToMajorIntegerComposition → IntegerCompositionbijectioninverseBijectionGraded mapMp00315The inverse of Foata's bijection on compositions: peel off the last part, rotate the blocks of the rest back.
- FoataMajorToInversionsIntegerComposition → IntegerCompositionbijectioninverseBijectionGraded mapMp00314Foata's bijection on the word of parts: each part is put on the end of the image so far, which is cut into blocks, and every block is rotated one place right.
- InverseCyclicShiftIntegerComposition → IntegerCompositioninverseBijectionGraded mapMp00172Rotate the parts one place to the right: the last part moves to the front.
- ReverseIntegerComposition → IntegerCompositioninvolutionBijectionGraded mapInvolutionMp00038The parts read backwards.
- SortedPartitionIntegerComposition → IntegerPartitionsurjectionSurjectionGraded mapMp00040The partition a composition's parts form, sorted largest first.
- TransposeCompositionIntegerComposition → IntegerCompositioninvolutionBijectionGraded mapInvolutionMp00041The conjugate composition: its ribbon shape transposed, the complement of the reverse.
To IntegerComposition
- BlockSizeCompositionSetPartition → IntegerCompositionsurjectionSurjectionGraded mapMp00128The block sizes of a set partition, its blocks taken in order of their least elements.
- BlockSizeCompositionSetComposition → IntegerCompositionsurjectionSurjectionGraded mapMp00287The block sizes of a set composition, its blocks taken in order.
- CodeCompositionBinaryWord → IntegerCompositionInjectionGraded mapMp00178The composition whose code is the word with a 1 put in front: each 1 opens a part, of 1 plus the zeros after it.
- DescentCompositionPermutation → IntegerCompositionsurjectionSurjectionGraded mapMp00071The composition of n cut at the descent positions.
- IntegerCompositionBinaryWord → IntegerCompositioninverseThe composition of m + 1 a binary word of length m cuts out.
- PeakCompositionStandardTableau → IntegerCompositionGraded mapMp00294The composition cut at the peaks: entries i that are descents after an ascent.
- RiseCompositionDyckPath → IntegerCompositionsurjectionSurjectionGraded mapMp00102The lengths of the maximal runs of up steps, left to right.
- RunCompositionBinaryWord → IntegerCompositionsurjectionSurjectionGraded mapMp00097The lengths of the maximal runs of equal letters, left to right.
- TouchCompositionDyckPath → IntegerCompositionsurjectionSurjectionGraded mapMp00100The semilengths of the primitive pieces between a path's returns to the diagonal.
- ValleyCompositionStandardTableau → IntegerCompositionGraded mapMp00295The composition cut at the valleys: entries i that are ascents after a descent.
10 more in FindStat, not implemented here
- Mp00054ParkingFunction → IntegerCompositionSurjectionGraded mapto inverse des composition
- Mp00057ParkingFunction → IntegerCompositionSurjectionGraded mapto touch composition
- Mp00152LabeledGraph → IntegerCompositionSurjectionGraded mapLaplacian multiplicities
- Mp00180IntegerComposition → SkewPartitionInjectionGraded mapto ribbon
- Mp00181SkewPartition → IntegerCompositionSurjectionGraded maprow lengths
- Mp00184IntegerComposition → LabeledGraphInjectionGraded mapto threshold graph
- Mp00207StandardTableau → IntegerCompositionSurjectionGraded maphorizontal strip sizes
- Mp00248Permutation → IntegerCompositionGraded mapDEX composition
- Mp00319ParkingFunction → IntegerCompositionInjectionto composition
- Mp00324LabeledGraph → IntegerCompositionGraded mapchromatic difference sequence
Enumeration
Examples
About
| Examples | 1 |
|---|---|
| Checked against | mathlib4 1 agree |
| Crosswalk | WikipediaMathWorldWikidataOEIS ×6SageMathmathlib4 |
Implementation
mapped
mathlib4packages/oracle/src/mappings.tsComposition n enumerated (Fintype) as block lists, in lexicographic order
See also: IntegerPartitions