A179454 -id:A179454 - cp's OEIS frontend

A179455 Triangle read by rows: number of permutation trees of power n and height <= k + 1.

1, 1, 1, 2, 1, 5, 6, 1, 15, 23, 24, 1, 52, 106, 119, 120, 1, 203, 568, 700, 719, 720, 1, 877, 3459, 4748, 5013, 5039, 5040, 1, 4140, 23544, 36403, 39812, 40285, 40319, 40320, 1, 21147, 176850, 310851, 354391, 362057, 362836, 362879, 362880

Offset: 0

Peter Luschny, Aug 11 2010

Partial row sums of A179454. Special cases: A179455(n,1) = BellNumber(n) = A000110(n) for n > 1; A179455(n,n-1) = n! for n > 1 and A179455(n,n-2) = A033312(n) for n > 1. Column 3 is A187761(n) for n >= 3.

See the interpretation of Joerg Arndt in A187761: Maps such that f^[k](x) = f^[k-1](x) correspond to column k of A179455 (for n >= k). - Peter Luschny, Jan 08 2013

			As a (0,0)-based triangle with an additional column [1,0,0,0,...] at the left hand side:
1;
0, 1;
0, 1, 2;
0, 1, 5, 6;
0, 1, 15, 23, 24;
0, 1, 52, 106, 119, 120;
0, 1, 203, 568, 700, 719, 720;
0, 1, 877, 3459, 4748, 5013, 5039, 5040;
0, 1, 4140, 23544, 36403, 39812, 40285, 40319, 40320;
0, 1, 21147, 176850, 310851, 354391, 362057, 362836, 362879, 362880;

Alois P. Heinz, Rows n = 0..141, flattened
Swapnil Garg, Alan Peng, Classical and consecutive pattern avoidance in rooted forests, arXiv:2005.08889 [math.CO], May 2020.
Peter Luschny, Permutation Trees.

Row sums are A264151.

Cf. A000110, A179454, A179456, A187761, A264428.

b[n_, t_, h_] := b[n, t, h] = If[n == 0 || h == 0, 1, Sum[Binomial[n - 1, j - 1]*b[j - 1, 0, h - 1]*b[n - j, t, h], {j, 1, n}]];
T[0, 0] = 1; T[n_, k_] := b[n, 1, k];
Table[T[n, k], {n, 0, 9}, {k, 0, If[n == 0, 0, n-1]}] // Flatten (* Jean-François Alcover, Jul 10 2019, after Alois P. Heinz in A179454 *)

# Generating algorithm from Joerg Arndt.
def A179455row(n):
    def generate(n, k):
        if n == 0 or k == 0: return 0
        for j in range(n-1, 0, -1):
            f = a[j] + 1
            while f <= j:
                a[j] = f1 = fl = f
                for i in range(k):
                    fl = f1
                    f1 = a[fl]
                if f1 == fl: return j
                f += 1
            a[j] = 0
        return 0
    count = [1 for j in range(n)] if n > 0 else [1]
    for k in range(n):
        a = [0 for j in range(n)]
        while generate(n, k) != 0:
            count[k] += 1
    return count
for n in range(9): A179455row(n) # Peter Luschny, Jan 08 2013

# uses[bell_transform from A264428]
# Adds the column (1,0,0,0,..) to the left hand side and starts at n=0.
def A179455_matrix(dim):
    b = [1]+[0]*(dim-1); L = [b]
    for k in range(dim):
        b = [sum(bell_transform(n, b)) for n in range(dim)]
        L.append(b)
    return matrix(ZZ, dim, lambda n, k: L[k][n] if k<=n else 0)
print(A179455_matrix(10)) # Peter Luschny, Dec 06 2015

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

Original entry on oeis.org

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, 180, 57, 1, 1, 22, 42, 56, 156, 474, 267, 294, 426, 1494, 496, 423, 768, 120, 1, 1, 29, 64, 98, 56, 288, 1038, 1344, 768, 855, 1206, 5142, 2829, 5946, 496, 2127, 9204, 4288, 1389, 2904, 247, 1

Offset: 0

Peter Luschny, Jul 16 2022

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.
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'.
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.

			The table T(n, k) begins:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 4,            1;
