cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

A179454 Permutation trees of power n and height k.

Original entry on oeis.org

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
Offset: 0

Views

Author

Peter Luschny, Aug 11 2010

Keywords

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<=kA008292 and the Eulerian polynomials as defined via DLMF 26.14.1. (See A123125 for the triangle with an (0,0)-based offset.)

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,    1 ]
  [ 0, 1,    4,     1 ]
  [ 0, 1,   14,     8,     1 ]
  [ 0, 1,   51,    54,    13,    1 ]
  [ 0, 1,  202,   365,   132,   19,   1 ]
  [ 0, 1,  876,  2582,  1289,  265,  26,  1 ]
  [ 0, 1, 4139, 19404, 12859, 3409, 473, 34, 1]
--------------------------------------------
The height statistic over permutations, n=4.
  [1, 2, 3, 4] => 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

Links

Crossrefs

Cf. A008292, A123125, A179455, A179456, A264428.
Row sums give A000142.

Programs

  • 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 *)
  • Sage
    # uses[bell_transform from 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

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

Original entry on oeis.org

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

Views

Author

Peter Luschny, Aug 11 2010

Keywords

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

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
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.