A356116 -id:A356116 - cp's OEIS frontend

A355776 Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.

0, 0, 0, 0, 0, 1, 0, 0, 3, 2, 5, 0, 0, 6, 10, 22, 24, 16, 0, 0, 10, 20, 12, 61, 162, 29, 102, 150, 42, 0, 0, 15, 35, 49, 135, 432, 246, 273, 391, 1389, 461, 388, 698, 99, 0, 0, 21, 56, 90, 52, 260, 982, 1288, 740, 827, 1150, 4974, 2745, 5778, 482, 2057, 8924, 4148, 1333, 2764, 219, 0

Offset: 0

Peter Luschny, Jul 27 2022

We say a list L is weakly increasing if x <= y, and weakly decreasing, if x >= y, for all x, y in L if index(x) < index(y). We say a list L is nonmonotonic if it is not weakly increasing and not weakly decreasing.

The ordering of the partitions is defined in A334439. See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'.

			Table T(n, k) starts:
[0]  0;
[1]  0;
[2]  0,  0;
[3]  0,  1,  0;
[4]  0, [3,  2],   5,  0;
[5]  0, [6, 10], [22, 24],   16,  0;
[6]  0, [10, 20, 12], [61,  162, 29], [102, 150],   42,   0;
[7]  0, [15, 35, 49], [135, 432, 246, 273], [391, 1389, 461], [388, 698], 99, 0;
Summing the bracketed terms reduces the triangle to A356116.
.
The permutations whose Lehmer code is nonmonotonic, in the case n = 4, k = 1 are: 1243, 1324, 1423, which map to the partition [3, 1] and 1342, 2143, which map to the partition [2, 2]. Thus A356116(4, 1) = 3 + 2 = 5.
.
The cardinality of the preimage of the partitions, i.e. the number of permutations whose Lehmer code is nonmonotonic, are the terms of the sequence. Here row 6:
[6] => 0
[5, 1] => 10
[4, 2] => 20
[3, 3] => 12
[4, 1, 1] => 61
[3, 2, 1] => 162
[2, 2, 2] => 29
[3, 1, 1, 1] => 102
[2, 2, 1, 1] => 150
[2, 1, 1, 1, 1] => 42
[1, 1, 1, 1, 1, 1] => 0

Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Cf. A000217 (column 1), A002662 (subdiagonal), A000041 (row lengths), A056986 (row sums), A356116 (reduced triangle), A355777 (Euler-Lehmer).

import collections
def perm_lehmer_nonmono_stats(n):
    res = collections.defaultdict(int)
    for p in Permutations(n):
        l = p.to_lehmer_code()
        if all(x >= y for x, y in zip(l, l[1:])): continue
        c = [l.count(i) for i in range(len(p)) if i in l]
        res[Partition(reversed(sorted(c)))] += 1
    return sorted(res.items(), key=lambda x: len(x[0]))
@cached_function
def A355776_row(n):
    if n < 2: return [0]
    S = perm_lehmer_nonmono_stats(n)
    return [0] + [s[1] for s in S] + [0]
def A355776(n, k): return A355776_row(n)[k] if n > 0 else 0
for n in range(0, 8): print(A355776_row(n))

A355777 Partition triangle read by rows. A statistic of permutations given by their Lehmer code refining Euler's triangle A173018.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 7, 4, 11, 1, 1, 11, 15, 32, 34, 26, 1, 1, 16, 26, 15, 76, 192, 34, 122, 180, 57, 1, 1, 22, 42, 56, 156, 474, 267, 294, 426, 1494, 496, 423, 768, 120, 1, 1, 29, 64, 98, 56, 288, 1038, 1344, 768, 855, 1206, 5142, 2829, 5946, 496, 2127, 9204, 4288, 1389, 2904, 247, 1

Offset: 0

Peter Luschny, Jul 16 2022

