SeparablePermutations
The permutations of avoiding the patterns and , as a lazy indexed family.
OEIS
A006318SeparablePermutations(n)the permutations of built up by direct and skew sums.Typed signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<permutation> | combinatorics | always |
Details
- A lazy indexed collection; the count is the large Schröder numbers, A006318 —
- Each element is the one-line word; enumerates all permutations in lexicographic order and indexes into those avoiding and — there is no closed-form unrank of the permutation itself.
- Separable permutations are exactly those avoiding every non-trivial SimplePermutations pattern beyond length — every one decomposes recursively as a direct or skew sum.
Definition
Epsil, as the implementation runs it.
count(_n)
Apply((schroder: list<integer>) => Apply(
(prefix: list<integer>) => Apply((filled: integer) => (1 if _n == 0 else schroder[_n]) if filled == 0 else 0 if Fold(Function(spc_ ||
Fold(Function(spb_ ||
Fold(Function(spa_ ||
prefix[spc] < prefix[spa] &&
prefix[spa] < prefix[filled] &&
prefix[filled] < prefix[spb] ||
prefix[spb] < prefix[filled] &&
prefix[filled] < prefix[spa] &&
prefix[spa] < prefix[spc], spa_, spa), False, Range(1, spb - 1, 1)), spb_, spb), False, Range(1, spc - 1, 1)), spc_, spc), False, Range(1, filled - 1, 1)) else Apply(
(smin: list<integer>) => Apply(
(smax: list<integer>) => Apply((sw: integer) => Apply(
(stable: list<integer>) => (1 if _n == 0 else schroder[_n]) if 0 == filled else (1 if _n == 1 else 0) +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(1 - 1) +
1] +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(2 - 1) +
1] if 0 < filled &&
filled - 0 <=
_n &&
1 + _n -
1 <=
_n &&
smin[0 + 1] >=
1 &&
smax[0 + 1] <=
1 + _n -
1 else 0,
Fold(
Function(Join(
st_t,
Fold(Function(ReplaceAt(
st_row,
st_c + 1,
Apply((stq: integer) => Apply((stj: integer) => Apply((stl: integer) => (Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl + sc0 +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl + sc0 &&
smax[stj + sc0 +
1] <=
stl + sc0 +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl - 1)) +
(2 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold((sr: list<integer>, sc) => Apply(
(sr_next: list<integer>) => sr_next,
sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srm == stl &&
srx ==
stl + sc -
1 else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc])),
), sr_init, Range(1, filled - stj, 1)), [0, _n + 1, 0])[1],
) if st_c % 2 ==
0 else Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl &&
smax[stj + sc0 +
1] <=
stl +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl + st_s -
1 +
1 -
ss -
1)) +
(1 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold((sr: list<integer>, sc) => Apply(
(sr_next: list<integer>) => sr_next,
sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srx ==
stl + st_s -
1 &&
srm ==
stl + st_s -
1 +
1 -
sc else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc])),
), sr_init, Range(1, filled - stj, 1)), [0, _n + 1, 0])[1],
)) if stj < filled &&
filled - stj <=
st_s &&
stl + st_s -
1 <=
_n &&
smin[stj + 1] >=
stl &&
smax[stj + 1] <=
stl + st_s -
1 else 0, stq %
(_n + 1) +
1), (stq -
stq %
(_n + 1)) /
(_n + 1)), (st_c -
st_c % 2) /
2),
), st_row, st_c), Map(Function(0, st_z), Range(0, sw - 1, 1)), Range(0, sw - 1, 1)),
), st_t, st_s),
Fold(
Function(ReplaceAt(st_row, st_c + 1, 0), st_row, st_c),
Map(Function(0, st_z), Range(0, sw - 1, 1)),
Range(0, sw - 1, 1),
),
Range(1, _n + 1 -
1, 1),
),
), 2 * filled * (_n + 1)),
Fold(
Function(ReplaceAt(smj_l, smj - 1 +
1, Fold(Function(Max(sme, prefix[smq]), sme, smq), 0, Range(smj, filled, 1))), smj_l, smj),
Map(Function(0, smj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
),
Fold(
Function(ReplaceAt(snj_l, snj - 1 +
1, Fold(Function(Min(sne, prefix[snq]), sne, snq), _n + 1, Range(snj, filled, 1))), snj_l, snj),
Map(Function(0, snj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
), 0),
Map(
Function(0, lr_y),
Range(1, _n, 1),
),
), _tables)unrank(_n, _r)
Apply((schroder: list<integer>) => Take(Fold(Function(Apply(
(lr_chosen: list<integer>) => ReplaceAt(ReplaceAt(
ReplaceAt(lr_s, lr_j, lr_chosen[2]),
_n + 1,
lr_chosen[1],
), _n + 1 + lr_chosen[2], lr_j),
Fold(Function(lr_pick if lr_pick[2] != 0 else lr_pick if lr_s[_n + 1 + lr_v] !=
0 else Apply(
(lr_c: integer) => [lr_pick[1], lr_v] if lr_pick[1] < lr_c else [lr_pick[1] - lr_c, 0],
Apply((prefix: list<integer>) => Apply((filled: integer) => (1 if _n == 0 else schroder[_n]) if filled == 0 else 0 if Fold(Function(spc_ ||
Fold(Function(spb_ ||
Fold(Function(spa_ ||
prefix[spc] < prefix[spa] &&
prefix[spa] < prefix[filled] &&
prefix[filled] < prefix[spb] ||
prefix[spb] < prefix[filled] &&
prefix[filled] < prefix[spa] &&
prefix[spa] < prefix[spc], spa_, spa), False, Range(1, spb - 1, 1)), spb_, spb), False, Range(1, spc - 1, 1)), spc_, spc), False, Range(1, filled - 1, 1)) else Apply(
(smin: list<integer>) => Apply(
(smax: list<integer>) => Apply((sw: integer) => Apply(
(stable: list<integer>) => (1 if _n == 0 else schroder[_n]) if 0 == filled else (1 if _n == 1 else 0) +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(1 - 1) +
1] +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(2 - 1) +
1] if 0 < filled &&
filled - 0 <=
_n &&
1 + _n -
1 <=
_n &&
smin[0 + 1] >=
1 &&
smax[0 + 1] <=
1 + _n -
1 else 0,
Fold(Function(Join(
st_t,
Fold(Function(ReplaceAt(
st_row,
st_c + 1,
Apply((stq: integer) => Apply((stj: integer) => Apply((stl: integer) => (Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl + sc0 +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl + sc0 &&
smax[stj + sc0 +
1] <=
stl + sc0 +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl - 1)) +
(2 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold(
(sr: list<integer>, sc) => Apply((sr_next: list<integer>) => sr_next, sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srm == stl &&
srx ==
stl + sc -
1 else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc]))),
sr_init,
Range(1, filled - stj, 1),
), [0, _n + 1, 0])[1],
) if st_c % 2 ==
0 else Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl &&
smax[stj + sc0 +
1] <=
stl +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl + st_s -
1 +
1 -
ss -
1)) +
(1 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold((sr: list<integer>, sc) => Apply(
(sr_next: list<integer>) => sr_next,
sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srx ==
stl + st_s -
1 &&
srm ==
stl + st_s -
1 +
1 -
sc else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc])),
), sr_init, Range(1, filled - stj, 1)), [0, _n + 1, 0])[1],
)) if stj < filled &&
filled - stj <=
st_s &&
stl + st_s -
1 <=
_n &&
smin[stj + 1] >=
stl &&
smax[stj + 1] <=
stl + st_s -
1 else 0, stq %
(_n + 1) +
1), (stq -
stq %
(_n + 1)) /
(_n + 1)), (st_c -
st_c % 2) /
2),
), st_row, st_c), Map(Function(0, st_z), Range(0, sw - 1, 1)), Range(0, sw - 1, 1)),
), st_t, st_s), Fold(
Function(ReplaceAt(st_row, st_c + 1, 0), st_row, st_c),
Map(Function(0, st_z), Range(0, sw - 1, 1)),
Range(0, sw - 1, 1),
), Range(1, _n + 1 -
1, 1)),
), 2 * filled * (_n + 1)),
Fold(
Function(ReplaceAt(smj_l, smj - 1 +
1, Fold(Function(Max(sme, prefix[smq]), sme, smq), 0, Range(smj, filled, 1))), smj_l, smj),
Map(Function(0, smj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
),
Fold(
Function(ReplaceAt(snj_l, snj - 1 +
1, Fold(Function(Min(sne, prefix[snq]), sne, snq), _n + 1, Range(snj, filled, 1))), snj_l, snj),
Map(Function(0, snj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
), lr_j), ReplaceAt(lr_s, lr_j, lr_v)),
), lr_pick, lr_v), [lr_s[_n + 1], 0], Range(1, _n, 1)),
), lr_s, lr_j), Join(
Map(
Function(0, lr_y),
Range(1, _n, 1),
),
[_r],
Map(
Function(0, lr_y2),
Range(1, _n, 1),
),
), Range(1, _n, 1)), _n), _tables)rank(_n, _x)
Apply((schroder: list<integer>) => Apply(
(lr_where: list<integer>) => Fold(Function(lr_r +
Apply(
(lr_base: list<integer>) => Fold(Function(lr_r2 +
(Apply((prefix: list<integer>) => Apply((filled: integer) => (1 if _n == 0 else schroder[_n]) if filled == 0 else 0 if Fold(Function(spc_ ||
Fold(Function(spb_ ||
Fold(Function(spa_ ||
prefix[spc] < prefix[spa] &&
prefix[spa] < prefix[filled] &&
prefix[filled] < prefix[spb] ||
prefix[spb] < prefix[filled] &&
prefix[filled] < prefix[spa] &&
prefix[spa] < prefix[spc], spa_, spa), False, Range(1, spb - 1, 1)), spb_, spb), False, Range(1, spc - 1, 1)), spc_, spc), False, Range(1, filled - 1, 1)) else Apply(
(smin: list<integer>) => Apply(
(smax: list<integer>) => Apply((sw: integer) => Apply(
(stable: list<integer>) => (1 if _n == 0 else schroder[_n]) if 0 == filled else (1 if _n == 1 else 0) +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(1 - 1) +
1] +
stable[_n * sw +
2 *
((_n + 1) *
0 +
(1 - 1)) +
(2 - 1) +
1] if 0 < filled &&
filled - 0 <=
_n &&
1 + _n -
1 <=
_n &&
smin[0 + 1] >=
1 &&
smax[0 + 1] <=
1 + _n -
1 else 0,
Fold(Function(Join(
st_t,
Fold(Function(ReplaceAt(
st_row,
st_c + 1,
Apply((stq: integer) => Apply((stj: integer) => Apply((stl: integer) => (Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl + sc0 -
1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl + sc0 +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl + sc0 &&
smax[stj + sc0 +
1] <=
stl + sc0 +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl - 1)) +
(2 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold(
(sr: list<integer>, sc) => Apply((sr_next: list<integer>) => sr_next, sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srm == stl &&
srx ==
stl + sc -
1 else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc]))),
sr_init,
Range(1, filled - stj, 1),
), [0, _n + 1, 0])[1],
) if st_c % 2 ==
0 else Apply(
(sc0: integer) => (((1 if st_s - sc0 ==
0 else schroder[st_s - sc0]) if stj + sc0 ==
filled else (1 if st_s - sc0 ==
1 else 0) +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(1 - 1) +
1] +
st_t[(st_s - sc0) *
sw +
2 *
((_n + 1) *
(stj + sc0) +
(stl - 1)) +
(2 - 1) +
1] if stj + sc0 <
filled &&
filled -
(stj + sc0) <=
st_s - sc0 &&
stl +
(st_s - sc0) -
1 <=
_n &&
smin[stj + sc0 +
1] >=
stl &&
smax[stj + sc0 +
1] <=
stl +
(st_s - sc0) -
1 else 0) if sc0 < st_s else 0) if sc0 > 0 else Fold(Function(sum_ss +
st_t[ss * sw +
2 *
((_n + 1) *
stj +
(stl + st_s -
1 +
1 -
ss -
1)) +
(1 - 1) +
1] *
(1 if st_s - ss ==
0 else schroder[st_s - ss]), sum_ss, ss), 0, Range(filled - stj +
1, st_s - 1, 1)),
Apply((sr_init: list<integer>) => Fold((sr: list<integer>, sc) => Apply(
(sr_next: list<integer>) => sr_next,
sr if sr[1] != 0 else Apply((srm: integer) => Apply((srx: integer) => [sc if srx ==
stl + st_s -
1 &&
srm ==
stl + st_s -
1 +
1 -
sc else 0, srm, srx], Max(sr[3], prefix[stj + sc])), Min(sr[2], prefix[stj + sc])),
), sr_init, Range(1, filled - stj, 1)), [0, _n + 1, 0])[1],
)) if stj < filled &&
filled - stj <=
st_s &&
stl + st_s -
1 <=
_n &&
smin[stj + 1] >=
stl &&
smax[stj + 1] <=
stl + st_s -
1 else 0, stq %
(_n + 1) +
1), (stq -
stq %
(_n + 1)) /
(_n + 1)), (st_c -
st_c % 2) /
2),
), st_row, st_c), Map(Function(0, st_z), Range(0, sw - 1, 1)), Range(0, sw - 1, 1)),
), st_t, st_s), Fold(
Function(ReplaceAt(st_row, st_c + 1, 0), st_row, st_c),
Map(Function(0, st_z), Range(0, sw - 1, 1)),
Range(0, sw - 1, 1),
), Range(1, _n + 1 -
1, 1)),
), 2 * filled * (_n + 1)),
Fold(
Function(ReplaceAt(smj_l, smj - 1 +
1, Fold(Function(Max(sme, prefix[smq]), sme, smq), 0, Range(smj, filled, 1))), smj_l, smj),
Map(Function(0, smj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
),
Fold(
Function(ReplaceAt(snj_l, snj - 1 +
1, Fold(Function(Min(sne, prefix[snq]), sne, snq), _n + 1, Range(snj, filled, 1))), snj_l, snj),
Map(Function(0, snj_z), Range(1, Max(filled, 1), 1)),
Range(1, Max(filled, 1), 1),
),
), lr_j), ReplaceAt(lr_base, lr_j, lr_v)) if lr_where[lr_v] > lr_j else 0), lr_r2, lr_v), 0, Range(1, _x[lr_j] - 1, 1)),
Map(
Function(_x[lr_q] if lr_q < lr_j else 0, lr_q),
Range(1, _n, 1),
),
), lr_r, lr_j), 0, Range(1, _n, 1)),
Fold(
Function(ReplaceAt(
lr_at,
_x[lr_p],
lr_p,
), lr_at, lr_p),
Map(
Function(0, lr_y3),
Range(1, _n, 1),
),
Range(1, _n, 1),
),
), _tables)valid(_n, _x)
(!Fold(
Function(sd_ || Fold(Function(sxc_ || Fold(
Function(sxb_ || Fold(
Function(sxa_ ||
_x[sxc] < _x[sxa] &&
_x[sxa] < _x[sd] &&
_x[sd] < _x[sxb] ||
_x[sxb] < _x[sd] &&
_x[sd] < _x[sxa] &&
_x[sxa] < _x[sxc], sxa_, sxa),
False,
Range(
1,
sxb - 1,
1,
),
), sxb_, sxb),
False,
Range(1, sxc - 1, 1),
), sxc_, sxc), False, Range(
1,
sd -
1,
1,
)), sd_, sd),
False,
Range(1, _n, 1),
) if Fold(Function(
(ReplaceAt(lr_d_seen, _x[lr_d_j], 1) if lr_d_seen[_x[lr_d_j]] ==
0 else ReplaceAt(
lr_d_seen,
_n + 1,
1,
)) if 1 <= _x[lr_d_j] &&
_x[lr_d_j] <= _n else ReplaceAt(lr_d_seen, _n + 1, 1),
lr_d_seen,
lr_d_j,
), Map(Function(0, lr_d_z), Range(1, _n + 1, 1)), Range(1, _n, 1))[_n + 1] ==
0 else False) if Length(_x) == _n else Falsetables(_n)
Apply((sq_init: list<integer>) => Fold(
(sq: list<integer>, sk) => Apply(
(sq_next: list<integer>) => sq_next,
Append(
sq,
sq[sk] +
Fold(
Function(sum_si +
sq[si + 1] *
sq[sk - si], sum_si, si),
0,
Range(0, sk - 1, 1),
),
),
),
sq_init,
Range(1, _n - 1, 1),
), [1])Statistics
On Permutation, called as CombinatorialStat(x, "Name").
- AdjacenciesSt000214Positions i with p(i+1) = p(i) - 1.
- AdjacenciesWithZeroAppendedSt000215Positions i with p(i) = p(i+1) + 1, reading p(n+1) = 0.
- AdjacentCyclesSt000153Cycles of the form (a, a+1, ..., a+k), fixed points included.
- AdjacentTranspositionsSt001465Two-cycles (i, i+1).
- AdmissibleInversionsSt000463Pairs i < j with p(i) > p(j) and either p(i-1) < p(i) or some entry between them larger than p(i).
- AdmissibleInversionsPlusDescentsSt000868ShareshianWachsAdmissibleInversions plus the descents.
- AlignmentsSt000222Pairs i, j of arcs of the permutation diagram that align.
- AlternatingRunsSt000483The interior peaks plus the interior valleys.
- AntiexcedancesSt000703Positions with p(i) < i.
- ArithmeticProgressionsOfLengthTwoSt001565Triples i < j < k with p(k) - p(j) = p(j) - p(i).
- AscentBottomSumSt000472The sum of the ascent bottoms: p(i) over the ascents i.
- AscentsSt000245Positions i with p(i) < p(i+1).
- AscentsOfDistanceTwoSt000837Positions i with p(i) < p(i+2).
- AscentTopSumSt000471The sum of the ascent tops: p(i+1) over the ascents i.
- AscentTopsWithSmallerValuesBeforeSt001640Ascents i whose top p(i+1) has every smaller value among p(1), ..., p(i).
- AugmentedDoubleAscentsSt001948Positions i with w(i) < w(i+1) < w(i+2) in the word w = 0 p(1) ... p(n).
- BabsonSteingrimssonStatisticSt000692Babson and Steingrimsson's stat: (13-2) + (21-3) + (32-1) + (21).
- BabsonSteingrimssonStatisticDoublePrimeSt000797Descents plus the occurrences of the vincular patterns 1-32, 3-12 and 3-21.
- BabsonSteingrimssonStatisticPrimeSt000796Descents plus the occurrences of the vincular patterns 13-2, 31-2 and 32-1.
- BigAscentsSt000646Positions i with p(i+1) - p(i) > 1.
- BigAscentsAfterPrependingZeroSt000742Positions of the word 0 p(1) ... p(n) that rise by more than 1, the first entry counted against 0.
- BigDeficienciesSt000710Positions with i - p(i) > 1.
- BigDescentsSt000647Positions i with p(i) - p(i+1) > 1.
- BigExcedancesSt000711Positions with p(i) - i > 1.
- BinStatisticSt001976The sum of the binomial coefficients (i + 1 choose 2) over the descents i.
- BondsSt001405Positions i with |p(i) - p(i+1)| = 1.
- BoxedOccurrencesOf123St001082Occurrences of 123 with no other entry positioned between the first and last and valued between them.
- BoxedOccurrencesOf132St001083Occurrences of 132 with no other entry positioned between the first and last and valued between the least and greatest.
- BruhatLowerCoversSt000957Pairs i < j with p(i) > p(j) and no entry between them valued between p(j) and p(i).
- ComajorIndexSt000833The sum of n - i over the descents i.
- ConjugacyClassSizeSt000690The number of permutations of the same cycle type: n! over the product of the cycle sizes and the factorials of the multiplicities.
- ConvexitySt000226The largest 2 p(i) - p(i-1) - p(i+1) over the interior positions, or 0.
- CrossingsSt000039Pairs i, j with i < j <= p(i) < p(j) or p(i) < p(j) < i < j.
- CycleCountSt000031The number of cycles in the disjoint-cycle decomposition.
- CycleDescentsSt000317Steps down within the cycles, each written from its smallest point.
- CycleMinimumExceedancesDeficienciesSt001269The sum over the cycles of the lesser of the number of exceedances and the number of the other points.
- CyclePeaksSt000994Values i with p^-1(i) < i > p(i).
- CyclesOfLengthAtLeastThreeSt000486Cycles of size at least three.
- CyclesOfLengthAtMostThreeSt000489Cycles of size at most three.
- CyclesOfLengthAtMostTwoSt000488Cycles of size one or two.
- CyclicAlignmentsSt001535Pairs (i, j) with i, j, p(j), p(i) in cyclic order.
- CyclicallyAdjacentTranspositionsSt001466Two-cycles (i, i+1), and the two-cycle (1, n).
- CyclicBondsSt001516Positions i with |p(i) - p(i+1)| = 1, with p(n+1) = p(1).
- CyclicCrossingsSt001537Pairs (i, j) with i, p(j), p(i), j in cyclic order.
- CyclicDescentsSt000619Descents of p read cyclically, counting position n when p(n) > p(1).
- CyclicMaximalJumpSt001245The largest |p(i+1) - p(i)|, with p(n+1) = p(1).
- CyclicMisalignmentsSt001536Pairs (i, j) with i, p(i), j, p(j) in cyclic order.
- CyclicSmallExcedancesSt000241Positions with p(i) = i + 1, read cyclically: the last position counts when p(n) = 1.
- CyclicSmallWeakExcedancesSt000236Positions with p(i) = i or p(i) = i + 1, read cyclically.
- CyclicValleysSt000243Positions lower than both neighbours, reading the word cyclically.
- DecompositionNumberSt000056The k with {p(1), ..., p(k)} = {1, ..., k}: the blocks of p as a direct sum.
- DenertSt000156Sum of the excedance positions, plus the inversions within each of the excedance and non-excedance subwords.
- DepthSt000029Half the total displacement, (1/2) * sum |p(i) - i|.
- DescentBottomSumSt000154The sum of the descent bottoms: p(i+1) over the descents i.
- DescentDifferenceSumSt000030The sum of p(i) - p(i+1) over the descents i.
- DescentsSt000021Positions i with p(i) > p(i+1).
- DescentsAfterZeroingFixedPointsSt000333The descents of the word with every fixed point replaced by 0.
- DescentsAndRecoilsSt001061Indices i < n that are both a descent of p and a recoil.
- DescentsMinusOneUnlessFirstEntryOneSt001960The number of descents of p, less one when p(1) is not 1.
- DescentsOfDistanceThreeSt001520Positions i with p(i) > p(i+3).
- DescentsOfDistanceTwoSt000836Positions i with p(i) > p(i+2).
- DescentsOfTypeTwoSt001737Descents i with p(i) larger than everything before it.
- DescentsOrRecoilsSt000831Indices i < n that are a descent of p or a recoil.
- DescentsPlusRecoilsSt000824Descents plus recoils: the two counts added, not the union of the indices.
- DescentTopSumSt000111The sum of the descent tops: p(i) over the descents i.
- DescentWeightMinusInversionsSt001911The sum of i(n - i) over the descents i, less the inversions.
- DiaconisGrahamDefectSt001906Half of the total displacement less the number of inversions and the reflection length.
- DisorderSt000446Scanning cyclically for 1, then 2, ...: the entries passed that are still larger than the one sought.
- DistinctCycleLengthsHow many distinct cycle sizes occur.
- DistinctDiagonalSumsSt000891The number of distinct sums along the diagonals of the permutation matrix.
- DoubleAscentsSt000365Positions i with p(i) < p(i+1) < p(i+2).
- DoubleDeficienciesSt000732Positions with i > p(i) > p(p(i)).
- DoubleDescentsSt000366Positions i with p(i) > p(i+1) > p(i+2).
- DoubleExcedancesSt000731Positions with i < p(i) < p(p(i)).
- DoubleSuccessionsSt001130Positions i with p(i+1) = p(i) + 1 and p(i+2) = p(i) + 2.
- ElizaldePakRankSt000352The largest k with p(i) > k for all i <= k.
- EvenDescentsSt001115Descents i with i even.
- EvenInversionsSt000538Inversions i < j with j - i even.
- EvenWeakDeficienciesAndOddWeakExcedancesSt001439Positions i with p(i) <= i for even i, and p(i) >= i for odd i.
- ExcedancesSt000155Positions with p(i) > i.
- ExclusiveLeftToRightMaximaSt000996Left-to-right maxima that are not right-to-left minima.
- ExclusiveRightToLeftMinimaSt000374Right-to-left minima that are not left-to-right maxima.
- ExteriorLengthSt001052The longest proper prefix whose relative order is that of the suffix of the same length.
- FinalRisesSt000989The ascents at the end: n - 1 less the last descent position.
- FirstAscentSt000990The smallest ascent position, or n when p is decreasing.
- FirstDescentSt000654The smallest descent position, or n when p is increasing.
- FirstDirectSummandSizeSt000501The smallest k with {p(1), ..., p(k)} = {1, ..., k}.
- FirstEntrySt000054The first entry p(1).
- FixedPointMajorIndexSt000339The sum of the fixed points less the triangular number of their count, plus the major index of the word without its fixed points.
- FixedPointsSt000022Positions with p(i) = i.
- FixedPointsBeforeLargestMovedPointSt001810Fixed points smaller than the largest i with p(i) != i.
- GlobalAscentsSt000234Positions i < n with p(j) < p(k) whenever j <= i < k.
- GlobalDescentsSt000546Positions i < n with p(j) > p(k) whenever j <= i < k.
- GreaterNeighborOfMaximumSt000060The larger of the two entries beside n, an end counting as 0.
- HagSt001671The excedance tops less their positions, plus the inversions among the excedance tops less those among the rest, plus the pairs k < i, over excedances i, with p(k) <= i.
- HalfParityMismatchesSt001801Half the positions i where i and p(i) differ in parity.
- HalfPermanentOfIdentityPlusPermutationSt001661Half the permanent of the identity matrix plus the permutation matrix, which is 2 to the power of the cycles less one.
- HertzsprungOccurrencesOf132St001663Positions i with p(i+1) = p(i) + 2 and p(i+2) = p(i) + 1.
- HookFactorInversionsSt000337The inversions summed over the hook factors t1, ..., tk of p.
- HookFactorizationPrefixLengthSt000338The length of the leading increasing factor p of the hook factorization p t1 ... tk.
- InterpolatingPolynomialDegreeSt001958The degree of the polynomial through the points (i, p(i)): the largest k with a nonzero k-th finite difference.
- InverseMajorIndexSt000305The major index of the inverse: the sum of the values v with v + 1 to the left of v.
- InversionIndexSt000616The sum of the larger entry p(i) over the inversions i < j.
- InversionsSt000018Pairs i < j with p(i) > p(j).
- InversionsBetweenExcedancesAndFixedPointsSt001552Pairs i < j = p(j) < p(i).
- InversionsBetweenExcedancesWithLinkedGreaterSt001550Pairs i < j < p(j) < p(i) with p^-1(j) < j.
- InversionsOfCyclicEmbeddingSt001074The inversions of the cycle (p(1), ..., p(n), n + 1), as a permutation of n + 1.
- InversionsOfDistanceAtMostThreeSt000494Inversions i < j with j - i <= 3.
- InversionsOfDistanceAtMostTwoSt000495Inversions i < j with j - i <= 2.
- InversionsOfSecondEntrySt001557Positions after the second with a smaller entry than p(2).
- InversionsOfThirdEntrySt001556Positions after the third with a smaller entry than p(3).
- InversionsPlusMajorIndexSt001379The number of inversions plus the major index.
- InversionSumSt000055The sum of j - i over the inversions i < j.
- InvisibleDescentsSt001728Positions i with p(i) > p(i+1) > i.
- InvisibleInversionsSt001727Pairs i < j with p(i) > p(j) > i.
- IsolatedDescentsSt000884Descents i such that neither i-1 nor i+1 is a descent.
- LargestCycleLengthSt000485The size of the largest cycle.
- LargestDirectSummandSizeSt000844The size of the largest block of p as a direct sum.
- LargestGreatestCommonDivisorOfPositionAndValueSt001778The largest gcd(i, p(i)).
- LargestRunLengthThe length of the longest increasing run (the catalog's second spelling of LongestRun).
- LargestSearchTreeLeafLabelSt000727The largest label of a leaf of the binary search tree of p, inserting p(1), ..., p(n) in order.
- LargestWeakExcedancePositionSt001497The largest i with p(i) >= i.
- LastDescentSt000653The largest descent position, or 0 when p is increasing.
- LastEntrySt000740The last entry p(n).
- LeftOuterPeaksSt000035Peaks of the word 0 p(1) ... p(n): the interior peaks, plus one when p(1) > p(2).
- LeftToRightMaximaSt000314Positions larger than everything before them.
- LeftToRightMaximaOrRightToLeftMinimaSt001004Positions that are a left-to-right maximum, a right-to-left minimum, or both.
- LeftToRightMaximaPositionSumSt000756The sum of the positions of the left-to-right maxima.
- LeftToRightMaximaXorRightToLeftMinimaSt001005Positions that are a left-to-right maximum or a right-to-left minimum but not both.
- LeftToRightMinimaSt000542Positions smaller than everything before them.
- LexicographicRankSt000020The position of p among the permutations of its size in lexicographic order, counting from 1.
- LoadSt000304The major index of the reverse of the inverse.
- LongestArithmeticProgressionSt001566The length of a longest subsequence whose entries form an arithmetic progression, of either sign.
- LongestCycleLengthSt000485The size of the largest cycle (the catalog's second spelling).
- LongestDecreasingSubsequenceThe length of a longest decreasing subsequence.
- LongestIncreasingSubsequenceSt000062The length of a longest increasing subsequence.
- LongestIncreasingSubsequenceCountSt000883The number of longest increasing subsequences of p.
- LongestKOneTwoPatternSt000451The largest k such that p has an occurrence of k 1 2 ... (k-1): a first entry above an increasing run of later, smaller ones.
- LongestRunThe length of the longest run of consecutive increases.
- LongestSuccessionRunSt001652The length of the longest factor p(k), ..., p(l) with p(i+1) = p(i) + 1.
- LowerMiddleEntrySt001807The entry p(floor((n+1)/2)).
- MadSt000795Foata and Zeilberger's mad: 2 (2-31) + (31-2) + (21).
- MajorIndexSt000004The SUM of the descent positions — not their count.
- MajorIndexAfterZeroingFixedPointsSt000334The major index of the word with every fixed point replaced by 0.
- MajorIndexMinusExcedancesSt000462The major index less the number of positions with p(i) > i.
- MajorIndexMinusInversionsSt001377The major index less the number of inversions.
- MajorIndexPlusInverseMajorIndexSt000825The major index plus the major index of the inverse.
- MakSt000794Foata and Zeilberger's mak: (2-31) + (32-1) + (1-32) + (21).
- MaklSt000798Foata and Zeilberger's makl: (1-32) + (31-2) + (32-1) + (21).
- MaximalCycleDifferenceSt000209The largest difference between two elements of one cycle.
- MaximalDiagonalOccupancySt000887The most entries on one diagonal of the permutation matrix: the largest number of i sharing a p(i) - i.
- MaximalDisplacementSt000956The largest |p(i) - i|.
- MaximalExcedanceSt000141The largest p(i) - i.
- MaximalJumpSt001246The largest |p(i+1) - p(i)|.
- MaximalModularDisplacementSt001569The largest cyclic distance between p(i) and i, taken mod n.
- MaximalRiseSizeSt000651The largest p(i+1) - p(i), or 0 when p has no rise.
- MaximalSuccessiveDifferenceSt000652The largest p(i+1) - p(i), negative for a decreasing permutation.
- MaximumOfDescentsAndInverseDescentsSt001489The larger of the number of descents and the number of inverse descents.
- MidPointsOfOccurrencesOf123St000372Positions that are the middle of a 123 occurrence.
- MidPointsOfOccurrencesOf321St000371Positions that are the middle of a 321 occurrence: neither a left-to-right maximum nor a right-to-left minimum.
- MinimalCycleDifferenceSt000210The smallest, over the cycles, of the largest difference between two elements of a cycle.
- MinimalInversionsEitherDirectionSt001511The smaller of the number of inversions and the number of non-inversions.
- MinimalJumpSt001162The smallest |p(i+1) - p(i)|.
- MinorIndexThe sum of the ascent positions.
- NeighboringNumberSt001344The smallest |p(i+1) - p(i)|, the wrap-around gap |p(1) - p(n)| included.
- NestedExcedancesSt001513Pairs i < j with i < j < p(j) < p(i).
- NestingsSt000223Pairs i, j with j < i < p(i) < p(j) or p(j) < p(i) <= i < j.
- NonAttackingNeighborsSt001388Positions i with |p(i) - p(i+1)| > 1.
- NonCyclicSmallExcedancesSt000235Positions that are not cyclic small excedances.
- NonCyclicSmallWeakExcedancesSt000242Positions that are not cyclic small weak excedances.
- NonFixedPointsSt000673Positions i with p(i) != i.
- NonInitialLeftToRightMinimaSt000541Positions i >= 2 with p(i) smaller than everything before it.
- NonInversionsSt000246Pairs i < j with p(i) < p(j).
- NonInversionSumSt000341The sum of j - i over the non-inversions i < j.
- NonLeftToRightMaximaSt000316Positions smaller than something before them.
- NonNegativeWalkStepsSt001332Steps of the walk (up at an ascent, down at a descent) that begin and end at height at least 0.
- NonOverlappingDescentsSt001928Descents taken greedily left to right, none starting where the last one ended.
- NonRecordsSt001715Positions that are none of a left-to-right maximum or minimum, or a right-to-left maximum or minimum.
- NonSmallExcedancesSt000240Positions with p(i) != i + 1.
- NonSmallWeakExcedancesSt000238Positions with p(i) not in {i, i + 1}.
- NontrivialCyclesSt000162Cycles of size at least two: the cycles less the fixed points.
- NonWeakExcedanceMidPointsOfOccurrencesOf321St000375Positions i with p(i) < i that are the middle of a 321 occurrence.
- NormalizedLeafLabelSumSt000726The sum of the leaf labels of the increasing binary tree of p, less n.
- NormalizedSumOfDistancesToGreaterElementSt000624The same sum, each gap one less: the entries strictly between a position and its nearest greater entry.
- OccurrencesOf123St000002Triples i < j < k with p(i) < p(j) < p(k).
- OccurrencesOf123Or132St000423Triples ordered as 123 or as 132.
- OccurrencesOf123Or213St000428Triples ordered as 123 or as 213.
- OccurrencesOf123Or231St000427Triples ordered as 123 or as 231.
- OccurrencesOf123Or312St000430Triples ordered as 123 or as 312.
- OccurrencesOf123Or321St000429Triples ordered as 123 or as 321.
- OccurrencesOf12Dash3St000357Triples i, i+1, k with k > i+1 ordered as 123 (12-3).
- OccurrencesOf132St000220Triples i < j < k with p(i) < p(k) < p(j).
- OccurrencesOf1324St000405Quadruples i < j < k < l ordered as 1324.
- OccurrencesOf132Or213St000425Triples ordered as 132 or as 213.
- OccurrencesOf132Or213Or321St000457Triples ordered as 132, 213 or 321.
- OccurrencesOf132Or231St000424Triples ordered as 132 or as 231.
- OccurrencesOf132Or312St000426Triples ordered as 132 or as 312.
- OccurrencesOf132Or321St000433Triples ordered as 132 or as 321.
- OccurrencesOf13Dash2St000356Triples i, i+1, k with k > i+1 ordered as 132 (13-2).
- OccurrencesOf1432St001847Quadruples i < j < k < l ordered as 1432.
- OccurrencesOf14Dash2Dash3Or14Dash3Dash2St000709Adjacent ascents p(i) < p(i+1) with two later entries between them, in either order, counted in pairs.
- OccurrencesOf213St000218Triples i < j < k with p(j) < p(i) < p(k).
- OccurrencesOf213Or231St000435Triples ordered as 213 or as 231.
- OccurrencesOf213Or312St000434Triples ordered as 213 or as 312.
- OccurrencesOf213Or321St000431Triples ordered as 213 or as 321.
- OccurrencesOf2143St000407Quadruples i < j < k < l ordered as 2143.
- OccurrencesOf2143Or4213St000751Quadruples ordered as 2143 or as 4213.
- OccurrencesOf21Dash3St000355Triples i, i+1, k with k > i+1 ordered as 213 (21-3).
- OccurrencesOf231St000219Triples i < j < k with p(k) < p(i) < p(j).
- OccurrencesOf231Or312St000432Triples ordered as 231 or as 312.
- OccurrencesOf231Or321St000436Triples ordered as 231 or as 321.
- OccurrencesOf23Dash1St000359Triples i, i+1, k with k > i+1 ordered as 231 (23-1).
- OccurrencesOf2413St001705Quadruples i < j < k < l ordered as 2413.
- OccurrencesOf312St000217Triples i < j < k with p(j) < p(k) < p(i).
- OccurrencesOf312Or321St000437Triples ordered as 312 or as 321.
- OccurrencesOf31Dash2St000358Triples i, i+1, k with k > i+1 ordered as 312 (31-2).
- OccurrencesOf321St000119Triples i < j < k with p(i) > p(j) > p(k).
- OccurrencesOf321Or3412St001411Triples ordered as 321, plus quadruples ordered as 3412.
- OccurrencesOf3241St000406Quadruples i < j < k < l ordered as 3241.
- OccurrencesOf3241Or4231St000404Quadruples ordered as 3241 or as 4231.
- OccurrencesOf32Dash1St000360Triples i, i+1, k with k > i+1 ordered as 321 (32-1).
- OccurrencesOf3412Or4231St000622Quadruples ordered as 3412 or as 4231.
- OccurrencesOf4132Or4231St000440Quadruples ordered as 4132 or as 4231.
- OccurrencesOf41352Or42351Or51342Or52341St001059Quintuples ordered as 41352, 42351, 51342 or 52341.
- OccurrencesOf4213St000750Quadruples i < j < k < l ordered as 4213.
- OccurrencesOf4231St000408Quadruples i < j < k < l ordered as 4231.
- OccurrencesOf52341St000623Quintuples i < j < k < l < m ordered as 52341.
- OccurrencesOfConsecutive132St001086Triples i, i+1, i+2 ordered as 132 (consecutive 132).
- OccurrencesOfInitial123St000804Triples 1 < j < k ordered as 123 (|123).
- OccurrencesOfInitial12Dash3St001084Triples 1, 2, k ordered as 123 (|12-3).
- OccurrencesOfInitial132St000803Triples 1 < j < k ordered as 132 (|132).
- OccurrencesOfInitial1Dash23St001087Triples 1, j, j+1 ordered as 123 (|1-23).
- OccurrencesOfInitial213St000799Triples 1 < j < k ordered as 213 (|213).
- OccurrencesOfInitial231St000800Triples 1 < j < k ordered as 231 (|231).
- OccurrencesOfInitial2Dash13St001085Triples 1, j, j+1 ordered as 213 (|2-13).
- OccurrencesOfInitial312St000801Triples 1 < j < k ordered as 312 (|312).
- OccurrencesOfInitial321St000802Triples 1 < j < k ordered as 321 (|321).
- OddDescentsSt001114Descents i with i odd.
- OddInversionsSt000539Inversions i < j with j - i odd.
- OneBoxPatternsSt000064Positions i with a neighbouring entry, left or right, differing from p(i) by exactly 1.
- OuterPeaksSt000092Peaks of the word 0 p(1) ... p(n) 0: the interior peaks, plus one for each end that is a peak.
- OverlapSetSizeSt001096Shifts i < n for which the first n - i entries and the last n - i entries are in the same relative order.
- PeaksSt000023Interior positions with p(i-1) < p(i) > p(i+1).
- PermutationBounceSt000133The sum of n - b over the bounce points b: the position of 1 in p, then the greatest position among the entries up to one past the last.
- PermutationBreadthSt000842The least Manhattan distance |i - j| + |p(i) - p(j)| between two points of the permutation matrix.
- PermutationCosineSt000342The sum of i p(i).
- PermutationGenusSt001394The genus g with n + 1 - 2g the cycles of p plus the cycles of p^-1 composed with the long cycle.
- PermutationOrderSt000058The order of p in the symmetric group — the lcm of its cycle lengths.
- PermutationSupportSt000673The points p moves, in increasing order.
- PermutationTreeHeightSt000308The height of the rooted tree from inserting the entries one by one, the most entries on the stack of ancestors.
- PinnacleSumSt001519The sum of the peak values: p(i) over the interior peaks i.
- PositionsOfLetterOneIn123St001682Positions that start an occurrence of 123.
- PositionsOfLetterOneIn132St001685Positions that start an occurrence of 132.
- PositionsOfLetterThreeIn132St001683Positions that are the middle of an occurrence of 132.
- PositionsOfLetterTwoIn213St001687Positions that start an occurrence of 213.
- PrefixSumProductSt001482The product of the prefix sums p(1) + ... + p(i) for i < n.
- PrimeColumnSumsSt001285Positions i with i + p(i) prime.
- PrimeProductsMinusOneSt001287Positions i with i * p(i) - 1 prime.
- PrimeProductsPlusOneSt001288Positions i with i * p(i) + 1 prime.
- ProperBlocksSt001160Windows p(i), ..., p(j) of two or more entries whose values are consecutive integers, the whole word excepted.
- PureExcedancesSt001665Excedances i < p(i) with no j < i where i <= p(j) < p(i).
- RaftsSt000665Maximal runs of consecutive successions p(i+1) = p(i) + 1.
- RecoilsSt000354Values i with i + 1 to the left of i: the descents of the inverse.
- RecursiveEndMaximumCountSt000461FindStat's rix: the number of times, peeling the word, the maximum of what is left is its last entry.
- RecursiveStartMinimumCountSt000873FindStat's aix: the number of times, peeling the word, the minimum of what is left is its first entry.
- ReducedWordSupportSt000019The simple reflections in a reduced word: the i < n with some entry of p(1), ..., p(i) larger than i.
- ReflectionLengthSt000216n minus the number of cycles — the minimum number of transpositions.
- RepeatedLehmerCodeEntriesSt001298The Lehmer code's length less its number of distinct entries.
- RestrictedNonInversionsBetweenExcedancesSt001549Pairs i < j < p(i) < p(j).
- RestrictedNonInversionsBetweenExcedancesWithLinkedRightmostSt001551Pairs i < j < p(i) < p(j) with p^-1(j) < j.
- RightFloatsSt000663Large ascents p(i+1) > p(i) + 1 beside no raft.
- RightOuterPeaksSt000834Peaks of the word p(1) ... p(n) 0: the interior peaks, plus one when p(n) > p(n-1).
- RightRopesSt000664Large ascents right after a raft.
- RightTethersSt000666Large ascents between two rafts.
- RightToLeftMaximaSt000007Positions larger than everything after them.
- RightToLeftMinimaSt000991Positions smaller than everything after them.
- RunsSt000325St000470Maximal increasing runs — one more than the number of descents.
- ScaledReciprocalPositionValueSumSt001293The sum of 1/(i + p(i)) times the least common multiple of 1 .. 2n, an integer.
- SeparatorsSt001402The values v that are a vertical separator of p, or whose image under p^-1 is a vertical separator of p^-1.
- ShareshianWachsAdmissibleInversionsSt000866Pairs i < j with p(i) > p(j) and either p(j) < p(j+1) or some entry between them smaller than p(j).
- ShiftedMajorIndexSt000961The sum of the positions i with p(i) - p(i+1) >= 2.
- ShortestCycleLengthSt000487The size of the smallest cycle.
- SignSt000037The sign of p: +1 when the inversion count is even, -1 when odd.
- SimsunDoubleDescentsSt000367Double descents in the restrictions of p to the values 1..k, over all k, counted with multiplicity.
- SmallerChildPathLeafLabelSt000724The label of the leaf reached from the root of the increasing binary tree of p by always following the child with the smaller label.
- SmallestFixedPointSt001468The smallest i with p(i) = i, or n + 1 when there is none.
- SmallestLeafLabelSt000725The smallest label of a leaf of the increasing binary tree of p: the least peak, an end counting as a peak.
- SmallExcedancesSt000237Positions with p(i) = i + 1.
- SmallWeakExcedancesSt000239Positions with p(i) = i or p(i) = i + 1.
- SortingIndexSt000224The total distance the entries move in selection sort.
- StackSortable1 when p avoids the pattern 231, 0 otherwise — exactly the stack-sortable permutations.
- StaircaseSizeOfCodeSt000662The largest k with a subsequence of the Lehmer code whose j-th entry from the right is at least j.
- StandardizedBiAlternatingInversionNumberSt000677Half of floor(n/2)^2 plus the signed inversions, each pair i < j weighted by (-1)^(i+j).
- StretchingPairsSt000516Pairs i < j with p(i) < i < j < p(j).
- StrongFixedPointsSt000221Positions that are both a left-to-right maximum and a right-to-left minimum.
- SuccessionsSt000441Positions i with p(i+1) = p(i) + 1.
- SumOfDistancesToGreaterElementSt000625Over each position, the gap to the nearest greater entry, the ends counting as greater.
- SymmetryClassSizeSt000401The permutations reachable from p by inverse, reverse and complement: 8 over the symmetries that fix p.
- TailPairsOfOccurrencesOf321St000123Pairs j < k with p(j) > p(k) and some entry before j above p(j), the positions of the 2 and the 1 of the occurrences of 321.
- ThreeCycleCountCycles of size exactly three.
- ThreeExcedancesSt000649Positions with p(i) = i + 3.
- ThreeRisesSt000650Positions i with p(i+1) = p(i) + 3.
- ThreeShiftedMajorIndexSt000962The sum of the positions i with p(i) - p(i+1) > 3.
- TierSt000779Positions a with a larger entry, then the value p(a) - 1, to its right.
- TotalDisplacementSt000830The sum of |p(i) - i|.
- TotalSquaredDisplacementSt000828The sum of (p(i) - i)^2.
- TwoCycleCountCycles of size exactly two.
- TwoExcedancesSt000648Positions with p(i) = i + 2.
- TwoRisesSt000534Positions i with p(i+1) = p(i) + 2.
- TwoShiftedMajorIndexSt000963The sum of the positions i with p(i) - p(i+1) > 2.
- UlamDistanceSt000829The entries to remove to leave an increasing sequence: n less the length of a longest increasing subsequence.
- UpDownRunsSt000638Maximal monotone runs, with p(1) counted alone when it is a descent.
- UpperMiddleEntrySt001806The entry p(floor(n/2) + 1).
- ValleysSt000353Interior positions with p(i-1) > p(i) < p(i+1).
- ValleysIncludingBoundarySt000099Positions lower than both neighbours, a larger entry standing off each end.
- VerticalSeparatorsSt001403Interior positions i with |p(i-1) - p(i+1)| = 1.
- VeryBigAscentsSt000871Positions i with p(i+1) - p(i) > 2.
- VeryBigDescentsSt000872Positions i with p(i) - p(i+1) > 2.
- VisibleDescentsSt001729Positions i with p(i+1) <= min(i, p(i)).
- VisibleInversionsSt001726Pairs i < j with p(j) <= min(i, p(i)).
- WeakAntiexcedancesSt000702Positions with p(i) <= i.
- WeakExcedanceMidPointsOfOccurrencesOf321St000373Positions i with p(i) >= i that are the middle of a 321 occurrence.
- WeakExcedancesSt000213Positions with p(i) >= i.
Maps
Into and out of Permutation, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From Permutation
- BinarySearchTreePermutation → BinaryTreesurjectionSurjectionGraded mapMp00072The tree built by inserting σ(1), σ(2), ... into an empty binary search tree.
- BinarySearchTreeParentArrayPermutation → BinaryTreeParentArrayThe binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.
- CactusEvacuationPermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00126The permutation with the same insertion tableau and the evacuation of the recording tableau.
- ComplementPermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00069Each entry replaced by n + 1 minus itself.
- ConjugacyClassRepresentativePermutation → PermutationidempotentThe canonical permutation with the same cycle type.
- ConjugateAfterCycleTypePermutation → IntegerPartitionThe conjugate partition of the cycle type.
- ConnectivityWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00114Letter i is 1 when the first i entries are all smaller than the rest: the connectivity set as a binary word.
- CycleAsOneLineNotationPermutation → PermutationGraded mapMp00090The cycles, each written from its least point and in order of those points, read as one word.
- CycleDecompositionPermutation → CycleDecompositioninverseA permutation in cycle notation, fixed points kept: each cycle from its least point, cycles in order of those points.
- CyclePartitionPermutation → SetPartitionsurjectionSurjectionGraded mapMp00151The orbits, as a set partition of the positions.
- CycleTypePermutation → IntegerPartitionsurjectionSurjectionGraded mapMp00108The multiset of cycle lengths, as a partition.
- CyclicShiftPermutation → PermutationinverseBijectionGraded mapMp00279Rotate the word one place to the left.
- DescentBottomWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00131Letter v is 1 when value v is a descent bottom: some larger value immediately precedes it.
- DescentCompositionPermutation → IntegerCompositionsurjectionSurjectionGraded mapMp00071The composition of n cut at the descent positions.
- DescentSetPermutation → FinsetThe positions where the word falls.
- DescentTopWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00130Letter v - 1 is 1 when value v is a descent top: some smaller value immediately follows it.
- DescentWordPermutation → BinaryWordsurjectionSurjectionGraded mapMp00109Letter i is 1 when the word falls between positions i and i + 1: the descent set as a binary word.
- FoataPermutation → PermutationbijectionBijectionGraded mapMp00087Foata's fundamental bijection: cycles rotated to their max, ordered by increasing max, parentheses erased.
- FoataInversionsToMajorPermutation → PermutationbijectioninverseBijectionGraded mapMp00175The inverse of Foata's major-to-inversions bijection: peel off the last letter, rotate the blocks of the rest back.
- FoataMajorToInversionsPermutation → PermutationbijectioninverseBijectionGraded mapMp00067Foata's bijection: each letter is put on the end of the image so far, which is cut into blocks, and every block is rotated one place right.
- FromPermutationPermutation → IncreasingBinaryTreeThe increasing binary tree built by minimum-splitting recursion: the position of the smallest value roots the tree, everything before it recurses to the left, everything after it to the right.
- InversePermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00066The inverse permutation: position of each value.
- InverseAfterComplementAfterReversePermutation → PermutationReverse, then complement, then invert.
- InverseCyclicShiftPermutation → PermutationinverseRotate the word one place to the right.
- InverseFoataPermutation → PermutationbijectioninverseBijectionGraded mapMp00086The permutation whose cycles are the stretches of the word between successive left-to-right maxima, each read as a cycle.
- InverseKrewerasComplementPermutation → PermutationbijectioninverseBijectionGraded mapMp00089cπ⁻¹ with the long cycle c = (1 2 ... n), FindStat's order: position i holds π⁻¹(c(i)).
- InverseToricPromotionPermutation → PermutationbijectioninverseBijectionGraded mapMp00309The same swaps as ToricPromotion in the opposite order: n and 1, then n - 1 and n, down to 1 and 2.
- KnuthClassRepresentativePermutation → PermutationidempotentThe row reading word of σ's RSK insertion tableau — the canonical word of its Knuth (plactic) class.
- KrewerasComplementPermutation → PermutationbijectionBijectionGraded mapMp00088π⁻¹c with the long cycle c = (1 2 ... n), FindStat's order: position i holds c(π⁻¹(i)).
- LeftToRightMaximaDyckPathPermutation → DyckPathsurjectionSurjectionGraded mapMp00127The Dyck path whose rises climb to each left-to-right maximum and whose falls run to the next one.
- LehmerCodeRotationPermutation → PermutationbijectionBijectionGraded mapMp00149The permutation whose Lehmer code is this one's with every entry one larger, cyclically.
- LehmerCodeToMajorCodePermutation → PermutationbijectioninverseBijectionGraded mapMp00062The permutation whose major code is this permutation's Lehmer code.
- LongCycleConjugationPermutation → PermutationbijectionBijectionGraded mapMp00265Conjugation by the long cycle (1 2 ... n): each cycle's entries shifted up by one, cyclically.
- MajorCodeToLehmerCodePermutation → PermutationbijectioninverseBijectionGraded mapMp00073The permutation whose Lehmer code is this permutation's major code.
- PeakSetPermutation → FinsetThe interior positions that rise then fall.
- PermutahedronVertexPermutation → FinsetThe vertex (σ(1), …, σ(n)), or its Loday point, is an ordered tuple of coordinates, while
finsetis an unordered set of positions (the carrier DescentSet and PeakSet use). Reordering the coordinates gives a different vertex but the same finset, so the map would not be injective. Afinset-valued PermutahedronVertex is a type mismatch, not a gap to close. - ReversePermutation → PermutationinvolutionBijectionGraded mapInvolutionMp00064The word read backwards.
- ReverseComplementPermutation → PermutationinvolutionReverse, then complement.
- RskPermutation → StandardTableauPairThe RSK correspondence: the insertion and recording tableaux, as a pair.
- RskInsertionPermutation → StandardTableausurjectionSurjectionGraded mapMp00059The insertion tableau of the RSK correspondence.
- RskRecordingPermutation → StandardTableausurjectionSurjectionGraded mapMp00070The recording tableau of the RSK correspondence, as its rows.
- RskShapePermutation → IntegerPartitionsurjectionSurjectionGraded mapMp00060The common shape of the RSK tableaux: the row lengths, as a partition of n.
- RunSortPermutation → PermutationidempotentIdempotentGraded mapMp00223The permutation with its increasing runs sorted lexicographically.
- SignedPermutationPermutation → SignedPermutationInjectionGraded mapMp00170A permutation as the signed permutation with every sign positive.
- SimionSchmidtPermutation → PermutationidempotentIdempotentGraded mapMp00068The left-to-right minima stay in place and the other positions take the remaining values, largest first: a 123-avoiding permutation.
- SubexcedantSeqPermutation → SubexcedantSeqinverseEntry i counts the earlier entries larger than p(i): the permutation's inversion sequence.
- ToLehmerCodePermutation → PermutationInversionEntry i counts the later entries smaller than p(i).
- ToricPromotionPermutation → PermutationbijectioninverseBijectionGraded mapMp00310Toric promotion of the path graph: swap the values 1 and 2, then 2 and 3, and so on up to n and 1, each swap skipped when the two values sit next to each other.
- WeakExceedancePartitionPermutation → SetPartitionSurjectionGraded mapMp00240The coarsest set partition containing every arc from i to π(i) with i ≤ π(i).
To Permutation
- Avoiding132PermutationDyckPath → PermutationInjectionGraded mapMp00025The 132-avoiding permutation of Krattenthaler's bijection, built from the path's area sequence read from the end.
- Avoiding312PermutationDyckPath → PermutationInjectionGraded mapMp00031The 312-avoiding permutation of Bandlow and Killpatrick: from the identity, each area-sequence entry swaps neighbouring positions that many times.
- Avoiding321PermutationDyckPath → PermutationInjectionGraded mapMp00024The 321-avoiding permutation whose RSK pair is the pair of two-row tableaux read off the first and last halves of the path.
- BilleyJockuschStanleyPermutationDyckPath → PermutationInjectionGraded mapMp00129The 321-avoiding permutation with entry (ups through a valley) + 1 at the position of its downs through that valley: the Billey-Jockusch-Stanley bijection.
- BlockConcatenationSetComposition → PermutationsurjectionSurjectionGraded mapMp00286The permutation that lists the blocks in order, each sorted increasingly.
- CarPermutationParkingFunction → PermutationSurjectionGraded mapMp00053Spot j holds the car that parks there, each car taking the first free spot at or after its preference.
- 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.
- KrattenthalerPermutationDyckPath → PermutationInjectionGraded mapMp00119The 321-avoiding permutation whose left-to-right maxima are the path's peaks: Krattenthaler's bijection.
- LabelingPermutationParkingFunction → PermutationSurjectionGraded mapMp00055The labeling of the parking function's support Dyck path: the positions of the entries, smallest entry first and equal entries left to right.
- NoncrossingPermutationDyckPath → PermutationInjectionGraded mapMp00023The noncrossing permutation Stump's bijection gives the path: the cycles of its touch points, peeled off round by round.
- PermutationCycleDecomposition → PermutationinverseThe permutation a cycle decomposition describes.
- PermutationSubexcedantSeq → PermutationinverseThe permutation a subexcedant sequence is the inversion sequence of.
- ReadingWordStandardTableau → PermutationInjectionGraded mapMp00081The rows read left to right, from the bottom row up, as a permutation.
- RingelDyckPath → PermutationInjectionGraded mapMp00201The Ringel permutation of the Nakayama algebra whose Kupisch series the path gives, one size up.
- StandardizationSignedPermutation → PermutationsurjectionSurjectionGraded mapMp00245The permutation of the same relative order, taking 1 < … < n < −n < … < −1.
- StandardPermutationBinaryWord → PermutationGraded mapMp00336The permutation ranking the letters of the word, equal letters from left to right.
- ToPermutationStandardTableauPair → PermutationinverseThe permutation an RSK pair comes from: inverse RSK.
- UnderlyingPermutationSignedPermutation → PermutationsurjectionSurjectionGraded mapMp00163The permutation left when the signs are forgotten.
32 more in FindStat, not implemented here
- Mp00002AlternatingSignMatrix → PermutationSurjectionGraded mapto left key permutation
- Mp00014BinaryTree → PermutationInjectionGraded mapto 132-avoiding permutation
- Mp00017BinaryTree → PermutationInjectionGraded mapto 312-avoiding permutation
- Mp00058PerfectMatching → PermutationInjectionGraded mapto permutation
- Mp00061Permutation → BinaryTreeSurjectionGraded mapto increasing tree
- Mp00063Permutation → AlternatingSignMatrixInjectionGraded mapto alternating sign matrix
- Mp00065Permutation → PosetsGraded mappermutation poset
- Mp00075SemistandardTableau → PermutationGraded mapreading word permutation
- Mp00159Permutation → PermutationGraded mapDemazure product with inverse
- Mp00160Permutation → LabeledGraphGraded mapgraph of inversions
- Mp00204Permutation → IntegerPartitionSurjectionGraded mapLLPS
- Mp00208Permutation → Latticeslattice of intervals
- Mp00209Permutation → Posetspattern poset
- Mp00235Permutation → PermutationBijectionGraded mapdescent views to invisible inversion bottoms
- Mp00236Permutation → PermutationBijectionGraded mapClarke-Steingrimsson-Zeng inverse
- Mp00237Permutation → PermutationBijectionGraded mapdescent views to invisible inversion bottoms
- Mp00238Permutation → PermutationBijectionGraded mapClarke-Steingrimsson-Zeng
- Mp00239Permutation → PermutationBijectionGraded mapInvolutionCorteel
- Mp00241Permutation → PermutationBijectionGraded mapInvolutioninvert Laguerre heap
- Mp00248Permutation → IntegerCompositionGraded mapDEX composition
- Mp00252Permutation → PermutationSurjectionrestriction
- Mp00253DecoratedPermutation → PermutationSurjectionGraded mappermutation
- Mp00254Permutation → PermutationIdempotentInverse fireworks map
- Mp00255DecoratedPermutation → PermutationGraded maplower permutation
- Mp00256DecoratedPermutation → PermutationGraded mapupper permutation
- Mp00257Permutation → PermutationBijectionGraded mapInvolutionAlexandersson Kebede
- Mp00277Permutation → PermutationGraded mapcatalanization
- Mp00283PerfectMatching → PermutationInjectionGraded mapnon-nesting-exceedence permutation
- Mp00305Permutation → ParkingFunctionInjectionGraded mapparking function
- Mp00325Permutation → PermutationBijectionGraded mapones to leading
- Mp00326Permutation → PermutationBijectionGraded mapweak order rowmotion
- Mp00329Permutation → PermutationBijectionTanimoto
Enumeration
Examples
1 more kept as data, checked against the oraclesAbout
| Examples | 2 |
|---|---|
| Crosswalk | OEIS |
See also: SimplePermutations, Count, At