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

Author

Peter Luschny, Aug 11 2010

Keywords

• nonn
• tabf
• look
• nice

Comments

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

Examples

			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;
		

Links

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

Crossrefs

Row sums are A264151.

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

Programs

Mathematica

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 *)

Sage

# 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

Sage

# 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