This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A179454 Permutation trees of power n and height k. 5
 1, 1, 1, 1, 1, 4, 1, 1, 14, 8, 1, 1, 51, 54, 13, 1, 1, 202, 365, 132, 19, 1, 1, 876, 2582, 1289, 265, 26, 1, 1, 4139, 19404, 12859, 3409, 473, 34, 1, 1, 21146, 155703, 134001, 43540, 7666, 779, 43, 1, 1, 115974, 1335278, 1471353, 569275, 120200, 15456, 1209, 53, 1 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,6 COMMENTS A permutation tree is a labeled rooted tree that has vertex set {0,1,2,..,n} and root 0 in which each child is larger than its parent and the children are in ascending order from the left to the right. The height of a permutation tree is the number of descendants of the root on the longest chain starting at the root and ending at a leaf. This defines C(n,height) for 1<=height<=n. Row sum is n!. Setting T(n,k) = C(n,k+1) for 0<=k 2; [1, 2, 4, 3] => 3; [1, 3, 2, 4] => 3; [1, 3, 4, 2] => 3; [1, 4, 2, 3] => 3; [1, 4, 3, 2] => 4; [2, 1, 3, 4] => 2; [2, 1, 4, 3] => 3; [2, 3, 1, 4] => 2; [2, 3, 4, 1] => 2; [2, 4, 1, 3] => 2; [2, 4, 3, 1] => 3; [3, 1, 2, 4] => 2; [3, 1, 4, 2] => 2; [3, 2, 1, 4] => 2; [3, 2, 4, 1] => 2; [3, 4, 1, 2] => 2; [3, 4, 2, 1] => 3; [4, 1, 2, 3] => 1; [4, 1, 3, 2] => 2; [4, 2, 1, 3] => 2; [4, 2, 3, 1] => 2; [4, 3, 1, 2] => 2; [4, 3, 2, 1] => 3; Gives row(4) = [0, 1, 14, 8, 1]. - Peter Luschny, Dec 09 2015 MAPLE b:= proc(n, t, h) option remember; `if`(n=0 or h=0, 1, add(       binomial(n-1, j-1)*b(j-1, 0, h-1)*b(n-j, t, h), j=1..n))     end: T:= (n, k)-> b(n, 1, k-1)-`if`(k<2, 0, b(n, 1, k-2)): seq(seq(T(n, k), k=min(n, 1)..n), n=0..12);  # Alois P. Heinz, Aug 24 2017 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[n_, k_] :=  b[n, 1, k - 1] - If[k < 2, 0, b[n, 1, k - 2]]; Table[T[n, k], {n, 0, 12}, {k, Min[n, 1], n}] // Flatten (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *) PROG (Sage) # The function bell_transform is defined in A264428. # Adds the column (1, 0, 0, 0, ..) to the left hand side and starts at n=0. def A179454_matrix(dim):     a = [2]+[0]*(dim-1); b = [1]+[0]*(dim-1); L = [b, a]     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+1][n]-L[k][n] if k<=n else 0) A179454_matrix(9) # Peter Luschny, Dec 07 2015 (Sage) # Alternatively, based on FindStat statistic St000308: def statistic_000308(pi):     if pi == []: return 0     h, i, branch, next = 0, len(pi), [0], pi[0]     while true:         while next < branch[len(branch)-1]:             del(branch[len(branch)-1])         current = 0         while next > current:             i -= 1             branch.append(next)             h = max(h, len(branch)-1)             if i == 0: return h             current, next = next, pi[i] def A179454_row(n):     L = [0]*(n+1)     for p in Permutations(n):         L[statistic_000308(p)] += 1     return L [A179454_row(n) for n in range(8)] # Peter Luschny, Dec 09 2015 CROSSREFS Cf. A008292, A123125, A179455, A179456, A264428. Row sums give A000142. Sequence in context: A064281 A267318 A050154 * A058711 A202906 A177984 Adjacent sequences:  A179451 A179452 A179453 * A179455 A179456 A179457 KEYWORD nonn,tabf AUTHOR Peter Luschny, Aug 11 2010 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 21 13:23 EST 2019. Contains 319350 sequences. (Running on oeis4.)