A080635 -id:A080635 - cp's OEIS frontend

A185422 Forests of k increasing plane unary-binary trees on n nodes. Generalized Stirling numbers of the second kind associated with A185415.

1, 1, 1, 3, 3, 1, 9, 15, 6, 1, 39, 75, 45, 10, 1, 189, 459, 330, 105, 15, 1, 1107, 3087, 2709, 1050, 210, 21, 1, 7281, 23535, 23814, 11109, 2730, 378, 28, 1, 54351, 197235, 228285, 122850, 36099, 6174, 630, 36, 1

Offset: 1

Peter Bala, Jan 28 2011

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

			Triangle begins
n\k|....1......2......3......4......5......6......7
===================================================
..1|....1
..2|....1......1
..3|....3......3......1
..4|....9.....15......6......1
..5|...39.....75.....45.....10......1
..6|..189....459....330....105.....15......1
..7|.1107...3087...2709...1050....210.....21......1
..
Examples of the recurrence:
T(5,1) = 39 = T(4,0)+1*T(4,1)+2*T(4,2) = 1*9+2*15;
T(6,3) = 330 = T(5,2)+3*T(5,3)+3*4*T(5,4) = 75+3*45+12*10.
Examples of forests:
T(4,1) = 9. The 9 plane increasing unary-binary trees on 4 nodes are shown in the example section of A080635.
T(4,2) = 15. The 15 forests consisting of two plane increasing unary-binary trees on 4 nodes consist of the 12 forests
......... ......... ...3.....
.2...3... .3...2... ...|.....
..\./.... ..\./.... ...2.....
...1...4. ...1...4. ...|.....
......... ......... ...1...4.
.
......... ......... ...4.....
.2...4... .4...2... ...|.....
..\./.... ..\./.... ...2.....
...1...3. ...1...3. ...|.....
......... ......... ...1...3.
.
......... ......... ...4.....
.3...4... .4...3... ...|.....
..\./.... ..\./.... ...3.....
...1...2. ...1...2. ...|.....
......... ......... ...1...2.
......... ......... ...4.....
.3...4... .4...3... ...|.....
..\./.... ..\./.... ...3.....
...2...1. ...2...1. ...|.....
......... ......... ...2...1.
.
and the three remaining forests
......... ......... ..........
..2..4... ..3..4... ..4...3...
..|..|... ..|..|... ..|...|...
..1..3... ..1..2... ..1...2...
......... ......... ..........

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees
T. Copeland, Mathemagical Forests

Cf. A080635, A008277, A185415, A147315, A185423.

#A185422
P := proc(n,x)
description 'polynomial sequence P(n,x) A185415'
if n = 0
return 1
else
return x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
end proc:
with combinat:
T:= (n,k) -> 1/k!*add ((-1)^(k-j)*binomial(k,j)*P(n,j),j = 0..k):
for n from 1 to 10 do
seq(T(n,k),k = 1..n);
end do;

