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

%I #50 May 25 2020 11:51:15

%S 1,1,1,2,1,5,6,1,15,23,24,1,52,106,119,120,1,203,568,700,719,720,1,

%T 877,3459,4748,5013,5039,5040,1,4140,23544,36403,39812,40285,40319,

%U 40320,1,21147,176850,310851,354391,362057,362836,362879,362880

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

%C 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.

%C 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

%H Alois P. Heinz, <a href="/A179455/b179455.txt">Rows n = 0..141, flattened</a>

%H Swapnil Garg, Alan Peng, <a href="https://arxiv.org/abs/2005.08889">Classical and consecutive pattern avoidance in rooted forests</a>, arXiv:2005.08889 [math.CO], May 2020.

%H Peter Luschny, <a href="http://www.oeis.org/wiki/User:Peter_Luschny/PermutationTrees">Permutation Trees</a>.

%e As a (0,0)-based triangle with an additional column [1,0,0,0,...] at the left hand side:

%e 1;

%e 0, 1;

%e 0, 1, 2;

%e 0, 1, 5, 6;

%e 0, 1, 15, 23, 24;

%e 0, 1, 52, 106, 119, 120;

%e 0, 1, 203, 568, 700, 719, 720;

%e 0, 1, 877, 3459, 4748, 5013, 5039, 5040;

%e 0, 1, 4140, 23544, 36403, 39812, 40285, 40319, 40320;

%e 0, 1, 21147, 176850, 310851, 354391, 362057, 362836, 362879, 362880;

%t 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 T[0, 0] = 1; T[n_, k_] := b[n, 1, k];

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

%o (Sage)

%o # Generating algorithm from Joerg Arndt.

%o def A179455row(n):

%o def generate(n, k):

%o if n == 0 or k == 0: return 0

%o for j in range(n-1, 0, -1):

%o f = a[j] + 1

%o while f <= j:

%o a[j] = f1 = fl = f

%o for i in range(k):

%o fl = f1

%o f1 = a[fl]

%o if f1 == fl: return j

%o f += 1

%o a[j] = 0

%o return 0

%o count = [1 for j in range(n)] if n > 0 else [1]

%o for k in range(n):

%o a = [0 for j in range(n)]

%o while generate(n, k) != 0:

%o count[k] += 1

%o return count

%o for n in range(9): A179455row(n) # _Peter Luschny_, Jan 08 2013

%o (Sage) # uses[bell_transform from A264428]

%o # Adds the column (1,0,0,0,..) to the left hand side and starts at n=0.

%o def A179455_matrix(dim):

%o b = [1]+[0]*(dim-1); L = [b]

%o for k in range(dim):

%o b = [sum(bell_transform(n, b)) for n in range(dim)]

%o L.append(b)

%o return matrix(ZZ, dim, lambda n, k: L[k][n] if k<=n else 0)

%o print(A179455_matrix(10)) # _Peter Luschny_, Dec 06 2015

%Y Row sums are A264151.

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

%K nonn,tabf,look,nice

%O 0,4

%A _Peter Luschny_, Aug 11 2010