An exposition of the theory is in Hivert et al. (see the table p. 4), test data can be found in the Statistics Database at St000275.
The ordering of the partitions is defined in A080577. See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'.
An alternative representation is Tom Copeland's A145271 which has a faster Maple program. The Sage program below, on the other hand, explicitly describes the combinatorial construction and shows how the permutations are bundled into partitions via the Lehmer code.

			The table T(n, k) begins:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 4,            1;
[4] 1, [7, 4],       11,                   1;
[5] 1, [11, 15],     [32, 34],             26,               1;
[6] 1, [16, 26, 15], [76, 192, 34],        [122, 180],       57,         1;
[7] 1, [22, 42, 56], [156, 474, 267, 294], [426, 1494, 496], [423, 768], 120, 1;
Summing the bracketed terms reduces the triangle to Euler's triangle A173018.
.
The Lehmer mapping of the permutations to the partitions, case n = 4, k = 1:
   1243, 1324, 1423, 2134, 2341, 3124, 4123 map to the partition [3, 1] and
   1342, 2143, 2314, 3412 map to the partition [2, 2]. Thus A173018(4, 1) = 7 + 4 = 11.
.
The cardinality of the preimage of the partitions, i.e. the number of permutations which map to the same partition, are the terms of the sequence. Here row 6:
[6] => 1
[5, 1] => 16
[4, 2] => 26
[3, 3] => 15
[4, 1, 1] => 76
[3, 2, 1] => 192
[2, 2, 2] => 34
[3, 1, 1, 1] => 122
[2, 2, 1, 1] => 180
[2, 1, 1, 1, 1] => 57
[1, 1, 1, 1, 1, 1] => 1

Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker and Amanda Welch, Homomesies on permutations -- an analysis of maps and statistics in the FindStat database, arXiv:2206.13409 [math.CO], 2022. (Def. 4.20 and Prop. 4.22.)
Florent Hivert, Jean-Christophe Novelli and Jean-Yves Thibon, Multivariate generalizations of the Foata-Schützenberger equidistribution, arXiv:math/0605060 [math.CO], 2006.
Florent Hivert, Number of permutations whose sorted list of non zero multiplicities of the Lehmer code is the given partition, Statistics Database St000275, 2015.
Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.
Wikipedia, Lehmer code.

Cf. A000295 (subdiagonal), A000124 (column 2), A000142 (row sums), A000041 (row lengths).

Cf. A179454 (permutation trees), A123125 and A173018 (Eulerian numbers), A145271 (variant).

import collections
@cached_function
def eulerian_stat(n):
    res = collections.defaultdict(int)
    for p in Permutations(n):
        c = p.to_lehmer_code()
        l = [c.count(i) for i in range(len(p)) if i in c]
        res[Partition(reversed(sorted(l)))] += 1
    return sorted(res.items(), key=lambda x: len(x[0]))
@cached_function
def A355777_row(n): return [v[1] for v in eulerian_stat(n)]
def A355777(n, k): return A355777_row(n)[k]
for n in range(8): print(A355777_row(n))

A356262 Partition triangle read by rows counting the irreducible permutations sorted by the partition type of their Lehmer code.

Original entry on oeis.org

1, 1, 0, 1, 0, 2, 1, 0, 2, 1, 9, 1, 0, 2, 3, 24, 17, 24, 1, 0, 2, 3, 3, 98, 29, 23, 156, 91, 55, 1, 0, 2, 8, 4, 181, 43, 157, 113, 1085, 243, 418, 714, 360, 118, 1, 0, 2, 7, 11, 4, 300, 61, 317, 461, 398, 2985, 536, 1822, 4366, 417, 7684, 1522, 3904, 2788, 1262, 245, 1

Offset: 0

Peter Luschny, Aug 01 2022

This is the Eulerian statistics of permutations as defined in A355777 restricted to the irreducible permutations. This is a refinement of A356263, which can be seen as Euler's triangle restricted to irreducible permutations.

The ordering of the partitions is defined in A080577. See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'.

			[0] 1;