t[n_, k_] := t[n, k] = t[n-1, k-1] + k*t[n-1, k] + k*(k+1)*t[n-1, k+1]; t[n_, n_] = 1; t[n_, k_] /; Not[1 <= k <= n] = 0; Table[t[n, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 22 2012, from given recurrence *)

{T(n,k)=if(n<1||k<1||k>n,0,if(n==k,1,T(n-1,k-1)+k*T(n-1,k)+k*(k+1)*T(n-1,k+1)))}

{T(n,k)=round(n!*polcoeff(polcoeff(exp(y*(-1/2+sqrt(3)/2*tan(sqrt(3)/2*x+Pi/6+x*O(x^n)))+y*O(y^k)),n,x),k,y))}

# uses[bell_matrix from A264428]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A080635(n+1), 10) # Peter Luschny, Jan 18 2016

TABLE ENTRIES
(1)... T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*P(n,j),
where P(n,x) are the polynomials described in A185415.
Compare (1) with the formula for the Stirling numbers of the second kind
(2)... Stirling2(n,k) = 1/k!*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*j^n.
RECURRENCE RELATION
(3)... T(n+1,k) = T(n,k-1) + k*T(n,k) + k*(k+1)*T(n,k+1).
GENERATING FUNCTION
Let E(t) = 1/2 + sqrt(3)/2*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635.
The e.g.f. for the present triangle is
(4)... exp{x*(E(t)-1)} = Sum_{n>=0} R(n,x)*t^n/n!
= 1 + x*t + (x+x^2)*t^2/2! + (3*x+3*x^2+x^3)*t^3/3! + ....
ROW POLYNOMIALS
The row generating polynomials R(n,x) satisfy the recurrence
(5)... R(n+1,x) = x*{R(n,x)+R'(n,x)+R''(n,x)},
where the prime ' indicates differentiation with respect to x.
RELATIONS WITH OTHER SEQUENCES
Column 1 is A080635.
k!*T(n,k) counts ordered forests A185423(n,k).
The row polynomials R(n,x) are given by D^n(exp(x*t)) evaluated at t = 0, where D is the operator (1+t+t^2)*d/dt. Cf. A147315 and A008297. - Peter Bala, Nov 25 2011

A185423 Ordered forests of k increasing plane unary-binary trees with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 6, 9, 30, 36, 24, 39, 150, 270, 240, 120, 189, 918, 1980, 2520, 1800, 720, 1107, 6174, 16254, 25200, 25200, 15120, 5040, 7281, 47070, 142884, 266616, 327600, 272160, 141120, 40320, 54351, 394470, 1369710, 2948400, 4331880

Offset: 1

Peter Bala, Jan 28 2011

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.

			Triangle begins
n\k|....1......2......3......4......5......6......7
===================================================
..1|....1
..2|....1......2
..3|....3......6......6
..4|....9.....30.....36.....24
..5|...39....150....270....240....120
..6|..189....918...1980...2520...1800....720
..7|.1107...6174..16254..25200..25200..15120...5040
..
Examples of recurrence relation:
T(5,3) = 270 = 3*(T(4,2) + T(4,3) + T(4,4)) = 3*(30+36+24);
T(6,1) = 1*(T(5,0) + T(5,1) + T(5,2)) = 39+150.
Examples of ordered forests:
T(4,2) = 30. The 15 unordered forests consisting of two plane increasing unary-binary trees on 4 nodes are shown below. We can order the trees in a forest in two ways giving rise to 30 ordered forests.
......... ......... ...3.....
.2...3... .3...2... ...|.....
..\./.... ..\./.... ...2.....
...1...4. ...1...4. ...|.....
......... ......... ...1...4.
.
......... ......... ...4.....
.2...4... .4...2... ...|.....
..\./.... ..\./.... ...2.....
...1...3. ...1...3. ...|.....
......... ......... ...1...3.
.
......... ......... ...4.....
.3...4... .4...3... ...|.....
..\./.... ..\./.... ...3.....
...1...2. ...1...2. ...|.....
......... ......... ...1...2.
.
......... ......... ...4.....
.3...4... .4...3... ...|.....
..\./.... ..\./.... ...3.....
...2...1. ...2...1. ...|.....
......... ......... ...2...1.
.
......... ......... ..........
..2..4... ..3..4... ..4...3...
..|..|... ..|..|... ..|...|...
..1..3... ..1..2... ..1...2...
......... ......... ..........

Cf. A019538, A080635, A185421, A185422.

#A185423
P := proc(n,x)
description 'polynomial sequence P(n,x) A185415'
if n = 0 return 1
else
return x*(P(n-1,x-1)-P(n-1,x)+P(n-1,x+1))
end proc:
with combinat:
T:=(n,k) -> add ((-1)^(k-j)*binomial(k,j)*P(n,j),j = 0..k):
for n from 1 to 10 do
seq(T(n,k),k = 1..n);
end do;

{T(n,k)=if(n<1||k<1||k>n,0,if(n==1,if(k==1,1,0),k*(T(n-1,k-1)+T(n-1,k)+T(n-1,k+1))))}

TABLE ENTRIES
(1)... T(n,k) = Sum_{j = 0..k} (-1)^j*binomial(k,j)*P(n,j),
where P(n,x) are the polynomials described in A185415.
Compare (1) with the formula for the number of ordered set partitions
(2)... A019538(n,k) = Sum_{j = 0..k} (-1)^j*binomial(k,j)*j^n.
RECURRENCE RELATION
(3)... T(n+1,k) = k*(T(n,k-1) + T(n,k) + T(n,k+1))
GENERATING FUNCTION
Let E(t) = 1/2 + (sqrt(3)/2)*tan(sqrt(3)/2*t + Pi/6) be the e.g.f. for A080635.
The e.g.f. for the present triangle is
(4)... 1/(1 + x*(1 - E(t))) = Sum {n >= 0} R(n,x)*t^n/n!
= 1 + x*t + (x + 2*x^2)*t^2/2! + (3*x + 6*x^2 + 6*x^3)*t^3/3! + ....
ROW POLYNOMIALS
The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by
(5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.
By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity
(6)... (-i*sqrt(3))^(n-1)*OB(n,x)/x = R(n,y)/y,
where i = sqrt(-1) and x = (sqrt(3)*i/3)*y + (-1/2+sqrt(3)*i/6).
RELATIONS WITH OTHER SEQUENCES
Column 1: A080635.
A185422(n,k) = T(n,k)/k!.
Setting y = 0 in (6) gives
(7)... A080635(n) = (-i*sqrt(3))^(n-1)*Sum_{k=1..n} k!*Stirling2(n,k) * (-1/2+sqrt(3)*i/6)^(k-1).
The row polynomials have their zeros on the vertical line Re(z) = -1/2 in the complex plane (this follows from the above connection with the ordered Bell polynomials, which have negative real zeros). - Peter Bala, Oct 23 2023

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Original entry on oeis.org

1, 1, 1, 2, 1, 8, 1, 22, 16, 1, 52, 136, 1, 114, 720, 272, 1, 240, 3072, 3968, 1, 494, 11616, 34304, 7936, 1, 1004, 40776, 230144, 176896, 1, 2026, 136384, 1328336, 2265344, 353792, 1, 4072, 441568, 6949952, 21953408, 11184128, 1, 8166, 1398000, 33981760

Offset: 1

Don Knuth, Jan 28 2005

Row n has ceiling(n/2) terms.
The paper by Shapiro et al. explains why T(n,k) is the number of permutations of n elements having k peaks and with the further property that every rise (ascent) is immediately followed by a peak. [That is, the permutation p_1 ... p_n has the further property that (j > 1 and p_{j-1} < p_j) implies (j < n and p_j > p_{j+1}).] For example, the T(4,1)=8 permutations in the case n=4, k=1 are 1423, 2143, 2431, 3142, 3241, 3421, 4231, 4132.
A more elegant way to state this property: T(n,k) is the number of permutations of n objects with k descents such that every descent is a peak. The eight examples for n=4 and k=1 are now 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
The rows of this triangle are the gamma vectors of the n-dimensional (type A) permutohedra (Postnikov et al., p. 31). Cf. A055151 and A089627. - Peter Bala, Oct 28 2008

			Triangle begins:
  1;
  1,
  1,   2;
  1,   8,
  1,  22,  16;
  1,  52, 136,
  1, 114, 720, 272;
  ...
From _Peter Bala_, Jun 26 2012: (Start)
n = 4: the 9 weighted plane increasing 0-1-2 trees on 4 vertices are
..................................................................
..4...............................................................
..|...............................................................
..3..........4...4...............4...4...............3...3........
..|........./.....\............./.....\............./.....\.......
..2....2...3.......3...2...3...2.......2...3...4...2.......2...4..
..|.....\./.........\./.....\./.........\./.....\./.........\./...
..1...(t)1........(t)1....(t)1........(t)1....(t)1........(t)1....
..................................................................
..3...4...4...3...................................................
...\./.....\./....................................................
.(t)2....(t)2.....................................................
....|.......|.....................................................
....1.......1.....................................................
Hence R(4,t) = 1 + 8*t.
(End)

D. Foata and V. Strehl, "Euler numbers and variations of permutations", in Colloquio Internazionale sulle Teorie Combinatorie, Rome, September 1973, (Atti dei Convegni Lincei 17, Rome, 1976), 129.
Guoniu Han, Frédéric Jouhet, Jiang Zeng, Two new triangles of q-integers via q-Eulerian polynomials of type A and B, Ramanujan J (2013) 31:115-127, DOI 10.1007/s11139-012-9389-3
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 4.

Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
François Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Leonard Carlitz and Richard Scoville, Generalized Eulerian numbers: combinatorial applications, Journal für die reine und angewandte Mathematik 265 (1974), 111.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Dominique Foata and Marcel-Paul Schützenberger, Théorie géometrique des polynômes eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math. 138 (1970), 81-83.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of descent polynomials and the change of grammars, arXiv:1802.02861 [math.CO], 2018.
Shi-Mei Ma, Jianfeng Wang, Guiying Yan, Jean Yeh, and Yeong-Nan Yeh, Symmetric decompositions and Euler-Stirling statistics on Stirling permutations, arXiv:2507.17667 [math.CO], 2025. See p. 5.
Shi-Mei Ma and Yeong-Nan Yeh, The alternating run polynomials of permutations, arXiv:1904.11437 [math.CO], 2019. See p. 4.
Alexander Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007. [_Peter Bala_, Oct 28 2008]
Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
Andrei K. Svinin, Somos-4 equation and related equations, arXiv:2307.05866 [math.CA], 2023. See p. 16.

The numbers 2^{n-1-k} T(n, k) form the array shown in A008303.
Cf. A055151, A089627. - Peter Bala, Oct 28 2008
Cf. A008292, A094503, A080635 (row sums).

T:=proc(n,k) if k<0 then 0 elif n=1 and k=0 then 1 elif k>floor((n-1)/2) then 0 else (k+1)*T(n-1,k)+(2*n-4*k)*T(n-1,k-1) fi end: for n from 1 to 13 do seq(T(n,k),k=0..floor((n-1)/2)) od; # yields sequence in triangular form # Emeric Deutsch, Aug 06 2005

t[, k?Negative] = 0; t[1, 0] = 1; t[n_, k_] /; k > (n-1)/2 = 0; t[n_, k_] := t[n, k] = (k+1)*t[n-1, k] + (2*n-4*k)*t[n-1, k-1]; Table[t[n, k], {n, 1, 13}, {k, 0, (n-1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012 *)

G.f.: Sum_{n>=1, k>=0} T(n, k) t^k z^n/n! = C(t)(2-C(t))/(exp^(-z sqrt(1-4t)) + 1 - C(t)) - C(t), where the sum on k is actually finite, running up to ceiling(n/2) - 1; here C(t) = (1 - sqrt(1-4t))/2t is the generating function for the Catalan numbers (A000108).
Sum_{k} Eulerian(n, k) x^k = Sum_{k} T(n, k) x^k (1+x)^(n-1-2k). E.g., 1 + 11x + 11x^2 + x^3 = (1+x)^3 + 8x(1+x).
From Peter Bala, Jun 26 2012: (Start)
T(n,k) = 2^k*A094503(n,k+1).
Let r(t) = sqrt(1 - 2*t) and w(t) = (1 - r(t))/(1 + r(t)). Define F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ...; F(t,z) is the e.g.f. for A094503. The e.g.f. for the present table is A(t,z) := (F(2*t,z) - 1)/(2*t) = z + z^2/2! + (1+2*t)*z^3/3! + (1+8*t)*z^4/4! + ....
The e.g.f. A(t,z) satisfies the autonomous partial differential equation dA/dz = 1 + A + t*A^2 with A(t,0) = 0. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = int {x = 0..z} 1/(1+x+t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the row polynomial R(n,t) is the generating function for rooted plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
Row sums A080635.
(End)

More terms from Emeric Deutsch, Aug 06 2005

A131178 Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.

Original entry on oeis.org

1, 2, 5, 16, 64, 308, 1730, 11104, 80176, 643232, 5676560, 54650176, 569980384, 6401959328, 77042282000, 988949446144, 13488013248256, 194780492544512, 2969094574403840, 47640794742439936, 802644553810683904, 14166772337295285248, 261410917571703825920

Offset: 1

Wenjin Woan, Oct 31 2007

A labeled tree of size n is a rooted tree on n nodes that are labeled by distinct integers from the set {1,...,n}. An increasing tree is a labeled tree such that the sequence of labels along any branch starting at the root is increasing. Thus the root of an increasing tree will be labeled 1. In unary binary trees (sometimes called 0-1-2 trees) the outdegree of a node is either 0, 1 or 2. Here we are counting non-plane (where the subtrees stemming from a node are not ordered between themselves) increasing unary binary trees where the nodes of outdegree 1 come in two colors. An example is given below. - Peter Bala, Sep 01 2011
The number of plane increasing 0-1-2 trees on n nodes, where the nodes of outdegree 1 come in two colors, is equal to n!. Other examples of sequences counting increasing trees include A000111, A000670, A008544, A008545, A029768 and A080635. - Peter Bala, Sep 01 2011
Number of plane increasing 0-1-2 trees, where the nodes of outdegree 1 come in 2 colors, avoiding pattern T213. See A278679 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016

			G.f. = x + 2*x^2 + 5*x^3 + 16*x^4 + 64*x^5 + 308*x^6 + 1730*x^7 + 11104*x^8 + ...
a(3) = 5: Denoting the two types of node of outdegree 1 by the letters a or b, the 5 possible trees are
.
.  1a    1b    1a    1b      1
.  |     |     |     |      / \
.  2a    2b    2b    2a    2   3
.  |     |     |     |
.  3     3     3     3
- _Peter Bala_, Sep 01 2011

Vincenzo Librandi, Table of n, a(n) for n = 1..100
Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki, Patterns in treeshelves, arXiv:1611.07793 [cs.DM], 2016.
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Lapo Cioni, Luca Ferrari, and Corentin Henriet. A direct bijection between two-stack sortable permutations and fighting fish, Euro. Conf. Comb., Graph Theory Appl. (2023) No. 12, 283-289.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.

Cf. A000111, A000670, A008544, A008545, A029768, A080635, A278679

E:=  (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)):
S:= map(simplify,series(E,x,101)):
seq(coeff(S,x,j)*j!, j=1..100); # Robert Israel, Nov 23 2016

max = 25; f[x_] := (2*(Exp[Sqrt[2]*x] - 1))/((2 + Sqrt[2]) - (2 - Sqrt[2])*Exp[Sqrt[2]*x]); Drop[ Simplify[ CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]!], 1] (* Jean-François Alcover, Oct 05 2011 *)

x='x+O('x^66); /* that many terms */
default(realprecision,1000); /* working with floats here */
egf=(2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x));
round(Vec(serlaplace(egf))) /* show terms */
/* Joerg Arndt, Sep 01 2011 */

/* the following program should be preferred. */
Vec( serlaplace( serreverse( intformal( 1/(1+2*x+1/2*x^2) + O(x^66) ) ) ) )
\\ Joerg Arndt, Mar 01 2014

{a(n) = if( n<1, 0, n! * polcoeff( 2 / (-2 + quadgen(8) * (-1 + 2 / (1 - exp(-quadgen(8) * x + x * O(x^n))))), n))};

E.g.f.: A(x) = (2*(exp(sqrt(2)*x)-1)) / ((2+sqrt(2))-(2-sqrt(2))*exp(sqrt(2)*x)) = x+2*x^2/2!+5*x^3/3!+16*x^4/4!+64*x^5/5!+....
From Peter Bala, Sep 01 2011: (Start)
The generating function A(x) satisfies the autonomous differential equation A' = 1+2*A+1/2*A^2 with A(0) = 0. It follows that the inverse function A(x)^-1 may be expressed as an integral A(x)^-1 = int {t = 0..x} 1/(1+2*t+1/2*t^2).
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the terms of the sequence: let f(x) = 1+2*x+1/2*x^2. Let D be the operator f(x)*d/dx. Then a(n) = D^n(f(x)) evaluated at x = 0. Compare with A000111(n+1) = D^n(1+x+x^2/2!) evaluated at x = 0.
(End)
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(2*k+1) - m*x^2*(k+1)*(2*k+1)/( 1 - 2*x*(2*k+2) - m*x^2*(k+1)*(2*k+3)/Q(k+1) ) and m=1; (continued fraction). - Sergei N. Gladkovskii, Sep 24 2013
G.f.: 1/Q(0), where Q(k) = 1 - 2*x*(k+1) - 1/2*x^2*(k+1)*(k+2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2013
a(n) ~ n! * 2^((n+3)/2) / log(3+2*sqrt(2))^(n+1). - Vaclav Kotesovec, Oct 08 2013
G.f.: conjecture: T(0)/(1-2*x) -1, where T(k) = 1 - x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2) - 2*(1-2*x*(k+1))*(1-2*x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 19 2013
E.g.f.: x/(T(0)-x), where T(k) = 4*k + 1 + x^2/(8*k+6 + x^2/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2013

Terms >= 80176 from Peter Bala, Sep 01 2011

Changed offset to 1 to agree with name and example. - Michael Somos, Nov 23 2016

A162976 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k double descents and initial descents (n>=0; 0<=k<=max(0,n-1)) [we say that i is a doubledescent of a permutation p if p(i) > p(i+1) > p(i+2); we say that a permutation p has an initial descent if p(1) > p(2)].

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 9, 11, 3, 1, 39, 48, 28, 4, 1, 189, 297, 166, 62, 5, 1, 1107, 1902, 1419, 476, 129, 6, 1, 7281, 14391, 11637, 5507, 1235, 261, 7, 1, 54351, 118044, 111438, 56400, 19096, 3020, 522, 8, 1, 448821, 1078245, 1119312, 673128, 239146, 61986

Offset: 0

Emeric Deutsch, Jul 26 2009

Sum of entries in row n is n! = A000142(n).

T(n,0) = A080635(n).

			T(4,2) = 3 because each of the permutations 4312, 4213, and 3214 has one doubledescent and one initial descent.
Triangle starts:
:   1;
:   1;
:   1,   1;
:   3,   2,   1;
:   9,  11,   3,  1;
:  39,  48,  28,  4, 1;
: 189, 297, 166, 62, 5, 1;

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983 (p. 195).

Alois P. Heinz, Rows n = 0..141, flattened
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint, 2015.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.

Cf. A000142, A080635, A162975.

eq := s^2-(t+1)*s+1 = 0: sol := solve(eq, s): a := sol[1]: b := sol[2]: G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): P[0]:=1: for n to 11 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n from 0 to 11 do seq(coeff(P[n], t, j), j = 0 .. max(0,n-1)) end do;
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, 1), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=2, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(0, n, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Dec 09 2016

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[u-j, o+j-1, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, 2]*If[t == 2, x, 1], {j, 1, o}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}] ][b[0, n, 1]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Dec 22 2016, after Alois P. Heinz *)