[4] 1, [7, 4],       11,                   1;
[5] 1, [11, 15],     [32, 34],             26,               1;
[6] 1, [16, 26, 15], [76, 192, 34],        [122, 180],       57,         1;
[7] 1, [22, 42, 56], [156, 474, 267, 294], [426, 1494, 496], [423, 768], 120, 1;
Summing the bracketed terms reduces the triangle to Euler's triangle A173018.
.
The Lehmer mapping of the permutations to the partitions, case n = 4, k = 1:
   1243, 1324, 1423, 2134, 2341, 3124, 4123 map to the partition [3, 1] and
   1342, 2143, 2314, 3412 map to the partition [2, 2]. Thus A173018(4, 1) = 7 + 4 = 11.
.
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:
[6] => 1
[5, 1] => 16
[4, 2] => 26
[3, 3] => 15
[4, 1, 1] => 76
[3, 2, 1] => 192
[2, 2, 2] => 34
[3, 1, 1, 1] => 122
[2, 2, 1, 1] => 180
[2, 1, 1, 1, 1] => 57
[1, 1, 1, 1, 1, 1] => 1

Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker and Amanda Welch, Homomesies on permutations -- an analysis of maps and statistics in the FindStat database, arXiv:2206.13409 [math.CO], 2022. (Def. 4.20 and Prop. 4.22.)
Florent Hivert, Jean-Christophe Novelli and Jean-Yves Thibon, Multivariate generalizations of the Foata-Schützenberger equidistribution, arXiv:math/0605060 [math.CO], 2006.
Florent Hivert, Number of permutations whose sorted list of non zero multiplicities of the Lehmer code is the given partition, Statistics Database St000275, 2015.
Peter Luschny, Permutations with Lehmer, a SageMath Jupyter Notebook.
Wikipedia, Lehmer code.

Cf. A000295 (subdiagonal), A000124 (column 2), A000142 (row sums), A000041 (row lengths).

Cf. A179454 (permutation trees), A123125 and A173018 (Eulerian numbers), A145271 (variant).

import collections
@cached_function
def eulerian_stat(n):
    res = collections.defaultdict(int)
    for p in Permutations(n):
        c = p.to_lehmer_code()
        l = [c.count(i) for i in range(len(p)) if i in c]
        res[Partition(reversed(sorted(l)))] += 1
    return sorted(res.items(), key=lambda x: len(x[0]))
@cached_function
def A355777_row(n): return [v[1] for v in eulerian_stat(n)]
def A355777(n, k): return A355777_row(n)[k]
for n in range(8): print(A355777_row(n))

A291204 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that the root of each subtree contains the subtree's minimal label and h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 3, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 7, 6, 0, 4, 4, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 15, 25, 10, 0, 14, 30, 10, 0, 8, 5, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 31, 90, 65, 15, 0, 51, 174, 120, 20, 0, 54, 63, 15, 0, 13, 6, 0, 1, 0

Offset: 0

Alois P. Heinz, Aug 20 2017

Elements in rows h=0 give A023531.
Positive elements in rows h=1 give A008277.
Positive row sums per layer (and - with a different offset - positive elements in column t=1) give A179454.
Positive column sums per layer give A132393.

			n h\t: 0  1  2  3  4 5 : A179454 : A132393       : A000142
-----+-----------------+---------+---------------+--------
0 0  : 1               :       1 :  1            : 1
-----+-----------------+---------+---------------+--------
1 0  : 0  1            :       1 :  .            :
1 1  : 0               :         :  1            : 1
-----+-----------------+---------+---------------+--------
2 0  : 0  0  1         :       1 :  .  .         :
2 1  : 0  1            :       1 :  .            :
2 2  : 0               :         :  1  1         : 2
-----+-----------------+---------+---------------+--------
3 0  : 0  0  0  1      :       1 :  .  .  .      :
3 1  : 0  1  3         :       4 :  .  .         :
3 2  : 0  1            :       1 :  .            :
3 3  : 0               :         :  2  3  1      : 6
-----+-----------------+---------+---------------+--------
4 0  : 0  0  0  0  1   :       1 :  .  .  .  .   :
4 1  : 0  1  7  6      :      14 :  .  .  .      :
4 2  : 0  4  4         :       8 :  .  .         :
4 3  : 0  1            :       1 :  .            :
4 4  : 0               :         :  6 11  6  1   : 24
-----+-----------------+---------+---------------+--------
5 0  : 0  0  0  0  0 1 :       1 :  .  .  .  . . :
5 1  : 0  1 15 25 10   :      51 :  .  .  .  .   :
5 2  : 0 14 30 10      :      54 :  .  .  .      :
5 3  : 0  8  5         :      13 :  .  .         :
5 4  : 0  1            :       1 :  .            :
5 5  : 0               :         : 24 50 35 10 1 : 120
-----+-----------------+---------+---------------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000012, A000110, A000142, A000217, A000225, A000254, A000325, A001791, A007820, A008277, A023531, A048993, A057427, A058692, A179454, A291203, A291336, A291529.

