A025565 a(n) = T(n,n-1), where T is array defined in A025564.

1, 2, 4, 10, 26, 70, 192, 534, 1500, 4246, 12092, 34606, 99442, 286730, 829168, 2403834, 6984234, 20331558, 59287740, 173149662, 506376222, 1482730098, 4346486256, 12754363650, 37461564504, 110125172682, 323990062452, 953883382354

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Comments

a(n+1) is the number of UDU-free paths of n upsteps (U) and n downsteps (D), n>=0. - David Callan, Aug 19 2004

Hankel transform is A120580. - Paul Barry, Mar 26 2010

If interpreted with offset 0, the inverse binomial transform of A006134 - Gary W. Adamson, Nov 10 2007

Also the number of different integer sets { k_1, k_2, ..., k_(i+1) } with Sum_{j=1..i+1} k_j = i and k_j >= 0, see the "central binomial coefficients" (A000984), without all sets in which any two successive k_j and k_(j+1) are zero. See the partition problem eq. 3.12 on p. 19 in my dissertation below. - Eva Kalinowski, Oct 18 2012

Examples

			G.f. = x + 2*x^2 + 4*x^3 + 10*x^4 + 26*x^5 + 70*x^6 + 192*x^7 + 534*x^8 + ...
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
• Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
• Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
• D. Baccherini, D. Merlini, and R. Sprugnoli, Binary words excluding a pattern and proper Riordan arrays, Discrete Math. 307 (2007), no. 9-10, 1021--1037. MR2292531 (2008a:05003). See page 1034. - _N. J. A. Sloane_, Mar 25 2014
• J. L. Jacobsen and J. Salas, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models IV. Chromatic polynomial with cyclic boundary conditions, J. Stat. Phys. 122 (2006) 705-760; arXiv:cond-mat/0407444, 2004-2006. Mentions this sequence. - _N. J. A. Sloane_, Mar 14 2014
• Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Crossrefs

Cf. A005773, A025564.

First column of A097692.

Partial sums of A105696.

Programs

Haskell

a025565 n = a025565_list !! (n-1)
a025565_list = 1 : f a001006_list [1] where
   f (x:xs) ys = y : f xs (y : ys) where
     y = x + sum (zipWith (*) a001006_list ys)
-- Reinhard Zumkeller, Mar 30 2012

Maple

seq( add(binomial(i-2, k)*(binomial(i-k, k+1)), k=0..floor(i/2)), i=1..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
# Alternatively:
a := n -> `if`(n=1,1,2*(-1)^n*hypergeom([3/2, 2-n], [2], 4)):
seq(simplify(a(n)),n=1..28); # Peter Luschny, Jan 30 2017

Mathematica

T[, 0] = 1; T[1, 1] = 2; T[n, k_] /; 0 <= k <= 2n := T[n, k] = T[n-1, k-2] + T[n-1, k-1] + T[n-1, k]; T[, ] = 0;
a[n_] := T[n-1, n-1];
Array[a, 30] (* Jean-François Alcover, Jul 30 2018 *)

Sage

def A():
    a, b, n  = 1, 1, 1
    yield a
    while True:
        yield a + b
        n += 1
        a, b = b, ((3*(n-1))*a+(2*n-1)*b)//n
A025565 = A()
print([next(A025565) for  in range(28)]) # _Peter Luschny, Jan 30 2017

Formula

G.f.: x*sqrt((1+x)/(1-3*x)).

a(n) = 2*A005773(n-1) for n > 1.

a(n) = |A085455(n-1)| = A025577(n) - A025577(n-1) = A002426(n) + A002426(n-1).

Sum_{i=0..n} Sum_{j=0..i} (-1)^(n-i)*a(j)*a(i-j) = 3^n. - Mario Catalani (mario.catalani(AT)unito.it), Jul 02 2003

a(1) = 1, a(n) = M(n-1) + Sum_{k=1..n-1} M(k-1)*a(n-k) with M=A001006, the Motzkin Numbers. - Reinhard Zumkeller, Mar 30 2012

D-finite with recurrence: (-n+1)*a(n) +2*(n-1)*a(n-1) +3*(n-3)*a(n-2)=0. - R. J. Mathar, Dec 02 2012

G.f.: G(0), where G(k) = 1 + 4*x*(4*k+1)/( (1+x)*(4*k+2) - x*(1+x)*(4*k+2)*(4*k+3)/(x*(4*k+3) + (1+x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 26 2013

a(n) = n*hypergeom([2-n, 1/2-n/2, 1-n/2], [2, -n], 4). - Peter Luschny, Jul 12 2016

a(n) = (-1)^n*2*hypergeom([3/2, 2-n], [2], 4) for n > 1. - Peter Luschny, Jan 30 2017

Extensions

Incorrect statement related to A000984 (see A002426) and duplicate of the g.f. removed by R. J. Mathar, Oct 16 2009

Edited by R. J. Mathar, Aug 09 2010