E.g.f.: G(t,z) = [exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=1+t and ab=1.

One term for row n=0 prepended by Alois P. Heinz, Dec 09 2016

A332776 a(n) = 1 + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k-1).

Original entry on oeis.org

1, 1, 2, 5, 18, 83, 464, 3041, 22810, 192595, 1807328, 18658097, 210138882, 2563990859, 33691089824, 474327797585, 7123141539610, 113656386574099, 1920170741071280, 34242622099969217, 642792206343361602, 12669617513914228907, 261613287097165614224, 5647565141926833774977

Offset: 0

Ilya Gutkovskiy, Jun 08 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..454

Cf. A000110, A006677, A007317, A080635, A105633, A186021.

a[n_] := a[n] = 1 + Sum[Binomial[n - 1, k] a[k] a[n - k - 1], {k, 1, n - 1}]; Table[a[n], {n, 0, 23}]
terms = 23; A[] = 0; Do[A[x] = Normal[Integrate[Exp[x] + A[x] (A[x] - 1), x] + O[x]^(terms + 1)], terms]; CoefficientList[A[x], x] Range[0, terms]!

E.g.f. A(x) satisfies: d/dx A(x) = exp(x) + A(x) * (A(x) - 1).
From Vaclav Kotesovec, Jun 09 2020: (Start)
E.g.f.: exp(x/2) * (BesselJ(2, 2*exp(x/2)) * BesselY(0,2) - BesselJ(0,2) * BesselY(2, 2*exp(x/2))) / (BesselJ(1, 2*exp(x/2)) * BesselY(0,2) - BesselJ(0,2) * BesselY(1, 2*exp(x/2))).
a(n) ~ n! / r^(n+1), where r = 1.0654335847261788612657252860730850911833168584... is the smallest real root of the equation BesselJ(1, 2*exp(r/2)) * BesselY(0,2) = BesselJ(0,2) * BesselY(1, 2*exp(r/2)). (End)

A194770 E.g.f. 2sqrt(3)/3arctan(sqrt(3)*x/(x+2)).

Original entry on oeis.org

1, -1, 0, 6, -24, 0, 720, -5040, 0, 362880, -3628800, 0, 479001600, -6227020800, 0, 1307674368000, -20922789888000, 0, 6402373705728000, -121645100408832000, 0, 51090942171709440000, -1124000727777607680000

Offset: 1

Peter Bala, Sep 02 2011

A080635

With[{nn=30},Rest[CoefficientList[Series[2 Sqrt[3]/3 ArcTan[Sqrt[ 3] x/(x+2)],{x,0,nn}],x] Range[0,nn-1]!]] (* Harvey P. Dale, May 13 2019 *)

a(3*n+1) = (3*n)!, a(3*n+2) = -(3*n+1)!, a(3*n) = 0.
E.g.f.: A(x) = 2*sqrt(3)/3*arctan(sqrt(3)*x/(x+2)) = x-x^2/2!+6*x^4/4!-24*x^5/5!+720*x^7/7!-....
The derivative A'(x) = 1/(1+x+x^2). The inverse function A^-1(x) = 2/sqrt(3)*tan(sqrt(3)/2*x)/(1-1/sqrt(3)*tan(sqrt(3)/2*x)) is the generating function for A080635 (apart from the initial term).
D-finite with recurrence: a(n) +(n-1)*a(n-1) +(n-1)*(n-2)*a(n-2)=0. - R. J. Mathar, Jan 25 2020

A230008 E.g.f. A(x) satisfies: A'(x) = -1 + A(x) + A(x)^2.

Original entry on oeis.org

1, 1, 3, 11, 51, 295, 2055, 16715, 155355, 1624255, 18868575, 241112675, 3361168275, 50760093175, 825541973175, 14385306834875, 267379330468875, 5280383597275375, 110414649582951375, 2437075699774353875, 56622329782817431875, 1381324610464997374375, 35302637257323023454375

Offset: 0

Paul D. Hanna, Dec 19 2013

nonn

Counts binary free multilabeled increasing trees with m labels. - Markus Kuba, Nov 19 2014

			G.f. = 1 + x + 3*x^2 + 11*x^3 + 51*x^4 + 295*x^5 + 2055*x^6 + 16715*x^7 + ...
E.g.f.: A(x) = 1 + x + 3*x^2/2! + 11*x^3/3! + 51*x^4/4! + 295*x^5/5! +...
where A(x)^2 = 1 + 2*x + 8*x^2/2! + 40*x^3/3! + 244*x^4/4! + 1760*x^5/5! +...
also log(A(x)) = x + 2*x^2/2! + 4*x^3/3! + 10*x^4/4! + 44*x^5/5! + 290*x^6/6! +...
and 1/A(x) = 1 - x - x^2/2! + x^3/3! + 7*x^4/4! + 5*x^5/5! - 85*x^6/6! +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..200
Veronica Bitonti, Bishal Deb, and Alan D. Sokal, Thron-type continued fractions (T-fractions) for some classes of increasing trees, arXiv:2412.10214 [math.CO], 2024. See pp. 5, 20, 57.
Markus Kuba, Alois Panholzer, Combinatorial families of multilabelled increasing trees and hook-length formulas, arXiv:1411.4587 [math.CO], (17-November-2014); see p. 29

