A006595 a(n) = (n+2)!/4 + n!/2. (Formerly M1794)

1, 2, 7, 33, 192, 1320, 10440, 93240, 927360, 10160640, 121564800, 1576713600, 22034073600, 330032102400, 5274286617600, 89575694208000, 1611054821376000, 30589118816256000, 611426688897024000, 12833558093131776000, 282216632948490240000

Offset

0,2

Comments

A non-plane recursive tree is a rooted labeled plane tree (the children of a node are not ordered) with the property that the labels increase along any path from the root to a leaf. a(n) is the total number of vertices of outdegree 1 among the set of n! non-plane recursive trees on n+1 vertices. An example is given below. - Peter Bala, Jul 08 2012

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Dan Daly and Lara Pudwell, Pattern avoidance in rook monoids, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013. - From N. J. A. Sloane, Feb 03 2013

Rui-Li Liu and Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.

J. R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285-1332.

Formula

E.g.f.: 1/2*(x^2-2*x+2)/(1-x)^3. - Peter Bala, Jul 08 2012

a(n) +(-n-2)*a(n-1) +2*a(n-2) +2*(-n+2)*a(n-3)=0. - R. J. Mathar, May 30 2014

Example

a(3) = 7. There are 3! = 6 non-plane recursive trees on 4 nodes shown below. The total number of nodes of outdegree 1 is 3+1+1+1+1+0 = 7.
.0o......0o..........0o..........0o.........0o...........0o......
..|.......|........../.\........./.\......../.\........../|\.....
..|.......|........./...\......./...\....../...\......../.|.\....
.1o......1o.......1o.....o3...1o....o2...2o.....o1...../..|..\...
..|....../.\.......|...........|..........|..........1o..2o...o3.
..|...../...\......|...........|..........|......................
.2o...2o.....o3...2o..........3o.........3o......................
..|..............................................................
..|..............................................................
.3o..............................................................
.................................................................

Mathematica

Table[(n + 2)! / 4 + n! / 2, {n, 0, 30}] (* Vincenzo Librandi, Aug 26 2016 *)

Prog

(PARI) a(n) = (n+2)!/4 + n!/2; \\ Michel Marcus, Aug 04 2013
(Magma) [Factorial(n+2)/4+Factorial(n)/2: n in [0..25]]; // Vincenzo Librandi, Aug 26 2016

Crossrefs

A diagonal of A059418.

Sequence in context: A058797 A121965 A337058 * A179525 A217033 A059099

Adjacent sequences: A006592 A006593 A006594 * A006596 A006597 A006598

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Improved description and sequence extended by N. J. A. Sloane, Aug 15 1995

Status

approved