%I A000957 M1624 N0635
%S A000957 0,1,0,1,2,6,18,57,186,622,2120,7338,25724,91144,325878,1174281,4260282,
%T A000957 15548694,57048048,210295326,778483932,2892818244,10786724388,40347919626,
%U A000957 151355847012,569274150156,2146336125648,8110508473252,30711521221376
%N A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 
               1 on an n-set; also number of ordered rooted trees with n edges having 
               root of even degree.
%C A000957 Row-sum of signed Catalan triangle A009766. (Mma program and comment 
               from wouter.meeussen(AT)pandora.be.)
%C A000957 There are two schools of thought about the best indexing for these numbers. 
               Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulae 
               given here use both labelings.
%C A000957 Comments from Douglas Rogers, Oct 18 2005:
%C A000957 "I notice that you have some other zero-one evaluations of binary bracketings 
               (such as A055395). But if you have an operation # with 0#0 = 1#0 
               = 1, 0#1 = 1#1 = 0,
%C A000957 and look at the number of bracketings of a string of n 0's that come 
               out 0, you get another instance of the Fine numbers.
%C A000957 For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 
               1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. 
               Indeed, C = Z + W = Z + xCZ.
%C A000957 In terms of rooted planar trees with root of even degree, this says that 
               of all rooted planar trees, some have root of even degree (Z) and 
               some have root of odd degree (xCZ)."
%C A000957 Hankel transform of a(n+1)=[1,0,1,2,6,18,57,186,...] is A000012=[1,1,
               1,1,1,...] . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Oct 24 
               2007
%C A000957 a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... 
               (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Dec 02 
               2008]
%C A000957 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 09 2009: 
               (Start)
%C A000957 Starting with offset 3 = iterates of M * [1,0,0,0,...] where M =
%C A000957 a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,
               1,...] as the super and subdiagonals. (End)
%C A000957 Starting with "1" and convolved with A068875 = the Catalan numbers with 
               offset 1. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009]
%D A000957 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000957 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000957 Albert, M. H.; Aldred, R. E. L.; Atkinson, M. D.; Handley, C. C.; Holton, 
               D. A.; and McCaughan, D. J.; Sorting classes, Electron. J. Combin. 
               12 (2005), no. 1, Research Paper 31, 25 pp.
%D A000957 Paul Barry, A Catalan Transform and Related Transformations on Integer 
               Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
%D A000957 P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 
               89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, 
               Annals of Discrete Math., 43 (1989), 89-102.
%D A000957 E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 
               241 (2001), 241-265.
%D A000957 E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bull. Instit. 
               Combin. Applic., 31 (2001), 31-38.
%D A000957 T. Fine, Extrapolation when very little is known about the source. Information 
               and Control 16 (1970), 331-359.
%D A000957 D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. 
               Theory, A 23 (1977), 88-98.
%D A000957 V. Strehl, A note on similarity relations, Discr. Math., 19 (1977), 99-102.
%D A000957 M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 
               2544-2563.
%H A000957 T. D. Noe, <a href="b000957.txt">Table of n, a(n) for n = 0..200</a>
%H A000957 E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, <a href="http://www.mat.univie.ac.at/
               ~slc/opapers/s46rinaldi.html">ECO method and hill-free generalized 
               Motzkin paths</a>
%H A000957 N. T. Cameron, <a href="http://www.princeton.edu/~wmassey/NAM03/cameron.pdf">
               Random walks, trees and extensions of Riordan group techniques</a>
%H A000957 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
               The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 
               4 (2001), #01.1.5.
%H A000957 P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/
               JIS/index.html">Generating Functions via Hankel and Stieltjes Matrices</
               a>, J. Integer Seqs., Vol. 3 (2000), #00.2.1.
%H A000957 P. Peart and W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/
               JIS/index.html">Dyck Paths With No Peaks at Height k</a>, J. Integer 
               Sequences, 4 (2001), #01.1.3.
%H A000957 A. Robertson, D. Saracino and D. Zeilberger, <a href="http://arXiv.org/
               abs/math.CO/0203033">Refined restricted permutations</a>.
%H A000957 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to 
               rooted trees</a>
%F A000957 Catalan(n) = 2*a(n) + a(n-1), n >= 1.
%F A000957 G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, 
               A000108) - from Emeric Deutsch (deutsch(AT)duke.poly.edu).
%F A000957 a(n) ~ 4^(n+1)/(9*n*sqrt(n*Pi)).
%F A000957 a(n)=(2/(n-1))sum((-2)^j*(j+1)binomial(2n-1, n-3-j), j=0..n-3), n>=2. 
               - Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 26 2003
%F A000957 a(n) = 3*sum(binomial(2n-2j-2, n-1), j=0..floor((n-1)/2)) - binomial(2n, 
               n) for n>0. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 28 2004
%F A000957 Reversion of g.f. (x-2x^2)/(1-x)^2. - R. Stephan, Mar 22 2004
%F A000957 a(n)=((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n)=((-1)^n/
               2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. 
               - Paul Barry (pbarry(AT)wit.ie), Jun 10 2005
%F A000957 Hankel determinant transform is 1-n. - Michael Somos Sep 17 2006
%F A000957 a(n+1)=A126093(n,0) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Mar 
               05 2007
%F A000957 Contribution from Paul Barry (pbarry(AT)wit.ie), Jan 17 2009: (Start)
%F A000957 G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
%F A000957 a(n+1)=sum{k=0..n, (-1)^k*C(2n-k,n-k)*(k+1)/(n+1)}. (End)
%F A000957 a(n) = 3*(-1/2)^(n+1) + GAMMA(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8)/
               (sqrt(Pi)*(n+1)!) (for n>0) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), 
               Nov 11 2009]
%p A000957 t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1,x,90); A000957 
               := n-> coeff(t2,x,n);
%t A000957 Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} 
               ], {n, 0, 36} ]
%o A000957 (PARI) {a(n)=if(n<1, 0, polcoeff( 1/(1+2/(1-sqrt(1-4*x+x*O(x^n)))), n))} 
               /* Michael Somos Sep 17 2006 */
%o A000957 (PARI) {a(n)=if(n<1, 0, polcoeff( 1/(1+1/serreverse(x-x^2+x*O(x^n))), 
               n))} /* Michael Somos Sep 30 2006 */
%Y A000957 a(n)= (A064306(n-1)+(-1)^(n-1))/2^n, n >= 1. A column of A065600.
%Y A000957 Sequence with signs: A064310. Bisections: A138413, A138414.
%Y A000957 A068875 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), May 01 2009]
%Y A000957 Sequence in context: A064310 A126983 A104629 this_sequence A125305 A148458 
               A148459
%Y A000957 Adjacent sequences: A000954 A000955 A000956 this_sequence A000958 A000959 
               A000960
%K A000957 nonn,nice,easy,new
%O A000957 0,5
%A A000957 N. J. A. Sloane (njas(AT)research.att.com).