login
A355776
Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.
3
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,9
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'.
LINKS
Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.
EXAMPLE
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
PROG
(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))
CROSSREFS
Cf. A000217 (column 1), A002662 (subdiagonal), A000041 (row lengths), A056986 (row sums), A356116 (reduced triangle), A355777 (Euler-Lehmer).
Sequence in context: A352811 A019116 A213611 * A318304 A318989 A082493
KEYWORD
nonn,tabf
AUTHOR
Peter Luschny, Jul 27 2022
STATUS
approved