|
%I M1794 #36 Sep 08 2022 08:44:35
%S 1,2,7,33,192,1320,10440,93240,927360,10160640,121564800,1576713600,
%T 22034073600,330032102400,5274286617600,89575694208000,
%U 1611054821376000,30589118816256000,611426688897024000,12833558093131776000,282216632948490240000
%N a(n) = (n+2)!/4 + n!/2.
%C 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
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A006595/b006595.txt">Table of n, a(n) for n = 0..200</a>
%H Dan Daly and Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/sandiego2013.pdf">Pattern avoidance in rook monoids</a>, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013. - From _N. J. A. Sloane_, Feb 03 2013
%H Rui-Li Liu and Feng-Zhen Zhao, <a href="https://www.emis.de/journals/JIS/VOL21/Liu/liu19.html">New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
%H J. R. Stembridge, <a href="http://dx.doi.org/10.1090/S0002-9947-97-01805-9">Some combinatorial aspects of reduced words in finite Coxeter groups</a>, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285-1332.
%F E.g.f.: 1/2*(x^2-2*x+2)/(1-x)^3. - _Peter Bala_, Jul 08 2012
%F a(n) +(-n-2)*a(n-1) +2*a(n-2) +2*(-n+2)*a(n-3)=0. - _R. J. Mathar_, May 30 2014
%e 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.
%e .0o......0o..........0o..........0o.........0o...........0o......
%e ..|.......|........../.\........./.\......../.\........../|\.....
%e ..|.......|........./...\......./...\....../...\......../.|.\....
%e .1o......1o.......1o.....o3...1o....o2...2o.....o1...../..|..\...
%e ..|....../.\.......|...........|..........|..........1o..2o...o3.
%e ..|...../...\......|...........|..........|......................
%e .2o...2o.....o3...2o..........3o.........3o......................
%e ..|..............................................................
%e ..|..............................................................
%e .3o..............................................................
%e .................................................................
%t Table[(n + 2)! / 4 + n! / 2, {n, 0, 30}] (* _Vincenzo Librandi_, Aug 26 2016 *)
%o (PARI) a(n) = (n+2)!/4 + n!/2; \\ _Michel Marcus_, Aug 04 2013
%o (Magma) [Factorial(n+2)/4+Factorial(n)/2: n in [0..25]]; // _Vincenzo Librandi_, Aug 26 2016
%Y A diagonal of A059418.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_
%E Improved description and sequence extended by _N. J. A. Sloane_, Aug 15 1995
| 