cp's OEIS Frontend

A000958 Number of ordered rooted trees with n edges having root of odd degree.

%I A000958 M2748 N1104 #144 Dec 12 2024 10:56:12
%S A000958 1,1,3,8,24,75,243,808,2742,9458,33062,116868,417022,1500159,5434563,
%T A000958 19808976,72596742,267343374,988779258,3671302176,13679542632,
%U A000958 51134644014,191703766638,720629997168,2715610275804,10256844598900,38822029694628,147229736485868
%N A000958 Number of ordered rooted trees with n edges having root of odd degree.
%C A000958 a(n) is the number of Dyck n-paths containing no peak at height 2 before the first return to ground level. Example: a(3)=3 counts UUUDDD, UDUUDD, UDUDUD. - _David Callan_, Jun 07 2006
%C A000958 Also number of order trees with n edges and having no even-length branches starting at the root. - _Emeric Deutsch_, Mar 02 2007
%C A000958 Convolution of the Catalan sequence 1,1,2,5,14,42,... (A000108) and the Fine sequence 1,0,1,2,6,18,... (A000957). a(n) = A127541(n,0). - _Emeric Deutsch_, Mar 02 2007
%C A000958 The Catalan transform of A008619. - _R. J. Mathar_, Nov 06 2008
%C A000958 Hankel transform is F(2n+1). - _Paul Barry_, Dec 01 2008
%C A000958 Starting with offset 2 = iterates of M * [1,1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - _Gary W. Adamson_, Jan 09 2009
%C A000958 Equals INVERT transform of A032357. - _Gary W. Adamson_, Apr 10 2009
%C A000958 a(n) is the number of Dyck paths of semilength n+1 that have equal length inclines incident with the first return to ground level. For example, for UUDDUUDDUD these inclines are DD and UU (steps 3 through 6), and a(3)=3 counts UDUDUUDD, UDUDUDUD, UUDDUUDD. - _David Callan_, Aug 23 2011
%C A000958 a(n) is the number of imprimitive Dyck paths of semilength n+1 for which the heights of the first and the last peaks coincide, this gives the connection to A193215. - _Volodymyr Mazorchuk_, Aug 27 2011
%C A000958 a(n) is the number of parking functions of size n-1 avoiding the patterns 123 and 132. - _Lara Pudwell_, Apr 10 2023
%C A000958 a(n) is the number of Dyck paths of semilength n that contain no UDUs at ground level. For example, a(3) = 3 counts UUUDDD, UUDUDD, UUDDUD. - _David Callan_, Feb 02 2024
%D A000958 Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013) - _N. J. A. Sloane_, Jun 05 2012
%D A000958 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000958 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000958 Alois P. Heinz, <a href="/A000958/b000958.txt">Table of n, a(n) for n = 1..1000</a> (first 200 terms from T. D. Noe)
%H A000958 Ayomikun Adeniran and Lara Pudwell, <a href="https://doi.org/10.54550/ECA2023V3S3R17">Pattern avoidance in parking functions</a>, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
%H A000958 Paul Barry, <a href="https://arxiv.org/abs/2307.00098">Moment sequences, transformations, and Spidernet graphs</a>, arXiv:2307.00098 [math.CO], 2023.
%H A000958 Paul Barry, <a href="https://arxiv.org/abs/2412.05461">The Triple Riordan Group</a>, arXiv:2412.05461 [math.CO], 2024. See pp. 6, 10.
%H A000958 Dennis E. Davenport, Louis W. Shapiro, and Leon C. Woodson, <a href="http://math.colgate.edu/~integers/u8/u8.Abstract.html">A bijection between the triangulations of convex polygons and ordered trees</a>, Integers (2020) Vol. 20, Article #A8.
%H A000958 Emeric Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.
%H A000958 Sergio Falcon, <a href="http://www.mathnet.or.kr/mathnet/thesis_file/CKMS-28-4-827-832.pdf">Catalan transform of the K-Fibonacci sequence</a>, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
%H A000958 T. Fine, <a href="http://dx.doi.org/10.1016/S0019-9958(70)90177-4">Extrapolation when very little is known about the source</a>, Information and Control 16 (1970), 331-359.
%H A000958 D. G. Rogers, <a href="http://dx.doi.org/10.1016/0097-3165(77)90082-6">Similarity relations on finite ordered sets</a>, J. Combin. Theory, A 23 (1977), 88-98. Erratum, loc. cit., 25 (1978), 95-96.
%H A000958 Yidong Sun, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.002">The statistic "number of udu's" in Dyck paths</a>, Discrete Math., 287 (2004), 177-186. See Table 2.
%H A000958 Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.
%H A000958 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A000958 a(n) = A000957(n) + A000957(n+1).
%F A000958 G.f.: (1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2)). - _Paul Barry_, Jan 26 2007
%F A000958 G.f.: z*C/(1-z^2*C^2), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function. - _Emeric Deutsch_, Mar 02 2007
%F A000958 a(n+1) = Sum_{k=0..floor(n/2)} A039599(n-k,k). - _Philippe Deléham_, Mar 13 2007
%F A000958 a(n) = (-1/2)^n*(-2 - 5*Sum_{k=1..n-1} (-8)^k*Gamma(1/2+k)*(4/5+k)/(sqrt(Pi)*Gamma(k+3))). - Mark van Hoeij, Nov 11 2009
%F A000958 a(n) + a(n+1) = A135339(n+1). - _Philippe Deléham_, Dec 02 2009
%F A000958 From _Gary W. Adamson_, Jul 14 2011: (Start)
%F A000958 a(n) = sum of top row terms in M^(n-1), where M = the following infinite square production matrix:
%F A000958   0, 1, 0, 0, 0, 0, ...
%F A000958   1, 1, 1, 0, 0, 0, ...
%F A000958   1, 1, 1, 1, 0, 0, ...
%F A000958   1, 1, 1, 1, 1, 0, ...
%F A000958   1, 1, 1, 1, 1, 1, ...
%F A000958   ... (End)
%F A000958 D-finite with recurrence 2*(n+1)*a(n) + (-5*n+3)*a(n-1) + (-11*n+21)*a(n-2) + 2 *(-2*n+5)*a(n-3) = 0. - _R. J. Mathar_, Dec 03 2012
%F A000958 a(n) ~ 5*4^n/(9*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Aug 09 2013
%F A000958 a(n) = Catalan(n-1)*h(n-1) for n>=2 where h(n) = hypergeom([1,3/2,-n/2,(1-n)/2],[1/2,-n,-n+1/2], 1). - _Peter Luschny_, Apr 25 2016
%p A000958 g:=(1-x-(1+x)*sqrt(1-4*x))/2/x/(x+2): gser:=series(g,x=0,30): seq(coeff(gser,x,n),n=1..26); # _Emeric Deutsch_, Mar 02 2007
%p A000958 A958 := n -> add(binomial(2*n-2*k-2, n-1)*(2*k+1)/n, k=0..floor((n-1)/2)): seq(A958(n), n=1..28); # _Johannes W. Meijer_, Jul 26 2013
%p A000958 A000958List := proc(m) local A, P, n; A := [1,1]; P := [1,1];
%p A000958 for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-2]]);
%p A000958 A := [op(A), P[-1]] od; A end: A000958List(28); # _Peter Luschny_, Mar 26 2022
%p A000958 # next Maple program:
%p A000958 b:= proc(n) option remember; `if`(n<3, n*(2-n),
%p A000958       ((7*n-12)*b(n-1)+(4*n-6)*b(n-2))/(2*n))
%p A000958     end:
%p A000958 a:= n-> b(n)+b(n+1):
%p A000958 seq(a(n), n=1..32);  # _Alois P. Heinz_, Apr 26 2023
%t A000958 nn = 30; Rest[CoefficientList[Series[(1-x-(1+x)*Sqrt[1-4*x])/(2*x*(x+2)), {x, 0, nn}], x]] (* _T. D. Noe_, May 09 2012 *)
%o A000958 (Python)
%o A000958 from itertools import accumulate
%o A000958 def A000958_list(size):
%o A000958     if size < 1: return []
%o A000958     L, accu = [], [1]
%o A000958     for n in range(size-1):
%o A000958         accu = list(accumulate(accu+[-accu[-1]]))
%o A000958         L.append(accu[n])
%o A000958     return L
%o A000958 print(A000958_list(29)) # _Peter Luschny_, Apr 25 2016
%o A000958 (Python)
%o A000958 from itertools import count, islice
%o A000958 def A000958_gen(): # generator of terms
%o A000958     yield 1
%o A000958     a, c = 0, 1
%o A000958     for n in count(1):
%o A000958         yield (c:=c*((n<<2)+2)//(n+2))+a>>1
%o A000958         a = c-a>>1
%o A000958 A000958_list = list(islice(A000958_gen(),20)) # _Chai Wah Wu_, Apr 26 2023
%o A000958 (PARI) my(x='x+O('x^30)); Vec((1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2))) \\ _G. C. Greubel_, Feb 27 2019
%o A000958 (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (1-x-(1+x)*Sqrt(1-4*x))/(2*x*(x+2)) )); // _G. C. Greubel_, Feb 27 2019
%o A000958 (Sage) a=((1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2))).series(x, 30).coefficients(x, sparse=False); a[1:] # _G. C. Greubel_, Feb 27 2019
%Y A000958 First column of A065602, A098747 and A362563. Row sums of A362563.
%Y A000958 Cf. A127541, A127539, A000108, A000957, A032357.
%Y A000958 Partial differences give A118973 (for n>=1).
%K A000958 nonn,easy
%O A000958 1,3
%A A000958 _N. J. A. Sloane_