A356113
Triangle read by rows. T(n, k) = A355776(n, k) + A355777(n, k). Refining A174159, the Euler minus Narayana/Catalan triangle.
Original entry on oeis.org
1, 1, 1, 1, 1, 5, 1, 1, 10, 6, 16, 1, 1, 17, 25, 54, 58, 42, 1, 1, 26, 46, 27, 137, 354, 63, 224, 330, 99, 1, 1, 37, 77, 105, 291, 906, 513, 567, 817, 2883, 957, 811, 1466, 219, 1, 1, 50, 120, 188, 108, 548, 2020, 2632, 1508, 1682, 2356, 10116, 5574, 11724, 978, 4184, 18128, 8436, 2722, 5668, 466, 1
Offset: 0
Triangle T(n, k) begins:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 5, 1;
[4] 1, [10, 6], 16, 1;
[5] 1, [17, 25], [54, 58], 42, 1;
[6] 1, [26, 46, 27], [137, 354, 63], [224, 330], 99, 1;
[7] 1, [37, 77, 105], [291, 906, 513, 567], [817, 2883, 957],[811, 1466], 219, 1;
-
for n in range(8):
print([n], [A355776(n, k) + A355777(n, k)
for k in range(number_of_partitions(n))])
A356116
Triangle read by row. The reduced triangle of the partition_triangle A355776.
Original entry on oeis.org
0, 0, 0, 0, 1, 0, 0, 5, 5, 0, 0, 16, 46, 16, 0, 0, 42, 252, 252, 42, 0, 0, 99, 1086, 2241, 1086, 99, 0, 0, 219, 4097, 15129, 15129, 4097, 219, 0, 0, 466, 14272, 87058, 154426, 87058, 14272, 466, 0, 0, 968, 47300, 452672, 1305062, 1305062, 452672, 47300, 968, 0
Offset: 1
Triangle T(n, k) starts:
[1] [0]
[2] [0, 0]
[3] [0, 1, 0]
[4] [0, 5, 5, 0]
[5] [0, 16, 46, 16, 0]
[6] [0, 42, 252, 252, 42, 0]
[7] [0, 99, 1086, 2241, 1086, 99, 0]
[8] [0, 219, 4097, 15129, 15129, 4097, 219, 0]
[9] [0, 466, 14272, 87058, 154426, 87058, 14272, 466, 0]
[10][0, 968, 47300, 452672, 1305062, 1305062, 452672, 47300, 968, 0]
.
Row 6 of the partition triangle A355776 is:
[0, [10, 20, 12], [61, 162, 29], [102, 150], 42, 0]
Adding the bracketed terms reduces this row to row 6 of the above triangle.
-
from functools import cache
@cache
def Pn(n: int, k: int) -> int:
if k == 0: return 0
if n == 0 or k == 1: return 1
return Pn(n, k - 1) + Pn(n - k, k) if k <= n else Pn(n, k - 1)
def reduce_parts(fun, n: int) -> list[int]:
funn: list[int] = fun(n)
return [sum(funn[Pn(n, k):Pn(n, k + 1)]) for k in range(n)]
def reduce_partition_triangle(fun, n: int) -> list[list[int]]:
return [reduce_parts(fun, k) for k in range(1, n)]
reduce_partition_triangle(A355776_row, 6)
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
[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
-
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))
A355776
Partition triangle read by rows. A statistic of permutations whose Lehmer code is nonmonotonic, refining triangle A356116.
Original entry on oeis.org
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
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
-
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))
A356114
Number of irreducible permutations of n with partition type [2, 1, 1, ..., 1] (with '1' taken n - 2 times).
Original entry on oeis.org
0, 0, 0, 2, 9, 24, 55, 118, 245, 500, 1011, 2034, 4081, 8176, 16367, 32750, 65517, 131052, 262123, 524266, 1048553, 2097128, 4194279, 8388582, 16777189, 33554404, 67108835, 134217698, 268435425, 536870880, 1073741791, 2147483614, 4294967261, 8589934556, 17179869147
Offset: 0
a(4) = 9 = card({2413, 2431, 3142, 3241, 3421, 4132, 4213, 4231, 4312}). The other two permutations of type [2, 1, 1], 1432 and 3214, are reducible. That there are 11 permutations of type [2, 1, 1] we know from Euler's triangle A173018 or from its refined form A355777.
-
seq(`if`(n < 3, 0, combinat:-eulerian1(n, n - 2) - 2), n = 0..34);
Showing 1-5 of 5 results.
Comments