b:= proc(n, t, h) option remember; expand(`if`(n=0 or h=0, x^(t*n), add(
       binomial(n-1, j-1)*x^t*b(j-1, 0, h-1)*b(n-j, t, h), j=1..n)))
    end:
g:= (n, h)-> b(n, 1, h)-`if`(h=0, 0, b(n, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..8);

b[n_, t_, h_] := b[n, t, h] = Expand[If[n == 0 || h == 0, x^(t*n), Sum[Binomial[n-1, j-1]*x^t*b[j-1, 0, h-1]*b[n-j, t, h], {j, 1, n}]]];
g[n_, h_] := b[n, 1, h] - If[h == 0, 0, b[n, 1, h - 1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n - h}], {h, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

Sum_{i=0..n} F(n,i,n-i) = A000325(n).
Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000142(n).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A000254(n).
Sum_{t=0..n-1} F(n,1,t) = A058692(n) =  A000110(n) - 1.
F(2n,n,n) = A001791(n) for n>0.
F(2n,1,n) = A007820(n).
F(n,1,n-1) = A000217(n-1) for n>0.
F(n,n-1,1) = A057427(n).
F(n,1,2) = A000225(n-1) for n>2.
F(n,0,n) = 1 = A000012(n).
F(n,0,0) = A000007(n).

A179456 Triangle read by rows: number of permutation trees of power n and height <= n - k.

Original entry on oeis.org

1, 1, 2, 1, 6, 5, 1, 24, 23, 9, 1, 120, 119, 68, 14, 1, 720, 719, 517, 152, 20, 1, 5040, 5039, 4163, 1581, 292, 27, 1, 40320, 40319, 36180, 16776, 3917, 508, 35, 1, 362880, 362879, 341733, 186030, 52029, 8489, 823, 44, 1

Offset: 0

Peter Luschny, Aug 11 2010

Partial row sums of A179454 starting from the diagonal. Special case: A179456(n,n-2) = A000096(n) for n > 1.

			1,
1,
2, 1,
6, 5, 1,
24, 23, 9, 1,
120, 119, 68, 14, 1,
720, 719, 517, 152, 20, 1,
5040, 5039, 4163, 1581, 292, 27, 1,
40320, 40319, 36180, 16776, 3917, 508, 35, 1,
362880, 362879, 341733, 186030, 52029, 8489, 823, 44, 1

Peter Luschny, Permutation trees.

Cf. A179454, A179455.

A264151 Row sums of A179455.

Original entry on oeis.org

1, 1, 3, 12, 63, 398, 2911, 24177, 224824, 2313892, 26107679, 320412404, 4249353369, 60561549764, 923107802463, 14985538729504, 258138422935578, 4702896016961154, 90350619640638353, 1825564783445799571, 38700814850328413380, 858915876402686598209, 19916917035087719607321

Offset: 0

Peter Luschny, Dec 06 2015

nonn

			a(4) = 5*0 + 4*1 + 3*14 + 2*8 + 1*1 = 63.

Vaclav Kotesovec, Table of n, a(n) for n = 0..447
Swapnil Garg, Alan Peng, Classical and consecutive pattern avoidance in rooted forests, arXiv:2005.08889 [math.CO], May 2020.
Peter Luschny, Permutation Trees

Cf. A179454, A179455, A264428.

# uses[bell_transform from A264428]
def A264151_list(len):
    b = [1]+[0]*(len-1); L = [b]
    for k in range(len):
        b = [sum((bell_transform(n, b))) for n in range(len)]
        L.append(b)
    return [sum(L[k][n] for k in (0..n)) for n in range(len)]
print(A264151_list(10))

a(n) = Sum_{k=0..n} (n-k+1)*A179454(n,k), where A179454(n,k) is read as a (0,0)-based table with an additional column (1,0,0,0,...) at the left hand side.

cp's OEIS Frontend

A179455 Triangle read by rows: number of permutation trees of power n and height <= k + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Sage

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

A291204 Number F(n,h,t) of forests of t labeled rooted trees with n vertices such that the root of each subtree contains the subtree's minimal label and h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A179456 Triangle read by rows: number of permutation trees of power n and height <= n - k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A264151 Row sums of A179455.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula