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.
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]
for n in range(0, 8): print(A355776_row(n))
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Peter Luschny, Jul 27 2022
STATUS
approved