A179455 -id:A179455 - cp's OEIS frontend

A264151 Row sums of A179455.

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.

A264428 Triangle read by rows, Bell transform of Bell numbers.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 0, 5, 11, 6, 1, 0, 15, 45, 35, 10, 1, 0, 52, 205, 210, 85, 15, 1, 0, 203, 1029, 1330, 700, 175, 21, 1, 0, 877, 5635, 8946, 5845, 1890, 322, 28, 1, 0, 4140, 33387, 63917, 50358, 20055, 4410, 546, 36, 1, 0, 21147, 212535, 484140, 450905, 214515, 57855, 9240, 870, 45, 1

Offset: 0

Peter Luschny, Nov 13 2015

Consider the sequence S0 -> T0 -> S1 -> T1 -> S2 -> T2 -> ... Here Sn -> Tn indicates the Bell transform mapping a sequence Sn to a triangle Tn as defined in the link and Tn -> S{n+1} the operator associating a triangle with the sequence of its row sums. If
S0 = A000012 = <1,1,1,...> then
T0 = A048993 # Stirling subset numbers,
S1 = A000110 # Bell numbers,
T1 = A264428 # Bell transform of Bell numbers,
S2 = A187761 # second-order Bell numbers,
T2 = A264430 # Bell transform of second-order Bell numbers,
S3 = A264432 # third-order Bell numbers.
This construction is closely related to permutations trees and A179455. Sn is A179455_col(n+1) prepended by A179455_diag(k) = k! for k <= n. In other words, Sn 'converges' to n! for n -> oo.
Given a sequence (s(n))n>=0 with s(0) = 0 and with e.g.f. B(x) = Sum_{n >= 1} s(n)*x^n/n!, then the Bell matrix associated with s(n) equals the exponential Riordan array [1, B(x)] belonging to the Lagrange subgroup of the exponential Riordan group. Omitting the first row and column from the Bell matrix produces the exponential Riordan array [d/dx(B(x)), B(x)] belonging to the Derivative subgroup of the exponential Riordan group. - Peter Bala, Jun 07 2016

			Triangle starts:
[1]
[0,   1]
[0,   1,    1]
[0,   2,    3,    1]
[0,   5,   11,    6,    1]
[0,  15,   45,   35,   10,    1]
[0,  52,  205,  210,   85,   15,   1]
[0, 203, 1029, 1330,  700,  175,  21,  1]
[0, 877, 5635, 8946, 5845, 1890, 322, 28, 1]

G. C. Greubel, Table of n, a(n) for n = 0..1325
Peter Luschny, The Bell transform
Peter Luschny, Permutation Trees

Cf. A000012, A000110, A000217, A000914, A027801, A048993, A051836, A179455, A187761 (row sums), A264430, A264432, A265312.

# Computes sequence in matrix form.
BellMatrix := proc(f, len) local T, A; A := [seq(f(n), n=0..len-2)];
T := proc(n, k) option remember; if k=0 then k^n else
add(binomial(n-1,j-1)*T(n-j,k-1)*A[j], j=1..n-k+1) fi end;
Matrix(len, (n,k)->T(n-1,k-1), shape=triangular[lower]) end:
BellMatrix(n -> combinat:-bell(n), 9); # Peter Luschny, Jan 21 2016
# Alternative, using the recurrence of Peter Bala:
R := proc(n) option remember; if n = 0 then 1 else
t*add(binomial(n-1,k)*combinat:-bell(k)*R(n-k-1,t),k=0..n-1) fi end:
T_row := n-> seq(coeff(R(n), t, k), k=0..n):
seq(print(T_row(n)),n=0..8); # Peter Luschny, Jun 09 2016

BellMatrix[f_Function|f_Symbol, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len-1}, {k, 0, len-1}]];
rows = 11;
M = BellMatrix[BellB, rows];
Table[M[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 21 2016, updated Jul 14 2018 *)
With[{r = 8}, Flatten[Table[BellY[n, k, BellB[Range[0, r]]], {n, 0, r}, {k, 0, n}]]] (* Jan Mangaldan, May 22 2016 *)

bell_matrix(f, len) = { my( m = matrix(len, len) );  m[1, 1] = 1;
  for( n = 1, len-1, m[n+1, 2] = f(n-1) );
  for( n = 0, len-1, for( k = 1, n,
     m[n+1, k+1] = sum(j = 1, n-k+1, binomial(n-1,j-1)*m[n-j+1,k]*m[j+1,2]) ));
  return( m )
}
f(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1 - i*x)), x^n * O(x)), n);
bell_matrix(f, 9) \\ Peter Luschny, Jan 24 2016

from functools import cache
from math import comb as binomial
def BellMatrix(f, size):
    A = [f(n) for n in range(size - 1)]
    @cache
    def T(n, k):
        if k == 0: return k ** n
        return sum(
            binomial(n - 1, j) * T(n - j - 1, k - 1) * A[j]
            for j in range(n - k + 1) )
    return [[T(n, k) for k in range(n + 1)] for n in range(size)]
@cache
def b(n, k=0): return n < 1 or k*b(n-1, k) + b(n-1, k+1)
print(BellMatrix(b, 9))  # Peter Luschny, Jun 14 2022

# The functions below are referenced in various other sequences.
def bell_transform(n, a): # partition_based
    row = []
    fn = factorial(n)
    for k in (0..n):
        result = 0
        for p in Partitions(n, length=k):
            factorial_product = 1
            power_factorial_product = 1
            for part, count in p.to_exp_dict().items():
                factorial_product *= factorial(count)
                power_factorial_product *= factorial(part)**count
            coefficient = fn//(factorial_product*power_factorial_product)
            result += coefficient*prod([a[i-1] for i in p])
        row.append(result)
    return row
def bell_matrix(generator, dim):
    G = [generator(k) for k in srange(dim)]
    row = lambda n: bell_transform(n, G)
    return matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)])
def inverse_bell_matrix(generator, dim):
    G = [generator(k) for k in srange(dim)]
    row = lambda n: bell_transform(n, G)
    M = matrix(ZZ, [row(n)+[0]*(dim-n-1) for n in srange(dim)]).inverse()
    return matrix(ZZ, dim, lambda n,k: (-1)^(n-k)*M[n,k])
bell_numbers = [sum(bell_transform(n, [1]*10)) for n in range(11)]
for n in range(11): print(bell_transform(n, bell_numbers))

From Peter Bala, Jun 07 2016: (Start)
E.g.f.: exp(t*B(x)), where B(x) = Integral_{u = 0..x} exp(exp(u) - 1) du =  x + x^2/2! + 2*x^3/3! + 5*x^4/4! + 15*x^5/5! + 52*x^6/6! + ....
Row polynomial recurrence: R(n+1,t) = t*Sum_{k = 0 ..n} binomial(n,k)*Bell(k)* R(n-k,t) with R(0,t) = 1. (End)

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Original entry on oeis.org

1, 1, 2, 6, 23, 106, 568, 3459, 23544, 176850, 1451253, 12904312, 123489888, 1264591561, 13790277294, 159466823794, 1948259002647, 25066729706582, 338670605492700, 4792623436607059, 70873649458154500, 1092969062435462254, 17543703470388927229, 292600906102204630092

Offset: 0

Joerg Arndt, Jan 04 2013

This sequence and A187771 and A187824 are winners in the contest held at the 2013 AMS/MAA Joint Mathematics Meetings. - T. D. Noe, Jan 14 2013
Number of monotonic-labeled forests on n vertices with rooted trees of height less than 3. A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex. (See comment by Dennis P. Walsh at A000110; with "greater" instead of "smaller".) To see this, consider the maps [1,2,...,n] -> [0,1,...,n-1] with f(x) < x.
As the maps are valid (left) inversion tables for permutations (see example), we obtain a simple bijection between permutations and such forests.
For n>=3 column 3 of A179455; maps such that f^[k](x) = f^[k-1](x) correspond to column k of A179455 (for n>=k).
Explanation of the Maple routine by Alois P. Heinz, Jan 15 2013: (Start)
b(n,x,y) is the number of forests consisting of trees we want to count, where n nodes are still to be inserted and x nodes at level 0 (the roots) and y nodes at level 1 are already present, plus perhaps some nodes at level 2 (whose number is not of interest).
If the next node is inserted at level 0 then n-1 remaining nodes are to be inserted (and level 0 has one more node: x+1).  There is only one possibility to do that.
If the next node is inserted at level 1 then again n-1 nodes are to be inserted (and level 1 has one more node: y+1).  The inserted node can have x different predecessors (at level 0), accounted by the multiplication by x.
If a node is inserted at level 2 then (again) n-1 nodes are to be inserted and level 2 has one more node (which is not counted).  The inserted node can have y predecessors, accounted by the multiplication by y.
b(0,x,y) = 1 counts any fixed forest that has received all its nodes.
b(n,0,0) counts all forests that can be constructed by inserting n nodes into the empty forest.
(End)
Also the row sums of the Bell transform of the Bell numbers. Since the Bell numbers are the row sums of the Bell transform of the Stirling_2 numbers they might also be called second order Bell numbers. (Also note that the Stirling_2 numbers are the row sums of the Bell transform of the simplest sequence of positive numbers 1,1,1,... which in turn are the row sums of the Bell transform of the characteristic function of 0. See the link 'Bell Transform' for more about this hierarchy which might be called the Bell hierarchy.) - Peter Luschny, Jan 23 2016

			There are a(4)=23 such maps f: [0,1,2,3] -> [0,1,2,3], all 4-digit mixed-radix numbers [f(0), f(1), f(2), f(3)] where 0 <= f(k) <= k (rising factorial basis) except for [ 0 0 1 2 ], as f(3)=2 and f(f(3)) = f(2) = 1 != f(f(f(3))) = f(f(2)) = f(1) = 0.
The exception corresponds to the tree 0 -- 1 -- 2 -- 3 (0 is the root), which can be identified with the map [1,2,3,4] -> [0,1,2,3] where f(k)=k-1.

Alois P. Heinz, Table of n, a(n) for n = 0..493
Peter Luschny, The Bell transform
Peter Luschny, Permutation Trees
D. P. Walsh, Counting forests with Stirling and Bell numbers

Cf. A000110 (Number of maps f: [n] -> [n] where f(x)<=x and f(f(x))=f(x) ).
Cf. A179455 (permutation trees of power n and height <= k+1 ).
Cf. A000949 (maps f: [n] -> [n] where f(f(x)) = f(f(f(x))) ).

b:= proc(n, x, y) option remember; `if`(n=0, 1,
       b(n-1, x+1, y) +x*b(n-1, x, y+1) +y*b(n-1, x, y))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 09 2013
# The function BellMatrix is defined in A264428.
B := BellMatrix(n -> combinat:-bell(n), 24):
seq(add(i, i=LinearAlgebra:-Row(B,n)), n=1..24); # Peter Luschny, Jan 23 2016
# alternative Maple program:
b:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*b(j-1, h-1)*b(n-j, h), j=1..n))
    end:
a:= n-> b(n, 2):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 21 2017

b[n_, x_, y_] := b[n, x, y] = If[n == 0, 1, b[n-1, x+1, y]+x*b[n-1, x, y+1]+y*b[n-1, x, y]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
Table[Sum[BellY[n, k, BellB[Range[n] - 1]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

/* using e.g.f. A(x) */
x = 'x + O('x^66);
B = exp( exp(x) - 1 );  /* e.g.f. of Bell numbers */
A = serconvol( x * B, -log(1-x) );
/* A = intformal(B) */ /* alternative to last line */
A = exp( A );
Vec( serlaplace( A ) )

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def a(n): return b(n, 2)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 21 2017, after second Maple program by Alois P. Heinz

Conjecture (confirmed below) about the e.g.f. A(x): Let B(x) = Sum_{n>=0} b(n) * x^n/n! = exp(exp(x)-1) the e.g.f. of the Bell numbers (A000110). Then A(x) = Sum_{n>=0} a(n) * x^n/n! = exp( Sum_{n>=0} b(n) * x^(n+1)/(n+1)! ), see PARI program.
From Joerg Arndt, Jan 14 2013: (Start)
Conjecture (confirmed below):  Let C(0,x) = 1 and for k>=1 C(k, x) = exp( integral(C(k-1,x)) ) then C(k,x) is the e.g.f. for monotonic-labeled forests on n vertices with rooted trees of height less than k (column k of A179455(n,k) for k>=1, n>=k).
For k=1 (C(1,x)=exp(x)) and k=2 (C(2,x)=exp(exp(x)-1)) this is known to be true, for k=3 this is the conjecture above. (End)
From Joerg Arndt, Jan 15 2013: (Start)
Gareth McCaughan, on the math-fun mailing list (Jan 14 2013), writes
"If F is the e.g.f. for Things Of Size n, then exp(F) is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.)
"Which means the conjecture is right. (The integral turns that into 'multisets of things whose sizes plus 1 add up to n'; a tree is a forest together with a new node on top.)"
(End)

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

Peter Luschny, Aug 11 2010

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

			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

Alois P. Heinz, Rows n = 0..141, flattened
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-2023. (Def. 4.20 and Prop. 4.22.)
FindStat - Combinatorial Statistic Finder, The height index of a permutation.
Peter Luschny, Permutation Trees.

Cf. A008292, A123125, A179455, A179456, A264428.

Row sums give A000142.

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

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

# 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

# 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

cp's OEIS Frontend

A264151 Row sums of A179455.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Sage

Formula

A264428 Triangle read by rows, Bell transform of Bell numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A179454 Permutation trees of power n and height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Sage

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs