A356116 Triangle read by row. The reduced triangle of the partition_triangle A355776.

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

Author

Peter Luschny, Jul 28 2022

Keywords

• nonn
• tabl

Comments

By a partition triangle, we understand an irregular triangle where each row corresponds to a mapping of Partitions(n) -> ZZ. We assume a fixed order of the partitions given. Here we will use the ordering defined in A080577. Examples are A355776, A355777, and A134264. 'Reducing' then means summing the values corresponding to the partitions of n with length k. The 'reduced partition triangle' then is a regular triangle with T(n, k) with 1 <= k <= n.

Conversely, A355776, the statistic of permutations whose Lehmer code is nonmonotonic, can be seen as a refinement of this triangle, which in turn is a refinement of the sequence A056986, the number of permutations on [n] containing any given pattern alpha in the symmetric group S_3.

Examples

			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.
		

Links

• FindStat - Combinatorial Statistic Finder, The number of occurrences of the pattern [1,2,3] inside a permutation of length at least 3.
• Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.

Crossrefs

A002662 (column 1), A056986 (row sums), A355776 (refinement).

Programs

SageMath

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)