StandardTableauPairs
Pairs of same-shape standard Young tableaux with cells — the RSK codomain — as a lazy indexed family of .
OEIS
A000142SageMathsage.combinat.rsk.RSKStandardTableauPairs(size)the pairs of size size, in bijection with the permutations of size via RSK.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<standard_tableau_pair> | combinatorics | always |
Details
- A lazy indexed collection: , exact and closed-form, since Robinson–Schensted–Knuth is a bijection . See Factorial.
- Each element is a
StandardTableauPair, its two same-shape tableaux each aStandardTableau, as rows; unranking goes through SymmetricGroup's permutation unrank, then forward RSK insertion. - Ranking inverts RSK back to a permutation and reads off SymmetricGroup's rank — so the two families share one underlying order.
Definition
Epsil, as the implementation runs it.
count(_n)
_n!unrank(_n, _r)
Apply(
(rk_raw: list<integer>) => Apply((rk_rsk_len: integer) => Apply(
(rk_rsk_state: list<integer>) => [
Map(
Function(Map(Function(rk_rsk_state[rk_rsk_len +
(fl_r - 1) *
rk_rsk_len +
fl_c], fl_c), Range(1, rk_rsk_state[fl_r], 1)), fl_r),
Range(1, Count(Filter(
Range(1, rk_rsk_len, 1),
Function(rk_rsk_state[fl_q] > 0, fl_q),
)), 1),
),
Map(
Function(Map(Function(rk_rsk_state[rk_rsk_len +
rk_rsk_len * rk_rsk_len +
(fl_r - 1) *
rk_rsk_len +
fl_c], fl_c), Range(1, rk_rsk_state[fl_r], 1)), fl_r),
Range(1, Count(Filter(
Range(1, rk_rsk_len, 1),
Function(rk_rsk_state[fl_q] > 0, fl_q),
)), 1),
),
],
Apply((rk_rsk_w: list<integer>) => Apply((rk_rsk_n: integer) => Apply((rk_rsk_nn: integer) => Apply(
(rk_rsk_row: list<integer>) => Apply(
(rk_rsk_col: list<integer>) => Apply(
(rk_rsk_s_init: list<integer>) => Fold((rk_rsk_s: list<integer>, rk_rsk_k) => Apply(
(rk_rsk_s_next: list<integer>) => rk_rsk_s_next,
Apply(
(rk_rsk_chain: list<integer>) => Join(
Apply((rk_rsk_q_built_init: list<integer>) => Fold(
(rk_rsk_q_built: list<integer>, rk_rsk_q) => Apply((rk_rsk_q_built_next: list<integer>) => rk_rsk_q_built_next, Join(rk_rsk_q_built, [rk_rsk_s[rk_rsk_q] + 1 if rk_rsk_chain[2rk_rsk_q] ==
rk_rsk_s[rk_rsk_q] + 1 else rk_rsk_s[rk_rsk_q]])),
rk_rsk_q_built_init,
Range(1, rk_rsk_n, 1),
), []),
Apply((rk_rsk_j_built_init: list<integer>) => Fold((rk_rsk_j_built: list<integer>, rk_rsk_j) => Apply(
(rk_rsk_j_built_next: list<integer>) => rk_rsk_j_built_next,
Join(rk_rsk_j_built, [Apply((rk_rsk_q: integer) => Apply((rk_rsk_c: integer) => rk_rsk_chain[2rk_rsk_q - 1] if rk_rsk_chain[2rk_rsk_q] == rk_rsk_c else rk_rsk_s[rk_rsk_n +
(rk_rsk_q - 1) *
rk_rsk_n +
rk_rsk_c], rk_rsk_col[rk_rsk_j]), rk_rsk_row[rk_rsk_j])]),
), rk_rsk_j_built_init, Range(1, rk_rsk_nn, 1)), []),
Apply((rk_rsk_j_built_init: list<integer>) => Fold((rk_rsk_j_built: list<integer>, rk_rsk_j) => Apply(
(rk_rsk_j_built_next: list<integer>) => rk_rsk_j_built_next,
Join(rk_rsk_j_built, [Apply((rk_rsk_q: integer) => Apply((rk_rsk_c: integer) => rk_rsk_k if rk_rsk_chain[2rk_rsk_q] == rk_rsk_c &&
rk_rsk_chain[2rk_rsk_q] ==
rk_rsk_s[rk_rsk_q] + 1 else rk_rsk_s[rk_rsk_n + rk_rsk_nn +
(rk_rsk_q - 1) *
rk_rsk_n +
rk_rsk_c], rk_rsk_col[rk_rsk_j]), rk_rsk_row[rk_rsk_j])]),
), rk_rsk_j_built_init, Range(1, rk_rsk_nn, 1)), []),
),
Apply((rk_rsk_acc_init: list<integer>) => Fold((rk_rsk_acc: list<integer>, rk_rsk_q) => Apply(
(rk_rsk_acc_next: list<integer>) => rk_rsk_acc_next,
Apply((rk_rsk_v: integer) => Apply((rk_rsk_l: integer) => Apply(
(rk_rsk_p: integer) => Join(rk_rsk_acc, [rk_rsk_p, 0 if rk_rsk_v == 0 ||
rk_rsk_p > rk_rsk_l else rk_rsk_s[rk_rsk_n +
(rk_rsk_q - 1) *
rk_rsk_n +
rk_rsk_p]]),
0 if rk_rsk_v == 0 else 1 +
Count(Filter(Range(1, rk_rsk_l, 1), Function(rk_rsk_s[rk_rsk_n +
(rk_rsk_q - 1) *
rk_rsk_n +
rk_rsk_c] <
rk_rsk_v, rk_rsk_c))),
), rk_rsk_s[rk_rsk_q]), rk_rsk_acc[2rk_rsk_q - 1]),
), rk_rsk_acc_init, Range(1, rk_rsk_n, 1)), [rk_rsk_w[rk_rsk_k]]),
),
), rk_rsk_s_init, Range(1, rk_rsk_n, 1)),
Map(Function(0, rk_rsk_j), Range(1, rk_rsk_n + 2rk_rsk_nn, 1)),
),
Map(Function((rk_rsk_j - 1) %
rk_rsk_n +
1, rk_rsk_j), Range(1, rk_rsk_nn, 1)),
),
Map(Function(Floor((rk_rsk_j - 1) /
rk_rsk_n) +
1, rk_rsk_j), Range(1, rk_rsk_nn, 1)),
), rk_rsk_n * rk_rsk_n), Length(rk_rsk_w)), rk_raw),
), Length(rk_raw)),
Map(Function(Fold(
Function(
v + 1 if v >= (_r - _r % (_n - i)!) / (_n -
i)! %
(_n - i + 1) + 1 else v,
v,
i,
),
(_r - _r % (_n - j)!) / (_n - j)! % (_n - j + 1) + 1,
Range(j - 1, 1, -1),
), j), Range(1, _n, 1)),
)rank(_n, _x)
Apply(
(rk_word: list<integer>) => Fold(
Function(r * (_n - j + 1) + (rk_word[j] -
1 - Fold(
Function(c +
(1 if rk_word[i] < rk_word[j] else 0), c, i),
0,
Range(1, j - 1, 1),
)), r, j),
0,
Range(1, _n, 1),
),
Fold(
Function(Apply((rk_t: list<any>) => Apply((rk_p: list<any>) => Apply((rk_q: list<any>) => Apply((rk_k: integer) => Apply(
(rk_r: integer) => Apply(
(rk_u: list<any>) => [
rk_u[1],
Take(rk_q, Count(rk_q) - 1) if Count(rk_q[rk_r]) == 1 else ReplaceAt(rk_q, rk_r, Take(rk_q[rk_r], Count(rk_q[rk_r]) - 1)),
ReplaceAt(rk_t[3], rk_k, rk_u[2]),
],
Fold(
Function(Apply((rk_b: list<any>) => Apply((rk_w: integer) => Apply((rk_row: list<integer>) => Apply(
(rk_pos: integer) => [ReplaceAt(rk_b[1], rk_w, ReplaceAt(rk_row, rk_pos, rk_b[2])), rk_row[rk_pos]],
Fold(Function(rk_m if rk_row[rk_m] < rk_b[2] else rk_g, rk_g, rk_m), 0, Range(1, Count(rk_row), 1)),
), rk_b[1][rk_w]), rk_r - rk_j), rk_a), rk_a, rk_j),
[Take(rk_p, Count(rk_p) - 1) if Count(rk_p[rk_r]) == 1 else ReplaceAt(rk_p, rk_r, Take(rk_p[rk_r], Count(rk_p[rk_r]) - 1)), rk_p[rk_r][Count(rk_p[rk_r])]],
Range(1, rk_r - 1, 1),
),
),
Fold(
Function(rk_i if rk_q[rk_i][Count(rk_q[rk_i])] == rk_k else rk_f, rk_f, rk_i),
0,
Range(1, Count(rk_q), 1),
),
), _n + 1 -
rk_c), rk_t[2]), rk_t[1]), rk_s), rk_s, rk_c),
[_x[1], _x[2], Map(Function(0, rk_z), Range(1, _n, 1))],
Range(1, _n, 1),
)[3],
)valid(_n, _x)
((Apply((rk_a: list<list<integer>>) => Length(rk_a) == 0 if _n == 0 else Fold(
Function(ok_va_i &&
Apply(
(va_r: list<integer>) => Length(va_r) >= 1,
rk_a[va_i],
), ok_va_i, va_i),
True,
Range(1, Length(rk_a), 1),
) &&
Fold(
Function(ok_va_h &&
Apply((va_r: list<integer>) => Apply(
(va_q: list<integer>) => Length(va_r) <= Length(va_q),
rk_a[va_h - 1],
), rk_a[va_h]), ok_va_h, va_h),
True,
Range(2, Length(rk_a), 1),
) &&
Fold(
Function(va_t +
Apply((va_r: list<integer>) => Length(va_r), rk_a[va_i]), va_t, va_i),
0,
Range(1, Length(rk_a), 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),
), rk_a[va_j]), ok_va_j, va_j),
True,
Range(1, Length(rk_a), 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),
), rk_a[va_i]), va_a, va_i),
Map(
Function(0, sy_z),
Range(1, _n, 1),
),
Range(1, Length(rk_a), 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),
), rk_a[va_g]), ok_va_g, va_g),
True,
Range(1, Length(rk_a), 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)),
rk_a[va_f - 1],
), rk_a[va_f]), ok_va_f, va_f),
True,
Range(2, Length(rk_a), 1),
), _x[1]) &&
Apply((rk_a: list<list<integer>>) => Length(rk_a) == 0 if _n == 0 else Fold(
Function(ok_va_i &&
Apply(
(va_r: list<integer>) => Length(va_r) >= 1,
rk_a[va_i],
), ok_va_i, va_i),
True,
Range(1, Length(rk_a), 1),
) &&
Fold(
Function(ok_va_h &&
Apply((va_r: list<integer>) => Apply(
(va_q: list<integer>) => Length(va_r) <= Length(va_q),
rk_a[va_h - 1],
), rk_a[va_h]), ok_va_h, va_h),
True,
Range(2, Length(rk_a), 1),
) &&
Fold(
Function(va_t +
Apply((va_r: list<integer>) => Length(va_r), rk_a[va_i]), va_t, va_i),
0,
Range(1, Length(rk_a), 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),
), rk_a[va_j]), ok_va_j, va_j),
True,
Range(1, Length(rk_a), 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),
), rk_a[va_i]), va_a, va_i),
Map(
Function(0, sy_z),
Range(1, _n, 1),
),
Range(1, Length(rk_a), 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),
), rk_a[va_g]), ok_va_g, va_g),
True,
Range(1, Length(rk_a), 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)),
rk_a[va_f - 1],
), rk_a[va_f]), ok_va_f, va_f),
True,
Range(2, Length(rk_a), 1),
), _x[2]) &&
Count(_x[1]) == Count(_x[2]) && 0 == Fold(
Function(rk_d + Abs(Count(_x[1][rk_h]) -
Count(_x[2][rk_h])), rk_d, rk_h),
0,
Range(1, Count(_x[1]), 1),
) if (False if _x[2] in Integers else Fold(
Function(ok_rk_i &&
(False if _x[2][rk_i] in
Integers else Fold(
Function(ok_rk_k &&
_x[2][rk_i][rk_k] in Integers, ok_rk_k, rk_k),
True,
Range(1, Count(_x[2][rk_i]), 1),
)), ok_rk_i, rk_i),
True,
Range(1, Count(_x[2]), 1),
)) else False) if (False if _x[1] in
Integers else Fold(
Function(ok_rk_i &&
(False if _x[1][rk_i] in Integers else Fold(
Function(ok_rk_k &&
_x[1][rk_i][rk_k] in Integers, ok_rk_k, rk_k),
True,
Range(1, Count(_x[1][rk_i]), 1),
)), ok_rk_i, rk_i),
True,
Range(1, Count(_x[1]), 1),
)) else False) if Length(_x) == 2 else FalseMaps
Into and out of StandardTableauPair, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From StandardTableauPair
- ToPermutationStandardTableauPair → PermutationinverseThe permutation an RSK pair comes from: inverse RSK.
To StandardTableauPair
- RskPermutation → StandardTableauPairThe RSK correspondence: the insertion and recording tableaux, as a pair.
Enumeration
Examples
1 more kept as data, checked against the oracles See also: SymmetricGroup, Factorial, Count, At