StandardTableaux
A name from the enumeratio catalogue with no kernel of its own yet; this page carries its crosswalk only.
Standard Young tableaux: fillings of a partition shape, weakly increasing along rows and columns.
Wikipedia
Young tableauMathWorldYoungTableauWikidataQ2166280nLabYoung diagramOEISA000085SageMathStandardTableaux(n)mathlib4SemistandardYoungTableauStandardTableaux(n)Standard Young tableaux: fillings of a partition shape, weakly increasing along rows and columns.Combinatorica
Flatten[Map[Tableaux, Partitions[n]], 1]Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<standard_tableau> | combinatorics | always |
Definition
Epsil, as the implementation runs it.
count(_n)
Fold(
Function([sy_i[2], sy_i[2] + (sy_m - 1) * sy_i[1]], sy_i, sy_m),
[1, 1],
Range(2, _n, 1),
)[2]unrank(_n, _r)
Apply(
(sy_found: list<integer>) => Apply(
(sy_shape: list<integer>) => Apply(
(sy_end: list<integer>) => Apply(
(sy_rows: list<integer>) => Map(
Function(Filter(Range(1, _n, 1), Function(sy_rows[sy_v] == sy_i, sy_v)), sy_i),
Range(1, Fold(Function(fh_a +
(1 if sy_shape[fh_r] > 0 else 0), fh_a, fh_r), 0, Range(1, _n, 1)), 1),
),
Drop(sy_end, _n + 1),
),
Apply(
(sy_u_init: list<integer>) => Fold((sy_u: list<integer>, sy_t) => Apply(
(sy_u_next: list<integer>) => sy_u_next,
Apply(
(sy_s: list<integer>) => Apply((sy_o: list<integer>) => Apply(
(sy_p: list<integer>) => Join([sy_p[1]], ReplaceAt(sy_s, sy_p[2], sy_s[sy_p[2]] - 1), ReplaceAt(sy_o, _n + 1 -
sy_t, sy_p[2])),
Apply((sy_c_init: list<integer>) => Fold((sy_c: list<integer>, sy_j) => Apply(
(sy_c_next: list<integer>) => sy_c_next,
sy_c if sy_c[2] != 0 else Apply(
(sy_k: integer) => [sy_c[1], sy_j] if sy_c[1] < sy_k else [sy_c[1] - sy_k, 0],
Apply((sy_less: list<integer>) => Apply(
(fh_L: integer) => Apply((fh_M: integer) => Apply(
(fh_C: list<integer>) => Fold(Function(Apply(
(fh_e: integer) => Fold(Function(fh_w * fh_p, fh_w, fh_k), fh_acc, Range(1, fh_e, 1)),
Apply((fh_st_init: list<integer>) => Fold((fh_st: list<integer>, fh_j) => Apply(
(fh_st_next: list<integer>) => fh_st_next,
fh_st if fh_st[2] > _n else Apply((fh_q: integer) => [fh_st[1] +
((fh_M -
fh_M % fh_q) /
fh_q -
Fold(Function(fh_a +
Fold(Function(fh_b +
(1 if (sy_less[fh_r] - fh_c +
(fh_C[fh_c] - fh_r) +
1) %
fh_q ==
0 else 0), fh_b, fh_c), 0, Range(1, sy_less[fh_r], 1)), fh_a, fh_r), 0, Range(1, fh_L, 1))), fh_q * fh_p], fh_st[2]),
), fh_st_init, Range(1, _n, 1)), [0, fh_p])[1],
) if Fold(Function(ok_fh_d &&
fh_p % fh_d !=
0, ok_fh_d, fh_d), True, Range(2, fh_p - 1, 1)) else fh_acc, fh_acc, fh_p), 1, Range(2, _n, 1)),
Map(Function(Fold(Function(fh_a +
(1 if sy_less[fh_r] >= fh_c else 0), fh_a, fh_r), 0, Range(1, fh_L, 1)), fh_c), Range(1, _n, 1)),
), Fold(Function(fh_a + sy_less[fh_r], fh_a, fh_r), 0, Range(1, _n, 1))),
Fold(Function(fh_a +
(1 if sy_less[fh_r] > 0 else 0), fh_a, fh_r), 0, Range(1, _n, 1)),
), ReplaceAt(sy_s, sy_j, sy_s[sy_j] - 1)),
) if (sy_s[sy_j] > 0 if sy_j == _n else sy_s[sy_j] > 0 &&
sy_s[sy_j] >
sy_s[sy_j + 1]) else sy_c,
), sy_c_init, Range(1, _n, 1)), [sy_u[1], 0]),
), Drop(sy_u, _n + 1)),
Take(Drop(sy_u, 1), _n),
),
), sy_u_init, Range(1, _n, 1)),
Join(
[sy_found[1]],
sy_shape,
Map(
Function(0, sy_z),
Range(1, _n, 1),
),
),
),
),
Apply(
(sy_parts: list<integer>) => Join(
sy_parts,
Map(
Function(0, sy_z),
Range(1, _n - Length(sy_parts), 1),
),
),
Apply((sy_pr: integer) => Drop(Fold(
Function(Apply((pw_m: integer) => Apply((pw_c: integer) => Apply((pw_r: integer) => pw_u if pw_m == 0 else Apply(
(pw_chosen: list<integer>) => Join([pw_m - pw_chosen[2], pw_chosen[2], pw_chosen[1]], Drop(pw_u, 3), [pw_chosen[2]]),
Fold(
Function(pw_pick if pw_pick[2] != 0 else Apply(
(pw_k: integer) => [pw_pick[1], pw_p] if pw_pick[1] < pw_k else [pw_pick[1] - pw_k, 0],
_tables[(pw_m - pw_p) *
(_n + 1) + pw_p + 1],
) if True else pw_pick, pw_pick, pw_p),
[pw_r, 0],
Range(Min(pw_m, pw_c), 1, -1),
),
), pw_u[3]), pw_u[2]), pw_u[1]), pw_u, pw_i),
[_n, _n, sy_pr],
Range(1, _n, 1),
), 3), sy_found[2]),
),
),
Apply((sy_f_init: list<integer>) => Fold(
(sy_f: list<integer>, sy_i) => Apply(
(sy_f_next: list<integer>) => sy_f_next,
sy_f if sy_f[2] >= 0 else Apply(
(sy_w: integer) => [sy_f[1], sy_i] if sy_f[1] < sy_w else [sy_f[1] - sy_w, -1],
_tables[(_n + 1) *
(_n + 1) + sy_i + 1],
),
),
sy_f_init,
Range(
0,
_tables[_n * (_n + 1) +
_n + 1] - 1,
1,
),
), [_r, -1]),
)rank(_n, _x)
Apply((sy_h: list<integer>) => Apply(
(sy_place: integer) => Apply(
(sy_o: list<integer>) => Fold(
Function(sy_b +
_tables[(_n + 1) *
(_n + 1) + sy_i + 1], sy_b, sy_i),
0,
Range(0, sy_place - 1, 1),
) +
Apply(
(sy_u_init: list<integer>) => Fold((sy_u: list<integer>, sy_v) => Apply(
(sy_u_next: list<integer>) => sy_u_next,
Apply((sy_s: list<integer>) => Apply((sy_t: integer) => Join([sy_u[1] +
Fold(Function(sy_a +
(Apply(
(sy_k: integer) => sy_k,
Apply((sy_less: list<integer>) => Apply(
(fh_L: integer) => Apply((fh_M: integer) => Apply(
(fh_C: list<integer>) => Fold(Function(Apply(
(fh_e: integer) => Fold(Function(fh_w * fh_p, fh_w, fh_k), fh_acc, Range(1, fh_e, 1)),
Apply((fh_st_init: list<integer>) => Fold((fh_st: list<integer>, fh_j) => Apply(
(fh_st_next: list<integer>) => fh_st_next,
fh_st if fh_st[2] > _n else Apply((fh_q: integer) => [fh_st[1] +
((fh_M -
fh_M % fh_q) /
fh_q -
Fold(Function(fh_a +
Fold(Function(fh_b +
(1 if (sy_less[fh_r] - fh_c +
(fh_C[fh_c] - fh_r) +
1) %
fh_q ==
0 else 0), fh_b, fh_c), 0, Range(1, sy_less[fh_r], 1)), fh_a, fh_r), 0, Range(1, fh_L, 1))), fh_q * fh_p], fh_st[2]),
), fh_st_init, Range(1, _n, 1)), [0, fh_p])[1],
) if Fold(Function(ok_fh_d &&
fh_p % fh_d !=
0, ok_fh_d, fh_d), True, Range(2, fh_p - 1, 1)) else fh_acc, fh_acc, fh_p), 1, Range(2, _n, 1)),
Map(Function(Fold(Function(fh_a +
(1 if sy_less[fh_r] >= fh_c else 0), fh_a, fh_r), 0, Range(1, fh_L, 1)), fh_c), Range(1, _n, 1)),
), Fold(Function(fh_a + sy_less[fh_r], fh_a, fh_r), 0, Range(1, _n, 1))),
Fold(Function(fh_a +
(1 if sy_less[fh_r] > 0 else 0), fh_a, fh_r), 0, Range(1, _n, 1)),
), ReplaceAt(sy_s, sy_j, sy_s[sy_j] - 1)),
) if sy_j < sy_t &&
(sy_s[sy_j] > 0 if sy_j == _n else sy_s[sy_j] > 0 &&
sy_s[sy_j] >
sy_s[sy_j + 1]) else 0), sy_a, sy_j), 0, Range(1, _n, 1))], ReplaceAt(sy_s, sy_t, sy_s[sy_t] - 1)), sy_o[sy_v]), Drop(sy_u, 1)),
), sy_u_init, Range(_n, 1, -1)),
Join(
[0],
Apply(
(sy_parts: list<integer>) => Join(sy_parts, Map(Function(0, sy_z), Range(1, _n - Length(sy_parts), 1))),
sy_h,
),
),
)[1],
Apply(
(sy_a_init: list<integer>) => Fold(
(sy_a: list<integer>, sy_i) => Apply(
(sy_a_next: list<integer>) => sy_a_next,
Apply((sy_r: list<integer>) => Apply((sy_m_init: list<integer>) => Fold(
(sy_m: list<integer>, sy_k) => Apply((sy_m_next: list<integer>) => sy_m_next, ReplaceAt(sy_m, sy_r[sy_k], sy_i)),
sy_m_init,
Range(1, Length(sy_r), 1),
), sy_a), _x[sy_i]),
),
sy_a_init,
Range(1, Length(_x), 1),
),
Map(
Function(0, sy_z),
Range(1, _n, 1),
),
),
),
Fold(
Function(Apply((pw_r: integer) => Apply(
(pw_m: integer) => Apply((pw_c: integer) => [pw_r +
Fold(
Function(pw_s +
(_tables[(pw_m - pw_q) *
(_n + 1) + pw_q + 1] if True else 0), pw_s, pw_q),
0,
Range(pw_x + 1, Min(pw_m, pw_c), 1),
), pw_m - pw_x, pw_x], pw_a[3]),
pw_a[2],
), pw_a[1]), pw_a, pw_x),
[0, _n, _n],
sy_h,
)[1],
), Map(
Function(Apply(
(sy_r: list<integer>) => Length(sy_r),
_x[sy_i],
), sy_i),
Range(1, Length(_x), 1),
))valid(_n, _x)
Length(_x) == 0 if _n == 0 else Fold(
Function(ok_va_i && Apply(
(va_r: list<integer>) => Length(va_r) >= 1,
_x[va_i],
), ok_va_i, va_i),
True,
Range(1, Length(_x), 1),
) && Fold(
Function(ok_va_h && Apply(
(va_r: list<integer>) => Apply(
(va_q: list<integer>) => Length(va_r) <= Length(va_q),
_x[va_h - 1],
),
_x[va_h],
), ok_va_h, va_h),
True,
Range(2, Length(_x), 1),
) && Fold(
Function(
va_t +
Apply(
(va_r: list<integer>) => Length(va_r),
_x[va_i],
),
va_t,
va_i,
),
0,
Range(1, Length(_x), 1),
) == _n && Fold(
Function(ok_va_j &&
Apply(
(va_r: list<integer>) => Fold(
Function(ok_va_k &&
va_r[va_k] >= 1 &&
va_r[va_k] <= _n, ok_va_k, va_k),
True,
Range(1, Length(va_r), 1),
),
_x[va_j],
), ok_va_j, va_j),
True,
Range(
1,
Length(_x),
1,
),
) && Apply(
(va_c: list<integer>) => Fold(
Function(ok_va_v &&
va_c[va_v] == 1, ok_va_v, va_v),
True,
Range(1, _n, 1),
),
Fold(
Function(Apply((va_r: list<integer>) => Fold(
Function(ReplaceAt(va_m, va_r[va_k], va_m[va_r[va_k]] + 1), va_m, va_k),
va_a,
Range(1, Length(va_r), 1),
), _x[va_i]), va_a, va_i),
Map(
Function(0, sy_z),
Range(1, _n, 1),
),
Range(1, Length(_x), 1),
),
) &&
Fold(
Function(ok_va_g && Apply(
(va_r: list<integer>) => Fold(
Function(ok_va_l &&
va_r[va_l - 1] <
va_r[va_l], ok_va_l, va_l),
True,
Range(2, Length(va_r), 1),
),
_x[va_g],
), ok_va_g, va_g),
True,
Range(1, Length(_x), 1),
) && Fold(
Function(ok_va_f && Apply(
(va_r: list<integer>) => Apply(
(va_q: list<integer>) => Fold(
Function(ok_va_m &&
va_q[va_m] < va_r[va_m], ok_va_m, va_m),
True,
Range(1, Length(va_r), 1),
),
_x[va_f - 1],
),
_x[va_f],
), ok_va_f, va_f),
True,
Range(2, Length(_x), 1),
)tables(_n)
Apply(
(_tables: list<integer>) => Join(
_tables,
Map(Function(Apply(
(sy_shape: list<integer>) => Apply(
(fh_L: integer) => Apply(
(fh_M: integer) => Apply(
(fh_C: list<integer>) => Fold(
Function(Apply(
(fh_e: integer) => Fold(Function(fh_w * fh_p, fh_w, fh_k), fh_acc, Range(1, fh_e, 1)),
Apply((fh_st_init: list<integer>) => Fold((fh_st: list<integer>, fh_j) => Apply(
(fh_st_next: list<integer>) => fh_st_next,
fh_st if fh_st[2] > _n else Apply((fh_q: integer) => [fh_st[1] +
((fh_M -
fh_M % fh_q) /
fh_q -
Fold(Function(fh_a +
Fold(Function(fh_b +
(1 if (sy_shape[fh_r] - fh_c +
(fh_C[fh_c] - fh_r) +
1) %
fh_q ==
0 else 0), fh_b, fh_c), 0, Range(1, sy_shape[fh_r], 1)), fh_a, fh_r), 0, Range(1, fh_L, 1))), fh_q * fh_p], fh_st[2]),
), fh_st_init, Range(1, _n, 1)), [0, fh_p])[1],
) if Fold(Function(ok_fh_d &&
fh_p % fh_d !=
0, ok_fh_d, fh_d), True, Range(2, fh_p - 1, 1)) else fh_acc, fh_acc, fh_p),
1,
Range(2, _n, 1),
),
Map(
Function(Fold(Function(fh_a +
(1 if sy_shape[fh_r] >= fh_c else 0), fh_a, fh_r), 0, Range(1, fh_L, 1)), fh_c),
Range(1, _n, 1),
),
),
Fold(
Function(fh_a + sy_shape[fh_r], fh_a, fh_r),
0,
Range(1, _n, 1),
),
),
Fold(
Function(fh_a +
(1 if sy_shape[fh_r] > 0 else 0), fh_a, fh_r),
0,
Range(1, _n, 1),
),
),
Apply(
(sy_parts: list<integer>) => Join(
sy_parts,
Map(
Function(0, sy_z),
Range(1, _n - Length(sy_parts), 1),
),
),
Apply((sy_pr: integer) => Drop(Fold(
Function(Apply((pw_m: integer) => Apply((pw_c: integer) => Apply((pw_r: integer) => pw_u if pw_m == 0 else Apply(
(pw_chosen: list<integer>) => Join([pw_m - pw_chosen[2], pw_chosen[2], pw_chosen[1]], Drop(pw_u, 3), [pw_chosen[2]]),
Fold(
Function(pw_pick if pw_pick[2] != 0 else Apply(
(pw_k: integer) => [pw_pick[1], pw_p] if pw_pick[1] < pw_k else [pw_pick[1] - pw_k, 0],
_tables[(pw_m - pw_p) *
(_n + 1) + pw_p + 1],
) if True else pw_pick, pw_pick, pw_p),
[pw_r, 0],
Range(Min(pw_m, pw_c), 1, -1),
),
), pw_u[3]), pw_u[2]), pw_u[1]), pw_u, pw_i),
[_n, _n, sy_pr],
Range(1, _n, 1),
), 3), sy_i),
),
), sy_i), Range(
0,
_tables[_n *
(_n + 1) + _n + 1] -
1,
1,
)),
),
Fold(Function(Join(
pw_t,
Fold(
Function(ReplaceAt(
pw_row,
pw_c + 1,
Fold(
Function(pw_a +
(pw_t[(pw_s -
pw_p) *
(_n +
1) +
pw_p +
1] if True else 0), pw_a, pw_p),
0,
Range(1, Min(
pw_s,
pw_c,
), 1),
),
), pw_row, pw_c),
Map(Function(0, pw_z), Range(0, _n + 1 - 1, 1)),
Range(0, _n + 1 - 1, 1),
),
), pw_t, pw_s), Fold(
Function(
ReplaceAt(
pw_row,
pw_c + 1,
1,
),
pw_row,
pw_c,
),
Map(
Function(0, pw_z),
Range(0, _n + 1 - 1, 1),
),
Range(0, _n + 1 - 1, 1),
), Range(1, _n + 1 - 1, 1)),
)Statistics
On StandardTableau, called as CombinatorialStat(x, "Name").
- AdjacentSuccessorCountSt000743Entries whose successor is the neighbor to their right or directly below them.
- AscentCountIncludingLargestEntrySt000507Entries whose successor is in the same or a higher row, and the largest entry.
- AttackingInversionCountSt000017Attacking pairs of cells whose entries are out of order: the cell in the lower row, strictly east of the other, holds the larger entry.
- AttackingPairCountSt000016Pairs of cells of the shape with one strictly west of the other in a row, or the first in the row below and strictly east of the second.
- ChargeSt000009The charge of the reading word: the sum of n - e over the entries e whose successor is not in a lower row.
- CochargeSt000169The cocharge of the reading word: the sum of n - e over the entries e whose successor is in a lower row.
- ComajorIndexMinusWeightedSizeSt001698The sum of n - e over the descents e of the tableau, less the weighted size of its shape.
- CylindricalTableauOverlapSt001803The number of rows, from the top, as long as the first row and starting, from the bottom, above the last entry of the first row.
- FirstColumnInitialSequenceLengthSt000745The largest k such that the first column starts 1, 2, ..., k.
- FirstEntryInLastRowSt000738The first entry in the last row.
- HaglundStevensInversionCountSt000059The pairs of a cell's entry and a smaller entry lying below the cell's inversion path, over all cells.
- LastEntryInFirstRowSt000734The last entry in the first row.
- LastEntryOnMainDiagonalSt000735The last entry on the main diagonal.
- MajorIndexMinusWeightedSizeSt001699The major index of the tableau less the weighted size of its shape.
- MinimalCylindricalInnerHeightSt001804The number of rows less the overlap of the cylindrical tableau.
- ModularMajorIndexSt000693The major index modulo the number of entries.
- NaturalComajorIndexSt001695The sum of n - e over the natural descents e, the entries whose successor is in a strictly higher row.
- NaturalDescentCountSt001712Entries whose successor is in a strictly higher row.
- NaturalMajorIndexSt001696The sum of the natural descents, the entries whose successor is in a strictly higher row.
- PathLengthToLargestEntrySt000744The length of the path from the top left cell to the largest entry, one step per cell down or to the right.
- RowOfLargestEntrySt000733The row containing the largest entry.
- ShiftedNaturalComajorIndexSt001697The sum of n - e over the natural descents e, plus the sum of (r - 1) times the length of row r.
- ShynarInversionCountSt000057Pairs of entries e < f with f strictly southwest of e.
- SmallestCylindricShiftSt001993The least shift s at which each entry of the last row is smaller than the first row's entry s columns on.
- WeightedSizeSt000336The sum of the leg lengths of the cells, the sum over the cells of their row counted from 0.
Maps
Into and out of StandardTableau, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From StandardTableau
- CatabolismStandardTableau → StandardTableauGraded mapMp00106Remove the first row and column-insert its entries back into the rest, largest first.
- EvacuationStandardTableau → StandardTableauinvolutionBijectionGraded mapInvolutionMp00085Schützenberger's evacuation (involution): remove the entry 1, slide the rest in, and give the cell that empties the largest label, until nothing is left.
- InverseTableauPromotionStandardTableau → StandardTableauinverseBijectionGraded mapMp00153Inverse promotion: replace the entry 1 by n + 1, slide it out to the rim, and subtract one from every entry.
- PeakCompositionStandardTableau → IntegerCompositionGraded mapMp00294The composition cut at the peaks: entries i that are descents after an ascent.
- ReadingWordStandardTableau → PermutationInjectionGraded mapMp00081The rows read left to right, from the bottom row up, as a permutation.
- RowDescentsToColumnDescentsStandardTableau → StandardTableaubijectionBijectionGraded mapMp00226A standard tableau of the same shape whose column descents are the original's row descents.
- RowSetPartitionStandardTableau → SetPartitionInjectionGraded mapMp00284The set partition whose blocks are the rows of the tableau.
- TableauDescentWordStandardTableau → BinaryWordsurjectionSurjectionGraded mapMp00134Letter i is 1 when entry i + 1 sits in a lower row than entry i.
- TableauPromotionStandardTableau → StandardTableauinverseBijectionGraded mapMp00155Promotion: replace the largest entry by a hole, slide it to the corner at the origin, and add one to every entry.
- TableauShapeStandardTableau → IntegerPartitionsurjectionSurjectionGraded mapMp00083The shape of a standard tableau: its row lengths.
- TransposeTableauStandardTableau → StandardTableauinvolutionBijectionGraded mapInvolutionMp00084The conjugate tableau: rows and columns exchanged.
- ValleyCompositionStandardTableau → IntegerCompositionGraded mapMp00295The composition cut at the valleys: entries i that are ascents after a descent.
To StandardTableau
- AssociatedStandardTableauSetPartition → StandardTableauSurjectionMp00258The standard tableau whose j-th column holds the j-th smallest elements of the blocks, in increasing order.
- InitialTableauIntegerPartition → StandardTableauInjectionGraded mapMp00042The standard tableau of the shape filled row by row with 1, 2, ..., n.
- ReadingTableauIntegerPartition → StandardTableauInjectionGraded mapMp00045The recording tableau of the row reading word of the shape filled row by row.
- RskInsertionPermutation → StandardTableausurjectionSurjectionGraded mapMp00059The insertion tableau of the RSK correspondence.
- RskRecordingPermutation → StandardTableausurjectionSurjectionGraded mapMp00070The recording tableau of the RSK correspondence, as its rows.
- TwoRowTableauDyckPath → StandardTableauInjectionGraded mapMp00033The standard tableau of shape (n, n) with the positions of the up steps in its first row and of the down steps in its second.
Enumeration
Examples
About
| Examples | 2 |
|---|---|
| Checked against | Combinatorica 2 agree |
| Crosswalk | WikipediaMathWorldWikidatanLabOEISCombinatoricaSageMathmathlib4 |
Implementation
mapped
combinatoricapackages/oracle/src/mappings.tsCombinatorica lists the tableaux of one shape; ours are all standard tableaux with n cells, the union over the partitions of n.