Cf. A080635.

FullSimplify[CoefficientList[Series[(2*(Sqrt[5] - 2)*E^(Sqrt[5]*x) + Sqrt[5] - 1)/((3*Sqrt[5] - 7)*E^(Sqrt[5]*x) + 2), {x, 0, 15}], x] * Range[0, 15]!] (* Vaclav Kotesovec, Dec 20 2013 *)
FullSimplify[Flatten[{1, Table[5^((n+1)/2)*PolyLog[-n,(7-3*Sqrt[5])/2], {n, 1, 20}]}]] (* Vaclav Kotesovec, Nov 19 2014 after Markus Kuba *)

{a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=exp(x+intformal(A-1/A+x*O(x^n)))); n!*polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", "))

{a(n)=local(A,X=x+x*O(x^n)); A=exp(serreverse(intformal(1/(1+2*sinh(X))))); n!*polcoeff(A, n)}
for(n=0, 30, print1(a(n), ", "))

{a(n)=local(A=1+serreverse(intformal(1/(1+3*x+x^2 +x*O(x^n))))); n!*polcoeff(A,n)}
for(n=0,25,print1(a(n),", "))

E.g.f. A(x) satisfies:
(1) A(x) = 1 + Series_Reversion( Integral 1/(1 + 3*x + x^2) dx ).
(2) A(x) = exp(x + Integral A(x) - 1/A(x) dx).
(3) log(A(x)) = Series_Reversion( Integral 1/(1+2*sinh(x)) dx ).
(4) log(A(x)) = Series_Reversion( log( (sqrt(5)+2) * (Phi*exp(x) - 1)/(exp(x) + Phi) ) / sqrt(5) ) where Phi = (sqrt(5)+1)/2.
O.g.f.: 1 + x/(1-3*x - 1*2*x^2/(1-6*x - 2*3*x^2/(1-9*x - 3*4*x^2/(1-12*x - 4*5*x^2/(1-15*x - 5*6*x^2/(1- .../(1-3*n*x - n*(n+1)*x^2/(1- ...))))))) (continued fraction).
E.g.f.: A(x) = (2*(sqrt(5) - 2)*exp(sqrt(5)*x) + sqrt(5) - 1)/((3*sqrt(5) - 7)*exp(sqrt(5)*x) + 2). - Vaclav Kotesovec, Dec 20 2013
a(n) ~ n! * 5^((n+1)/2)/(arccosh(7/2))^(n+1). - Vaclav Kotesovec, Dec 20 2013
For n>=1: a(n) = 5^((n+1)/2) * sum(k>=1, k^n *((7-3*sqrt(5))/2)^k ). - Markus Kuba, Nov 19 2014
a(0) = a(1) = 1; a(n) = a(n-1) + Sum_{k=0..n-1} binomial(n-1,k) * a(k) * a(n-k-1). - Ilya Gutkovskiy, Jul 05 2020

A232864 Number of permutations of n elements not cyclically containing the consecutive pattern 123.

Original entry on oeis.org

1, 1, 2, 3, 12, 45, 234, 1323, 8856, 65529, 543510, 4937031, 49030596, 526930677, 6101871426, 75686176035, 1001517264432, 14079895613937, 209594037600558, 3293305758743679, 54470994630103260, 945988795762018029, 17211193919411902938, 327371367293394753627

Offset: 0

Richard Ehrenborg, Dec 01 2013

nonn

			a(4) = 12 comes from the 3 permutations 1324, 1423 and 1432, and by cyclically shifting we obtain 3 * 4 = 12 permutations.

Alois P. Heinz, Table of n, a(n) for n = 0..200
R. Ehrenborg, Cyclically consecutive permutation avoidance, arXiv:1312.2051 [math.CO], 2013.

Cf. A049774, A080635.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 1), j=1..u))
    end:
a:= n-> `if`(n=0, 1, n*b(0, n-1, 1)):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 01 2013

b[u_,o_,t_] := b[u, o, t] = If[u+o==0, 1, If[t<2, Sum[b[u+j-1, o-j, t+1], {j, 1, o}], 0] + Sum[b[u-j, o+j-1, 1], {j, 1, u}]];
a[n_]:= If[n==0, 1, n*b[0, n-1, 1]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 14 2017, after Alois P. Heinz *)

a(n) = n! * Sum_{k=-oo..oo} (sqrt(3)/(2*Pi*(k+1/3)))^n for n >= 2.

a(n) = A080635(n-1)*n for n>0. - Alois P. Heinz, Dec 01 2013

A335441 a(n) = 1 + Sum_{k=1..n-1} binomial(n-2,k-1) * a(k) * a(n-k-1).

Original entry on oeis.org

1, 1, 2, 4, 11, 40, 176, 907, 5360, 35668, 263789, 2146390, 19054040, 183248581, 1897952690, 21061861828, 249309196559, 3135518918800, 41754612283244, 586922460056851, 8684272948653068, 134919751191875572, 2195942678525060093, 37365571515146318650

Offset: 0

Ilya Gutkovskiy, Jun 10 2020

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..470

Cf. A000111, A006677, A052886, A054687, A080635, A332776.

a[n_] := a[n] = 1 + Sum[Binomial[n - 2, k - 1] a[k] a[n - k - 1], {k, 1, n - 1}]; Table[a[n], {n, 0, 23}]
terms = 23; A[] = 0; Do[A[x] = Normal[Integrate[Integrate[Exp[x] + A[x] D[A[x], x], x], x] + O[x]^(terms + 1)], terms]; CoefficientList[A[x], x] Range[0, terms]!

E.g.f. A(x) satisfies: A''(x) = exp(x) + A(x) * A'(x).
From Vaclav Kotesovec, Jun 11 2020: (Start)
E.g.f.: (BesselY(0, sqrt(2))*(BesselJ(1, sqrt(2)*exp(x/2)) - sqrt(2)*exp(x/2)*BesselJ(0, sqrt(2)*exp(x/2))) + BesselJ(0, sqrt(2))*(sqrt(2)*exp(x/2)*BesselY(0, sqrt(2)*exp(x/2)) - BesselY(1, sqrt(2)*exp(x/2)))) / (BesselJ(1, sqrt(2)*exp(x/2))*BesselY(0, sqrt(2)) - BesselJ(0, sqrt(2))*BesselY(1, sqrt(2)*exp(x/2))).
a(n) ~ 2 * n! / r^(n+1), where r = 1.35169030867903432729790416904526340210784862703704233748118252928787... is the smallest real root of the equation BesselY(0, sqrt(2))*BesselJ(1, sqrt(2)*exp(r/2)) = BesselJ(0, sqrt(2))*BesselY(1, sqrt(2)*exp(r/2)). (End)

cp's OEIS Frontend

A185422 Forests of k increasing plane unary-binary trees on n nodes. Generalized Stirling numbers of the second kind associated with A185415.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A185423 Ordered forests of k increasing plane unary-binary trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Formula

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A131178 Non-plane increasing unary binary (0-1-2) trees where the nodes of outdegree 1 come in 2 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A332776 a(n) = 1 + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A194770 E.g.f. 2sqrt(3)/3arctan(sqrt(3)*x/(x+2)).