[1] 1;
[2] 0, 1;
[3] 0, 2, 1;
[4] 0, [2, 1], 9, 1;
[5] 0, [2, 3], [24, 17], 24, 1;
[6] 0, [2, 3, 3], [98,  29, 23], [156, 91], 55, 1;
[7] 0, [2, 8, 4], [181, 43, 157, 113], [1085, 243, 418], [714, 360], 118, 1;
Summing the bracketed terms reduces the triangle to A356263 .
.
The Lehmer mapping of the irreducible permutations to the partitions, case n = 4, k = 1: 2341 and 4123 map to the partition [3, 1], and 3412 map to the partition [2, 2]. Thus A356263(4, 1) = 2 + 1 = 3. Compare with the example in A355777.
.
The partition mapping of row 4:
[4] => 0
[3, 1] => 2
[2, 2] => 1
[2, 1, 1] => 9
[1, 1, 1, 1] => 1

Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Cf. A356263 (reduced triangle), A003319 (row sums).

Cf. A355777.

import collections
def reducible(p) -> bool:
    return any(i for i in range(1, p.size())
        if all(p(j) < p(k)
            for j in range(1, i + 1)
                for k in range(i + 1, p.size() + 1)
    )   )
def perm_irreducible_stats(n: int):
    res = collections.defaultdict(int)
    for p in Permutations(n):
        if reducible(p): continue
        l = p.to_lehmer_code()
        c = [l.count(i) for i in range(len(p)) if i in l]
        res[Partition(reversed(sorted(c)))] += 1
    return sorted(res.items(), key=lambda x: len(x[0]))
@cached_function
def A356262_row(n):
    if n <= 1: return [1]
    return [0] + [v[1] for v in perm_irreducible_stats(n)]
def A356262(n, k): return A356262_row(n)[k]
for n in range(0, 8): print(A356262_row(n))

A356263 Triangle read by rows. The reduced triangle of the partition triangle of irreducible permutations (A356262). T(n, k) for n >= 1 and 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 9, 1, 0, 5, 41, 24, 1, 0, 8, 150, 247, 55, 1, 0, 14, 494, 1746, 1074, 118, 1, 0, 24, 1537, 10126, 13110, 4050, 245, 1, 0, 43, 4642, 52129, 122521, 79396, 14111, 500, 1, 0, 77, 13745, 248494, 967644, 1126049, 425471, 46833, 1011, 1

Offset: 1

Peter Luschny, Aug 01 2022

The triangle can be seen as Euler's triangle A008292 restricted to irreducible permutations.

See the comments in A356116 for the definition of the terms 'partition triangle' and 'reduced partition triangle'. The reduction procedure is formalized in the Sage program in A356116.

			[1] [1]
[2] [0,  1]
[3] [0,  2,     1]
[4] [0,  3,     9,      1]
[5] [0,  5,    41,     24,      1]
[6] [0,  8,   150,    247,     55,       1]
[7] [0, 14,   494,   1746,   1074,     118,     1]
[8] [0, 24,  1537,  10126,  13110,    4050,   245,      1]
[9] [0, 43,  4642,  52129, 122521,   79396, 14111,    500,    1]
[10][0, 77, 13745, 248494, 967644, 1126049, 425471, 46833, 1011, 1]
.
The 5 irreducible permutations counted with T(5, 2) are 23451, 51234, 31524, 34512, and 45123.

Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Cf. A356262 (partition triangle), A007059 (column 2), A003319 (row sums), A356114 (subdiagonal).

Cf. A008292, A356116.

# Uses function 'reduce_partition_triangle' from A356116.
reduce_partition_triangle(A356262_row, 8)

cp's OEIS Frontend

A355776 Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A355777 Partition triangle read by rows. A statistic of permutations given by their Lehmer code refining Euler's triangle A173018.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A356262 Partition triangle read by rows counting the irreducible permutations sorted by the partition type of their Lehmer code.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A356263 Triangle read by rows. The reduced triangle of the partition triangle of irreducible permutations (A356262). T(n, k) for n >= 1 and 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath