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
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
Improved description and sequence extended by N. J. A. Sloane, Aug 15 1995
STATUS
approved