0,5

Row-sum of signed Catalan triangle A009766. - Wouter Meeussen

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.

From Douglas Rogers, Oct 18 2005: (Start)

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, 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.

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.

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). (End)

Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - Gary W. Adamson, Jan 09 2009

Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - Gary W. Adamson, May 01 2009

For a relation to non-crossing partitions of the root system A_n, see A100754. - Tom Copeland, Oct 19 2014

From Tom Copeland, Nov 02 2014: (Start)

Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).

Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) =  P(x).

Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).

BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).

Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).

Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].

(End)

E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., 31 (2001), 31-38.

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

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

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

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

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb. 12 (2005) R31.

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, 46 (2001).

J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

N. T. Cameron, Random walks, trees and extensions of Riordan group techniques

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.

Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.

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.

C. Jean-Louis and A. Nkwanta, Some algebraic structure of the Riordan group, Linear Algebra and its Applications, Nov. 27, 2012. - N. J. A. Sloane, Jan 03 2013

Sergey Kitaev, Anna de Mier, Marc Noy, On the number of self-dual rooted maps, European J. Combin. 35 (2014), 377--387. MR3090510. See page 827.

S. Kitaev, J. Remmel and M. Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243, 2012. - From N. J. A. Sloane, May 09 2012

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

T. Mansour, M. Shattuck, Chebyshev Polynomials and Statistics on a New Collection of Words in the Catalan Family, arXiv:1407.3516 [math.CO], 2014

A. Nkwanta, A. Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, 16 (2013), #13.9.5.

P. Peart and W.-J. Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), #00.2.1.

P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.

A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations.

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

V. Strehl, A note on similarity relations, Discr. Math., 19 (1977), 99-102.

Index entries for sequences related to rooted trees

Catalan(n) = 2*a(n) + a(n-1), n >= 1.

a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.

G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, A000108). - Emeric Deutsch

a(n) ~ 4^(n+1)/(9*n*sqrt(n*Pi)).

a(n) = (2/(n-1))sum((-2)^j*(j+1)binomial(2n-1, n-3-j), j=0..n-3), n>=2. - Emeric Deutsch, Dec 26 2003

a(n) = 3*sum(binomial(2n-2j-2, n-1), j=0..floor((n-1)/2)) - binomial(2n, n) for n>0. - Emeric Deutsch, Jan 28 2004

Reversion of g.f. (x-2x^2)/(1-x)^2. - Ralf Stephan, Mar 22 2004

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, Jun 10 2005

Hankel determinant transform is 1-n. - Michael Somos, Sep 17 2006

a(n+1) = A126093(n,0). - Philippe Deléham, Mar 05 2007

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). - Paul Barry, Dec 02 2008

From Paul Barry, Jan 17 2009: (Start)

G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;

a(n+1) = sum{k=0..n, (-1)^k*C(2n-k,n-k)*(k+1)/(n+1)}. (End)

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). - Mark van Hoeij, Nov 11 2009

Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - Milan Janjic, Jul 08 2010

a(n) = the upper left term in M^n, n>0; where M = the 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

a(n+1) = Sum_{k, 0<=k<=n} A039598(n,k)*(-2)^k. - Philippe Deléham, Nov 04 2011

Conjecture: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar, Nov 15 2011

a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - José Luis Ramírez Ramírez, Mar 22 2012

0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * 2^n if n>0. - Michael Somos, Jan 31 2014

G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...

t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1, x, 90); A000957 := n- coeff(t2, x, n);

A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # Johannes W. Meijer, Jul 22 2013

Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* Wouter Meeussen *)

a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* Jean-François Alcover, Feb 22 2012 *)

(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 */

(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 */

(Haskell)

a000957 n = a000957_list !! n

a000957_list = 0 : 1 :

   (map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)

-- Reinhard Zumkeller, Nov 12 2011

A column of A065600.

Sequence with signs: A064310.

Bisections: A138413, A138414.

Cf. A068875

Cf. A000108, A000045, A005043, A057078, A007317, A091867, A104597.

Sequence in context: A064310 A126983 A104629 * A125305 A148458 A148459

Adjacent sequences:  A000954 A000955 A000956 * A000958 A000959 A000960

nonn,nice,easy

N. J. A. Sloane

approved