cp's OEIS Frontend

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

%I A355777 #30 Mar 18 2023 08:49:14
%S A355777 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,
%T A355777 180,57,1,1,22,42,56,156,474,267,294,426,1494,496,423,768,120,1,1,29,
%U A355777 64,98,56,288,1038,1344,768,855,1206,5142,2829,5946,496,2127,9204,4288,1389,2904,247,1
%N A355777 Partition triangle read by rows. A statistic of permutations given by their Lehmer code refining Euler's triangle A173018.
%C A355777 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.
%C A355777 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'.
%C A355777 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.
%H A355777 Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker and Amanda Welch, <a href="https://doi.org/10.48550/arxiv.2206.13409">Homomesies on permutations -- an analysis of maps and statistics in the FindStat database</a>, arXiv:2206.13409 [math.CO], 2022. (Def. 4.20 and Prop. 4.22.)
%H A355777 Florent Hivert, Jean-Christophe Novelli and Jean-Yves Thibon, <a href="https://arxiv.org/abs/math/0605060">Multivariate generalizations of the Foata-Schützenberger equidistribution</a>, arXiv:math/0605060 [math.CO], 2006.
%H A355777 Florent Hivert, <a href="http://www.findstat.org/StatisticsDatabase/St000275">Number of permutations whose sorted list of non zero multiplicities of the Lehmer code is the given partition</a>, Statistics Database St000275, 2015.
%H A355777 Peter Luschny, <a href="https://github.com/PeterLuschny/PermutationsWithLehmer/blob/main/PermutationsWithLehmer.ipynb">Permutations with Lehmer</a>, a SageMath Jupyter Notebook.
%H A355777 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lehmer_code">Lehmer code</a>.
%e A355777 The table T(n, k) begins:
%e A355777 [0] 1;
%e A355777 [1] 1;
%e A355777 [2] 1, 1;
%e A355777 [3] 1, 4,            1;
%e A355777 [4] 1, [7, 4],       11,                   1;
%e A355777 [5] 1, [11, 15],     [32, 34],             26,               1;
%e A355777 [6] 1, [16, 26, 15], [76, 192, 34],        [122, 180],       57,         1;
%e A355777 [7] 1, [22, 42, 56], [156, 474, 267, 294], [426, 1494, 496], [423, 768], 120, 1;
%e A355777 Summing the bracketed terms reduces the triangle to Euler's triangle A173018.
%e A355777 .
%e A355777 The Lehmer mapping of the permutations to the partitions, case n = 4, k = 1:
%e A355777    1243, 1324, 1423, 2134, 2341, 3124, 4123 map to the partition [3, 1] and
%e A355777    1342, 2143, 2314, 3412 map to the partition [2, 2]. Thus A173018(4, 1) = 7 + 4 = 11.
%e A355777 .
%e A355777 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:
%e A355777 [6] => 1
%e A355777 [5, 1] => 16
%e A355777 [4, 2] => 26
%e A355777 [3, 3] => 15
%e A355777 [4, 1, 1] => 76
%e A355777 [3, 2, 1] => 192
%e A355777 [2, 2, 2] => 34
%e A355777 [3, 1, 1, 1] => 122
%e A355777 [2, 2, 1, 1] => 180
%e A355777 [2, 1, 1, 1, 1] => 57
%e A355777 [1, 1, 1, 1, 1, 1] => 1
%o A355777 (SageMath)
%o A355777 import collections
%o A355777 @cached_function
%o A355777 def eulerian_stat(n):
%o A355777     res = collections.defaultdict(int)
%o A355777     for p in Permutations(n):
%o A355777         c = p.to_lehmer_code()
%o A355777         l = [c.count(i) for i in range(len(p)) if i in c]
%o A355777         res[Partition(reversed(sorted(l)))] += 1
%o A355777     return sorted(res.items(), key=lambda x: len(x[0]))
%o A355777 @cached_function
%o A355777 def A355777_row(n): return [v[1] for v in eulerian_stat(n)]
%o A355777 def A355777(n, k): return A355777_row(n)[k]
%o A355777 for n in range(8): print(A355777_row(n))
%Y A355777 Cf. A000295 (subdiagonal), A000124 (column 2), A000142 (row sums), A000041 (row lengths).
%Y A355777 Cf.  A179454 (permutation trees), A123125 and A173018 (Eulerian numbers), A145271 (variant).
%K A355777 nonn,tabf
%O A355777 0,6
%A A355777 _Peter Luschny_, Jul 16 2022