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

Author

Peter Luschny, Jul 27 2022

Keywords

• nonn
• tabf

Comments

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'.

Examples

			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
		

Links

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

Crossrefs

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

Programs

SageMath

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))