cp's OEIS Frontend

An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing.

A080635 enumerates increasing plane (ordered) unary-binary trees with n nodes labeled from the set {1,2,...n}. The entry T(n,k) of the present table counts forests of k increasing plane unary-binary trees having n nodes in total. See below for an example.

The Stirling number of the second kind Stirling2(n,k) counts the partitions of the set [n] set into k blocks. Arranging the elements in each block in ascending numerical order provides an alternative combinatorial interpretation for Stirling2(n,k) as counting forests of k increasing unary trees on n nodes. Thus we may view the present array as generalized Stirling numbers of the second kind (associated with A080635 or with the polynomials P(n,x) of A185415 - see formulas (1) and (2) below).

For a table of ordered forests of increasing plane unary-binary trees see A185423. For the enumeration of forests and ordered forests in the non-plane case see A147315 and A185421.

The Bell transform of A080635(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).

exp(x*(1-y+y^2)*D_y)*f(y)|_{y=0} = f(1-E(-x)) for any function f with a Taylor series. D_y means differentiation with respect to y and E(x) is the e.g.f. given below. For a proof of exp(x*g(y)*D_y)*f(y) = f(F^{-1}(x+F(y))) with the compositional inverse F^{-1} of F(y)=int(1/g(y),y) with F(0)=0 see, e.g., the Datolli et al. reference.

Number of increasing ordered trees on vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2. - David Callan, Mar 30 2007

Number of increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2. - Wenjin Woan, May 21 2011

Production array is [cosh(x),x] beheaded. Inverse is A147308. Row sums are A000111(n+1).

Unsigned version of A147308. - N. J. A. Sloane, Nov 07 2008

From Peter Bala, Jan 26 2011: (Start)

Define a polynomial sequence {Z(n,x)} n >= 0 by means of the recursion

(1)... Z(n+1,x) = 1/2*x*{Z(n,x-1)+Z(n,x+1)}

with starting condition Z(0,x) = 1. We call Z(n,x) the zigzag polynomial of degree n. This table lists the coefficients of these polynomials (for n >= 1) in ascending powers of x, row indices shifted by 1. The first few polynomials are

... Z(1,x) = x

... Z(2,x) = x^2

... Z(3,x) = x + x^3

... Z(4,x) = 4*x^2 + x^4

... Z(5,x) = 5*x + 10*x^3 + x^5.

The value Z(n,1) equals the zigzag number A000111(n). The polynomials Z(n,x) occur in formulas for the enumeration of permutations by alternating descents A145876 and in the enumeration of forests of non-plane unary binary labeled trees A147315.

{Z(n,x)}n>=0 is a polynomial sequence of binomial type and so is analogous to the sequence of monomials x^n. Denoting Z(n,x) by x^[n] to emphasize this analogy, we have, for example, the following analog of Bernoulli's formula for the sum of integer powers:

(2)... 1^[m]+...+(n-1)^[m] = (1/(m+1))*Sum_{k=0..m} (-1)^floor(k/2)*binomial(m+1,k)*B_k*n^[m+1-k],

where {B_k} k >= 0 = [1, -1/2, 1/6, 0, -1/30, ...] is the sequence of Bernoulli numbers.

For similarly defined polynomial sequences to Z(n,x) see A185415, A185417 and A185419. See also A185424.

(End)

[gd(x)^(-1)]^m = Sum_{n>=m} Tg(n,m)*(m!/n!)*x^n, where gd(x) is Gudermannian function, Tg(n+1,m+1)=T(n,m). - Vladimir Kruchinin, Dec 18 2011

The Bell transform of abs(E(n)), E(n) the Euler numbers. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

The table entries T(n,k), n,k>=1, are defined by the recurrence relation

1)... T(n+1,k) = (k-1)*T(n,k-1)-k*T(n,k)+(k+1)*T(n,k+1) with boundary condition T(1,k)=1.

The first column of the table is A080635.

For similar tables to calculate the zigzag numbers, the Springer numbers and the number of minimax trees see A185414, A185418 and A185420, respectively.

Define a polynomial sequence S(n,x) recursively by

(1)... S(n+1,x) = x*S(n,x-1)+(x+1)*S(n,x+1) with S(0,x) = 1.

This table lists the coefficients of these polynomials (for n>=1) in ascending powers of x.

The first few polynomials are

S(0,x) = 1

S(1,x) = 2*x+1

S(2,x) = 4*x^2+4*x+3

S(3,x) = 8*x^3+12*x^2+26*x+11.

The sequence [1,1,3,11,57,...] of constant terms of the polynomials is the sequence of Springer numbers A001586. The zeros of the polynomials S(n,-x) lie on the vertical line Re x = 1/2 in the complex plane.

Compare the recurrence (1) with the recurrence relation satisfied by the coefficients T(n,k) of the polynomials of A104035, namely

(2)... T(n+1,k) = k*T(n,k-1)+(k+1)*T(n,k+1).

DEFINITION

Define a sequence of polynomials M(n,x) by means of the recurrence relation

(1)... M(n+1,x) = x*{2*M(n,x+1)-M(n,x-1)},

with starting value M(0,x) = 1. We call these the minimax polynomials.

The first few polynomials are

M(1,x) = x

M(2,x) = x*(x + 3)

M(3,x) = x*(x^2 + 9*x + 10)

M(4,x) = x*(x^3 + 18*x^2 + 67*x + 42)

M(5,x) = x*(x^4 + 30*x^3 + 235*x^2 + 510*x + 248).

This triangle lists the coefficients of these polynomials (apart from M(0,x)) in ascending powers of x.

RELATION TO MINIMAX TREES

The value M(n,1) equals the number of minimax trees on n nodes - A080795(n). This result can be used to recursively calculate the entries of A080795 - see A185420.

In addition, the minimax polynomials M(n,x) occur in the formula for the number T(n,k) of forests of k minimax trees on n nodes. ... T(n,k) = 1/k!*sum {j = 0..k} (-1)^(k-j)*binomial(k,j)*M(n,j).

ANALOGIES WITH THE MONOMIALS

{M(n,x)}n>=0 is a polynomial sequence of binomial type and so is analogous to the sequence of monomials x^n. Denoting M(n,x) by x^[n] to emphasize this analogy, we have, for example, the following analog of Bernoulli's formula for the sum of integer powers:

(2)... 1^[p]+...+(n-1)^[p] = -2*n^[p]+ 1/(p+1)*Sum_{k = 0..floor(p/2)} 8^k*binomial(p+1,2k)*B_(2k)*n^[p+1-2k], where {B_k}k>=0 = [1, -1/2, 1/6, 0, -1/30, ...] is the sequence of Bernoulli numbers.

For other polynomial sequences defined by recurrences similar to (1), and related to the zigzag numbers A000111 and the Springer numbers A001586, see A147309 and A185417, respectively. See also A185415.

The Bell transform of A143523(n). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing. A080635 enumerates increasing plane (ordered) unary-binary trees with n nodes with labels drawn from the set {1,2,...,n}. The entry T(n,k) of the present table counts ordered forests of k increasing plane unary-binary trees with n nodes. See below for an example. See A185421 for the corresponding table in the non-plane case. See A185422 for the table for unordered forests of increasing plane unary-binary trees.