login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000958 Number of ordered rooted trees with n edges having root of odd degree.
(Formerly M2748 N1104)
18
1, 1, 3, 8, 24, 75, 243, 808, 2742, 9458, 33062, 116868, 417022, 1500159, 5434563, 19808976, 72596742, 267343374, 988779258, 3671302176, 13679542632, 51134644014, 191703766638, 720629997168, 2715610275804, 10256844598900, 38822029694628, 147229736485868 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

a(n) = 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

Also number of order trees with n edges and having no even-length branches starting at the root. - Emeric Deutsch, Mar 02 2007

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

The Catalan transform of A008619. - R. J. Mathar, Nov 06 2008

Hankel transform is F(2n+1). - Paul Barry, Dec 01 2008

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

Equals INVERT transform of A032357. - Gary W. Adamson, Apr 10 2009

a(n) = 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

a(n) = 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

REFERENCES

Kim, Ki Hang; Rogers, Douglas G.; Roush, Fred W. 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

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

LINKS

T. D. Noe, Table of n, a(n) for n = 1..200

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.

T. Fine, Extrapolation when very little is known about the source Information and Control 16 (1970), 331-359.

D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, A 23 (1977), 88-98. Erratum, loc. cit., 25 (1978), 95-96.

Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186. See Table 2.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Index entries for sequences related to rooted trees

FORMULA

a(n) = A000957(n) + A000957(n+1).

G.f.: (1-x-(1+x)*sqrt(1-4*x))/(2*x*(x+2)). - Paul Barry, Jan 26 2007

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

a(n+1) = Sum_{0<=k<=[n/2]} A039599(n-k,k). - Philippe Deléham, Mar 13 2007

a(n) = (-1/2)^n*(-2-5*Sum((-8)^k*Gamma(1/2+k)*(4/5+k)/(sqrt(Pi)*Gamma(k+3)),k=1.. n-1)). - Mark van Hoeij, Nov 11 2009

a(n) + a(n+1) = A135339(n+1). - Philippe Deléham, Dec 02 2009

a(n) = sum of top row terms in M^(n-1), where M = the following infinite square production matrix:

0, 1, 0, 0, 0, 0,...

1, 1, 1, 0, 0, 0,...

1, 1, 1, 1, 0, 0,...

1, 1, 1, 1, 1, 0,...

1, 1, 1, 1, 1, 1,...

...

- Gary W. Adamson, Jul 14 2011

Conjecture: 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

a(n) ~ 5*4^n/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013

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

MAPLE

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

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

MATHEMATICA

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 *)

PROG

(Python)

from itertools import accumulate

def A000958_list(size):

    if size < 1: return []

    L, accu = [], [1]

    for n in range(size-1):

        accu = list(accumulate(accu+[-accu[-1]]))

        L.append(accu[n])

    return L

print(A000958_list(29)) # Peter Luschny, Apr 25 2016

CROSSREFS

A column of A065602, a column of A098747.

Cf. A127541, A127539, A000108, A000957, A032357.

Sequence in context: A046342 A238977 A182453 * A148782 A148783 A084205

Adjacent sequences:  A000955 A000956 A000957 * A000959 A000960 A000961

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 22:56 EST 2018. Contains 299427 sequences. (Running on oeis4.)