A005773 -id:A005773 - cp's OEIS frontend

A057682 a(n) = Sum_{j=0..floor(n/3)} (-1)^jbinomial(n,3j+1).

0, 1, 2, 3, 3, 0, -9, -27, -54, -81, -81, 0, 243, 729, 1458, 2187, 2187, 0, -6561, -19683, -39366, -59049, -59049, 0, 177147, 531441, 1062882, 1594323, 1594323, 0, -4782969, -14348907, -28697814, -43046721, -43046721, 0, 129140163, 387420489, 774840978

Offset: 0

N. J. A. Sloane, Oct 20 2000

Let M be any endomorphism on any vector space, such that M^3 = 1 (identity). Then (1-M)^n = A057681(n)-a(n)*M+z(n)*M^2, where z(0)=z(1)=0 and, apparently, z(n+2)=A057083(n). - Stanislav Sykora, Jun 10 2012
From Tom Copeland, Nov 09 2014: (Start)
This array belongs to an interpolated family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the interp. (here t=-2) o.g.f. G(x,t) = x(1-x)/[1+(t-1)x(1-x)] and inverse o.g.f. Ginv(x,t) =  [1-sqrt(1-4x/(1+(1-t)x))]/2 (Cf. A005773 and A091867 and A030528 for more info on this family). (End)
{A057681, A057682, A*}, where A* is A057083 prefixed by two 0's, is the difference analog of the trigonometric functions {k_1(x), k_2(x), k_3(x)} of order 3. For the definitions of {k_i(x)} and the difference analog {K_i (n)} see [Erdelyi] and the Shevelev link respectively. - Vladimir Shevelev, Jul 31 2017

			G.f. = x + 2*x^2 + 3*x^3 + 3*x^4 - 9*x^6 - 27*x^7 - 54*x^8 - 81*x^9 + ...
If M^3=1 then (1-M)^6 = A057681(6) - a(6)*M + A057083(4)*M^2 = -18 + 9*M + 9*M^2. - _Stanislav Sykora_, Jun 10 2012

A. Erdelyi, Higher Transcendental Functions, McGraw-Hill, 1955, Vol. 3, Chapter XVIII.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Mark W. Coffey, Reductions of particular hypergeometric functions 3F2 (a, a+1/3, a+2/3; p/3, q/3; +-1), arXiv preprint arXiv:1506.09160 [math.CA], 2015.
Vladimir Shevelev, Combinatorial identities generated by difference analogs of hyperbolic and trigonometric functions of order n, arXiv:1706.01454 [math.CO], 2017.
Index entries for linear recurrences with constant coefficients, signature (3,-3).

Alternating row sums of triangle A030523.

Cf. A000108, A000484, A000748, A005043, A005773, A057083, A057681, A091867.

I:=[0,1,2]; [n le 3 select I[n] else 3*Self(n-1)-3*Self(n-2): n in [1..45]]; // Vincenzo Librandi, Nov 10 2014

A057682:=n->add((-1)^j*binomial(n,3*j+1), j=0..floor(n/3)):
seq(A057682(n), n=0..50); # Wesley Ivan Hurt, Nov 11 2014

A[n_] := Array[KroneckerDelta[#1, #2 + 1] - KroneckerDelta[#1, #2] + Sum[KroneckerDelta[#1, #2 -q], {q, n}] &, {n, n}];
Join[{0,1}, Table[(-1)^(n-1)*Total[CoefficientList[ CharacteristicPolynomial[A[(n-1)], x], x]], {n,2,30}]] (* John M. Campbell, Mar 16 2012 *)
Join[{0}, LinearRecurrence[{3,-3}, {1,2}, 40]] (* Jean-François Alcover, Jan 08 2019 *)

{a(n) = sum( j=0, n\3, (-1)^j * binomial(n, 3*j + 1))} /* Michael Somos, May 26 2004 */

{a(n) = if( n<2, n>0, n-=2; polsym(x^2 - 3*x + 3, n)[n + 1])} /* Michael Somos, May 26 2004 */

b=BinaryRecurrenceSequence(3,-3,1,2)
def A057682(n): return 0 if n==0 else b(n-1)
[A057682(n) for n in range(41)] # G. C. Greubel, Jul 14 2023

G.f.: (x - x^2) / (1 - 3*x + 3*x^2).
a(n) = 3*a(n-1) - 3*a(n-2), if n>1.
Starting at 1, the binomial transform of A000484. - Paul Barry, Jul 21 2003
It appears that abs(a(n)) = floor(abs(A000748(n))/3). - John W. Layman, Sep 05 2003
a(n) = ((3+i*sqrt(3))/2)^(n-2) + ((3-i*sqrt(3))/2)^(n-2). - Benoit Cloitre, Oct 27 2003
a(n) = n*3F2(1/3-n/3,2/3-n/3,1-n/3 ; 2/3,4/3 ; 1) for n>=1. - John M. Campbell, Jun 01 2011
Let A(n) be the n X n matrix with -1's along the main diagonal, 1's everywhere above the main diagonal, and 1's along the subdiagonal. Then a(n) equals (-1)^(n-1) times the sum of the coefficients of the characteristic polynomial of A(n-1), for all n>1 (see Mathematica code below). - John M. Campbell, Mar 16 2012
Start with x(0)=1, y(0)=0, z(0)=0 and set x(n+1) = x(n) - z(n), y(n+1) = y(n) - x(n), z(n+1) = z(n) - y(n). Then a(n) = -y(n). But this recurrence falls into a repetitive cycle of length 6 and multiplicative factor -27, so that a(n) = -27*a(n-6) for any n>6. - Stanislav Sykora, Jun 10 2012
a(n) = A057083(n-1) - A057083(n-2). - R. J. Mathar, Oct 25 2012
G.f.: 3*x - 1/3 + 3*x/(G(0) - 1) where G(k)= 1 + 3*(2*k+3)*x/(2*k+1 - 3*x*(k+2)*(2*k+1)/(3*x*(k+2) + (k+1)/G(k+1)));(continued fraction, 3rd kind, 3-step). - Sergei N. Gladkovskii, Nov 23 2012
G.f.: Q(0,u) -1, where u=x/(1-x), Q(k,u) = 1 - u^2 + (k+2)*u - u*(k+1 - u)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
From Vladimir Shevelev, Jul 31 2017: (Start)
For n>=1, a(n) = 2*3^((n-2)/2)*cos(Pi*(n-2)/6);
For n>=2, a(n) = K_1(n) + K_3(n-2);
For m,n>=2, a(n+m) = a(n)*K_1(m) + K_1(n)*a(m) - K_3(n-2)*K_3(m-2), where
K_1 = A057681, K_3 = A057083. (End)

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

Original entry on oeis.org

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

Clark Kimberling

nonn

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

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

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.

Cf. A005773, A025564.
First column of A097692.
Partial sums of A105696.

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

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

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

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

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

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

A085810 Number of three-choice paths along a corridor of height 5, starting from the lower side.

Original entry on oeis.org

1, 2, 5, 13, 35, 96, 266, 741, 2070, 5791, 16213, 45409, 127206, 356384, 998509, 2797678, 7838801, 21963661, 61540563, 172432468, 483144522, 1353740121, 3793094450, 10628012915, 29779028189, 83438979561, 233790820762, 655067316176, 1835457822857, 5142838522138, 14409913303805

Offset: 1

Philippe Deléham, Jul 25 2003

From Svjetlan Feretic, Jun 01 2013: (Start)
A three-choice path is a path whose steps lie in the set {(1,1), (1,0), (1,-1)}.
The paths under consideration "live" in a corridor like 0<=y<=5. Thus, the ordinate of a vertex of a path can take six values (0,1,2,3,4,5), but the height of the corridor is five.
a(1)=1 is the number of paths with zero steps, a(2)=2 is the number of paths with one step, a(3)=5 is the number of paths with two steps, ...
Narrower corridors produce A000012, A000079, A000129, A001519, A057960. An infinitely wide corridor would produce A005773.
(End)
Diagonal sums of A114164. - Paul Barry, Nov 15 2005
C(n):= a(n)*(-1)^n appears in the following formula for the nonpositive powers of rho*sigma, where rho:=2*cos(Pi/7) and sigma:=sin(3*Pi/7)/sin(Pi/7) = rho^2-1 are the ratios of the smaller and larger diagonal length to the side length in a regular 7-gon (heptagon). See the Steinbach reference where the basis  <1,rho,sigma> is used in an extension of the rational field. (rho*sigma)^(-n) = C(n) + B(n)*rho + A(n)*sigma,n>=0, with B(n)= A181880(n-2)*(-1)^n, and A(n)= A116423(n+1)*(-1)^(n+1). For the nonnegative powers see A120757(n), |A122600(n-1)| and A181879(n), respectively. See also a comment under A052547.
a(n) is also the number of bi-wall directed polygons with n cells. (The definition of bi-wall directed polygons is given in the article on A122737.)

G. C. Greubel, Table of n, a(n) for n = 1..1000
Svjetlan Feretic, Generating functions for bi-wall directed polygons, in: Proc. of the Seventh Int. Conf. on Lattice Path Combinatorics and Applications (eds. S. Rinaldi and S. G. Mohanty), Siena, 2010, 147-151.
Peter Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), p. 22-31 (formula 5).
Roman Witula, Damian Slota and Adam Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-1).

Cf. A000012, A000079, A000129, A001519, A057960, A005773.

I:=[1,2,5]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-Self(n-3): n in [1..35]]; // Vincenzo Librandi, Sep 18 2015

LinearRecurrence[{4,-3,-1}, {1,2,5}, 50] (* Roman Witula, Aug 09 2012 *)
CoefficientList[Series[(1 - 2 x)/(1 - 4 x + 3 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

x='x+O('x^30); Vec((1-2*x)/(1-4*x+3*x^2+x^3)) \\ G. C. Greubel, Apr 19 2018

a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3).
From Paul Barry, Nov 15 2005: (Start)
G.f.: (1-2*x)/(1-4*x+3*x^2+x^3).
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, j)*C(j+k, 2k));
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, k+j)*C(k, k-j)*2^(n-2k-j));
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-2*k} C(n-j, n-2*k-j)*C(k, j)(-1)^j*2^(n-2*k-j)). (End)
a(n-1) = -B(n;-1) = (1/7)*((c(4)-c(1))*(1-c(1))^n + (c(1)-c(2))*(1-c(2))^n + (c(2)-c(4))*(1-c(4))^n), where a(-1):=0, c(j):=2*cos(2*Pi*j/7). Moreover, B(n;d), n in N, d in C, denotes the respective quasi-Fibonacci number defined in comments to A121449 or in Witula-Slota-Warzynski's paper (see also A077998, A006054, A052975, A094789, A121442). - Roman Witula, Aug 09 2012

Name corrected and clarified, and offset 1 from Svjetlan Feretic, Jun 01 2013

A057960 Number of base-5 (n+1)-digit numbers starting with a zero and with adjacent digits differing by one or less.

Original entry on oeis.org

1, 2, 5, 13, 35, 95, 259, 707, 1931, 5275, 14411, 39371, 107563, 293867, 802859, 2193451, 5992619, 16372139, 44729515, 122203307, 333865643, 912137899, 2492007083, 6808289963, 18600594091, 50817768107, 138836724395, 379308985003, 1036291418795, 2831200807595

Offset: 0

Henry Bottomley, May 18 2001

Or, number of three-choice paths along a corridor of width 5 and length n, starting from one side.

If b(n) is the number of three-choice paths along a corridor of width 5 and length n, starting from any of the five positions at the beginning of the corridor, then b(n) = a(n+2) for n >= 0. - Pontus von Brömssen, Sep 06 2021

			a(6) = 259 since a(5) = 21 + 30 + 25 + 14 + 5 so a(6) = (21+30) + (21 + 30 + 25) + (30+25+14) + (25+14+5) + (14+5) = 51 + 76 + 69 + 44 + 19.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Sergey Kirgizov, and Vincent Vajnovszki, Descent distribution on Catalan words avoiding a pattern of length at most three, arXiv:1803.06706 [math.CO], 2018.
Tomislav Došlić and Biserka Kolarec, On Log-Definite Tempered Combinatorial Sequences, Mathematics (2025) Vol. 13, Iss. 7, 1179.
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.
Index entries for linear recurrences with constant coefficients, signature (3,0,-2).

The "three-choice" comes in the recurrence b(n+1, i) = b(n, i-1) + b(n, i) + b(n, i+1) if 1 <= i <= 5. Narrower corridors produce A000012, A000079, A000129, A001519. An infinitely wide corridor (i.e., just one wall) would produce A005773. Two-choice corridors are A000124, A000125, A000127.

Cf. A038754, A052948, A155020 (first differences), A188866.

with(combstruct): ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), b): ZL1:=Prod(begin_blockP, Z, end_blockP): ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL1, ZL2, ZL3), b=ZL3], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n+2), n=0..28); # Zerinvary Lajos, Mar 08 2008

Join[{a=1,b=2},Table[c=(a+b)*2-1;a=b;b=c,{n,0,50}]] (* Vladimir Joseph Stephan Orlovsky, Nov 22 2010 *)
CoefficientList[Series[(1-x-x^2)/((1-x)*(1-2*x-2*x^2)),{x,0,100}],x] (* Vincenzo Librandi, Aug 13 2012 *)

from functools import cache
@cache
def B(n, j):
    if not 0 <= j < 5:
        return 0
    if n == 0:
        return j == 0
    return B(n - 1, j - 1) + B(n - 1, j) + B(n - 1, j + 1)
def A057960(n):
    return sum(B(n, j) for j in range(5))
print([A057960(n) for n in range(30)]) # Pontus von Brömssen, Sep 06 2021

a(n) = Sum_{0 <= i <= 6} b(n, i) where b(n, 0) = b(n, 6) = 0, b(0, 1) = 1, b(0, n) = 0 if n <> 1 and b(n+1, i) = b(n, i-1) + b(n, i) + b(n, i+1) if 1 <= i <= 5.
a(n) = 3*a(n-1) - 2*a(n-3) = 2*A052948(n) - A052948(n-2).
a(n) = ceiling((1+sqrt(3))^(n+2)/12). - Mitch Harris, Apr 26 2006
a(n) = floor(a(n-1)*(a(n-1) + 1/2)/a(n-2)). - Franklin T. Adams-Watters and Max Alekseyev, Apr 25 2006
a(n) = floor(a(n-1)*(1+sqrt(3))). - Philippe Deléham, Jul 25 2003
From Paul Barry, Sep 16 2003: (Start)
G.f.: (1-x-x^2)/((1-x)*(1-2*x-2*x^2));
a(n) = 1/3 + (2+sqrt(3))*(1+sqrt(3))^n/6 + (2-sqrt(3))*(1-sqrt(3))^n/6.
Binomial transform of A038754 (with extra leading 1). (End)
More generally, it appears that a(base,n) = a(base-1,n) + 3^(n-1) for base >= n; a(base,n) = a(base-1,n) + 3^(n-1)-2 when base = n-1. - R. H. Hardin, Dec 26 2006
a(n) = A188866(4,n-1) for n >= 2. - Pontus von Brömssen, Sep 06 2021
a(n) = 2*a(n-1) + 2*a(n-2) - 1 for n >= 2, a(0) = 1, a(1) = 2. - Philippe Deléham, Mar 01 2024
E.g.f.: exp(x)*(1 + 2*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x))/3. - Stefano Spezia, Mar 02 2024

This is the result of merging two identical entries submitted by Henry Bottomley and R. H. Hardin. - N. J. A. Sloane, Aug 14 2012

Name clarified by Pontus von Brömssen, Sep 06 2021

A005774 Number of directed animals of size n (k=1 column of A038622); number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, where s(0) = 2; also sum of row n+1 of array T in A026323.

Original entry on oeis.org

0, 1, 3, 9, 26, 75, 216, 623, 1800, 5211, 15115, 43923, 127854, 372749, 1088283, 3181545, 9312312, 27287091, 80038449, 234988827, 690513030, 2030695569, 5976418602, 17601021837, 51869858544, 152951628725, 451271872701, 1332147482253

Offset: 0

Simon Plouffe

Number of ordered trees with n+1 edges, having root degree at least 2 and nonroot outdegrees at most 2. - Emeric Deutsch, Aug 02 2002
From Petkovsek's algorithm, this recurrence does not have any closed form solutions. So there is no hypergeometric closed form for a(n). - Herbert S. Wilf
Sum of two consecutive trinomial coefficients starting two positions before central one. Example: a(4) = 10+16 and (1 + x + x^2)^4 = ... + 10*x^2 + 16*x^3 + 19*x^4 + ... - David Callan, Feb 07 2004
Image of n (A001477) under the Motzkin related matrix A107131. Binomial transform of A037952. - Paul Barry, May 12 2005
a(n) = total number of ascents (maximal runs of consecutive upsteps) in all Motzkin (n+1)-paths. For example, the 9 Motzkin 4-paths are FFFF, FFUD, FUDF, FUFD, UDFF, UDUD, UFDF, UFFD, UUDD and they contain a total of 9 ascents and so a(3)=9 (U=upstep, D=downstep, F=flatstep). - David Callan, Aug 16 2006
Image of the sequence (0,1,2,3,3,3,...) under the array A122896. - Paul Barry, Sep 18 2006
This is some kind of Motzkin transform of A079978 because the substitution x-> x*A001006(x) in the independent variable of the g.f. A079978(x) yields 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008

			G.f.: x + 3*x^2 + 9*x^3 + 26*x^4 + 75*x^5 + 216*x^6 + 623*x^7 + ...

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
P. Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
D. Gouyou-Beauchamps, G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.
Christian Krattenthaler, Daniel Yaqubi, Some determinants of path generating functions, II, arXiv:1802.05990 [math.CO], 2018; Adv. Appl. Math. 101 (2018), 232-265.
Simon Plouffe, Approximations de Séries Génératrices et Quelques Conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

Cf. A038622, A098494, A026010, A005773, A005775, A066822.

a005774 0 = 0
a005774 n = a038622 n 1 -- Reinhard Zumkeller, Feb 26 2013

seq( add(binomial(i,k+1)*binomial(i-k,k), k=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
seq(simplify(GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2)), n=0..27); # Peter Luschny, May 12 2016

CoefficientList[Series[(1-x-Sqrt[1-2x-3x^2])/(x(1-3x+Sqrt[1-2x-3x^2])),{x,0,30}],x] (* Harvey P. Dale, Sep 20 2011 *)
RecurrenceTable[{a[0]==0, a[1]==1,a[n]==(2n(n+1)a[n-1]+3n(n-1)a[n-2])/ ((n+2)(n-1))},a,{n,30}] (* Harvey P. Dale, Nov 09 2012 *)

s=[0,1]; {A005774(n)=k=(2*(n+2)*(n+1)*s[2]+3*(n+1)*n*s[1])/((n+3)*n); s[1]=s[2]; s[2]=k; k}

{a(n) = if( n<2, n>0, (2 * (n+1) * n *a(n-1) + 3 * (n-1) * n * a(n-2)) / (n+2) / (n-1))}; /* Michael Somos, May 01 2003 */

Inverse binomial transform of [ 0, 1, 5, 21, 84, ... ] (A002054). - John W. Layman
D-finite with recurrence (n+2)*(n-1)*a(n) = 2*n*(n+1)*a(n-1) + 3*n*(n-1)*a(n-2) for all n in Z. - Michael Somos, May 01 2003
E.g.f.: exp(x)*(BesselI(1, 2*x)+BesselI(2, 2*x)). - Vladeta Jovovic, Jan 01 2004
G.f.: (1-x-sqrt(1-2x-3x^2))/(x(1-3x+sqrt(1-2x-3x^2))); a(n)= Sum_{k=0..n} C(k+1, n-k+1)*C(n, k)*k/(k+1); a(n) = Sum_{k=0..n} C(n, k)*C(k, floor((k-1)/2)). - Paul Barry, May 12 2005
Starting (1, 3, 9, 26, ...) = binomial transform of A026010: (1, 2, 4, 7, 14, 25, 50, 91, ...). - Gary W. Adamson, Oct 22 2007
a(n)*(2+n) = (4+4*n)*a(n-1) - n*a(n-2) + (12-6*n)*a(n-3). - Simon Plouffe, Feb 09 2012
a(n) ~ 3^(n+1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
0 = a(n)*(+36*a(n+1) + 18*a(n+2) - 96*a(n+3) + 30*a(n+4)) + a(n+1)*(-6*a(n+1) + 49*a(n+2) - 26*a(n+3) + 3*a(n+4)) + a(n+2)*(+15*a(n+3) - 8*a(n+4)) + a(n+3)*(a(n+4)) if n >= 0. - Michael Somos, Aug 06 2014
a(n) = GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2). - Peter Luschny, May 12 2016

Further descriptions from Clark Kimberling

A132894 Number of (1,0) steps in all paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., in all length-n left factors of Motzkin paths).

Original entry on oeis.org

0, 1, 4, 15, 52, 175, 576, 1869, 6000, 19107, 60460, 190333, 596652, 1863745, 5804176, 18028755, 55873872, 172818243, 533589660, 1644921789, 5063762220, 15568666029, 47811348816, 146675181975, 449538774048, 1376564658525

Offset: 0

Emeric Deutsch, Oct 07 2007

nonn

Number of peaks (i.e., UDs) in all paths of length n+1 with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., in all length n+1 left factors of Motzkin paths). Example: a(2)=4 because in the 13 (=A005773(4)) length-3 left factors of Motzkin paths, namely HHH, HHU, H(UD), HUH, HUU, (UD)H, (UD)U, UHD, UHH, UHU, U(UD), UUH and UUU, we have altogether 4 peaks (shown between parentheses).

This could be called the Motzkin transform of A077043 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A077043 yields the g.f. of this sequence here. - R. J. Mathar, Nov 10 2008

			a(2) = 4 because in the 5 (=A005773(3)) length-2 left factors of Motzkin paths, namely HH, HU, UD, UH and UU, we have altogether 4 H steps.
G.f. = x + 4*x^2 + 15*x^3 + 52*x^4 + 175*x^5 + 576*x^6 + 1869*x^7 + 6000*x^8 + ...

Alois P. Heinz, Table of n, a(n) for n = 0..1000
A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv preprint arXiv:1203.6792, 2012; and also, J. Int. Seq. 17 (2014) #14.1.5.
Mark Shattuck, Subword Patterns in Smooth Words, Enum. Comb. Appl. (2024) Vol. 4, No. 4, Art. No. S2R32. See p. 6.

Cf. A005773, A107230, A132893.

Column k=1 of A328347.

a := n -> add(k*binomial(n, k)*binomial(n-k, floor((n-k)/2)), k=0..n): seq(a(n), n=0..25);
# second Maple program:
a:= proc(n) a(n):=`if`(n<2, n, 2*n/(n-1)*a(n-1)+3*a(n-2)) end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 15 2013

a[n_] := n*Hypergeometric2F1[3/2, 1-n, 2, 4]; Table[ a[n] // Abs, {n, 0, 25}] (* Jean-François Alcover, Jul 10 2013 *)
a[ n_] := If[ n < 0, 0, -(-1)^n n Hypergeometric2F1[ 3/2, 1 - n, 2, 4]]; (* Michael Somos, Aug 06 2014 *)

A132894 = lambda n: (-1)^(n+1)*jacobi_P(n-1,1,-n+1/2,-7)
[Integer(A132894(n).n(40),16) for n in range(26)] # Peter Luschny, Sep 23 2014

a(n) = Sum_{k=0..n} k*A107230(n,k).
a(n) = Sum_{k=0..floor((n+1)/2)} k*A132893(n+1,k).
a(n) = Sum_{k=0..n} k*C(n,k)*C(n-k, floor((n-k)/2)).
G.f.: z/((1-3*z)*sqrt(1-2*z-3*z^2)).
a(n) = Sum_{k=0..n} k*C(n,k)*C(2*k,k)*(-1)^(n-k). - Wadim Zudilin, Oct 11 2010
E.g.f.: exp(x)*x*(BesselI(0, 2*x) + BesselI(1, 2*x)). - Peter Luschny, Aug 25 2012
a(n) = 2*n/(n-1)*a(n-1) + 3*a(n-2) for n>=2, a(n) = n for n<2. a(n) = n*A005773(n). - Alois P. Heinz, Jul 15 2013
a(n) ~ 3^(n-1/2)*sqrt(n/Pi). - Vaclav Kotesovec, Oct 08 2013
a(n) = (-1)^(n+1)*JacobiP(n-1,1,-n+1/2,-7). - Peter Luschny, Sep 23 2014

A025566 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0, s(1) = 1, |s(i) - s(i-1)| <= 1 for i >= 2. Also a(n) = sum of numbers in row n+1 of the array T defined in A026105. Also a(n) = T(n,n), where T is the array defined in A025564.

Original entry on oeis.org

1, 1, 1, 3, 8, 22, 61, 171, 483, 1373, 3923, 11257, 32418, 93644, 271219, 787333, 2290200, 6673662, 19478091, 56930961, 166613280, 488176938, 1431878079, 4203938697, 12353600427, 36331804089, 106932444885, 314946659951, 928213563878

Offset: 0

Clark Kimberling

nonn

a(n+1) is the number of Motzkin (2n)-paths whose last weak valley occurs immediately after step n. A weak valley in a Motzkin path (A001006) is an interior vertex whose following step has nonnegative slope and whose preceding step has nonpositive slope. For example, the weak valleys in the Motzkin path F.UF.FD.UD occur after the first, third and fifth steps as indicated by the dots (U=upstep of slope 1, D=downstep of slope -1, F=flatstep of slope 0) and, with n=2, a(3)=3 counts FFUD, UDUD, UFFD. - David Callan, Jun 07 2006

Starting with offset 2: (1, 3, 8, 22, 61, 171, 483, ...), = row sums of triangle A136537. - Gary W. Adamson, Jan 04 2008

Michael De Vlieger, Table of n, a(n) for n = 0..2100
Jean-Luc Baril, Richard Genestier, Sergey Kirgizov, Pattern distributions in Dyck paths with a first return decomposition constrained by height, arXiv:1911.03119 [math.CO], 2019.
C. Dalfó, M. A. Fiol, and N. López, New results for the Mondrian art problem, arXiv:2007.09639 [math.CO], 2020.
D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From _N. J. A. Sloane_, May 11 2012
Christian Krattenthaler, Daniel Yaqubi, Some determinants of path generating functions, II, arXiv:1802.05990 [math.CO], 2018; Adv. Appl. Math. 101 (2018), 232-265.
Donatella Merlini, Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

First differences of A026135. Row sums of triangle A026105.
Pairwise sums of A005727. Column k=2 in A115990.
Cf. A001791, A132816.
Cf. A136537.

List([0..30],i->Sum([0..Int(i/2)],k->Binomial(i-2,k)*Binomial(i-k,k))); # Muniru A Asiru, Mar 09 2019

seq( sum('binomial(i-2,k)*binomial(i-k,k)', 'k'=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001

CoefficientList[Series[x+(2x(x-1))/(1-3x-Sqrt[1-2x-3x^2]),{x,0,30}],x] (* Harvey P. Dale, Jun 12 2016 *)

G.f.: x + 2*x*(x-1)/(1-3x-sqrt(1-2x-3x^2)); for n > 1, first differences of the "directed animals" sequence A005773: a(n) = A005773(n) - A005773(n-1). - Emeric Deutsch, Aug 16 2002
Starting (1, 3, 8, 22, 61, 171, ...) gives the inverse binomial transform of A001791 starting (1, 4, 15, 56, 210, 792, ...). - Gary W. Adamson, Sep 01 2007
a(n) is the sum of the (n-2)-th row of triangle A131816. - Gary W. Adamson, Sep 01 2007
D-finite with recurrence n*a(n) +(-3*n+2)*a(n-1) +(-n+2)*a(n-2) +3*(n-4)*a(n-3)=0. - R. J. Mathar, Sep 15 2020

A055898 Triangle: Number of directed site animals on a square lattice with n+1 total sites and k sites supported in one particular way.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 5, 1, 1, 10, 16, 7, 1, 1, 15, 39, 31, 9, 1, 1, 21, 81, 101, 51, 11, 1, 1, 28, 150, 272, 209, 76, 13, 1, 1, 36, 256, 636, 696, 376, 106, 15, 1, 1, 45, 410, 1340, 1980, 1496, 615, 141, 17, 1, 1, 55, 625, 2600, 5000, 5032, 2850, 939, 181, 19, 1, 1

Offset: 0

Christian G. Bower, Jun 13 2000

			Triangle begins:
  1;
  1, 1;
  1, 3, 1;
  1, 6, 5, 1;
  1,10,16, 7, 1;
  ...

A. J. Guttmann, Indicators of solvability for lattice models, Discrete Math., 217 (2000), 167-189 (A_sq of Section 6).
M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals
M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discr. Math., 180 (1998), 73-106.

Row sums give A005773. Columns 0-8: A000012, A000217, A011863(n-1), A055899-A055904. Cf. A055905, A055907.

nmax = 10;
A[x_, y_] = (1/2) x ((1 - (4 x/((1 + x) (1 + x - x y))))^(-1/2) - 1);
g = A[x, y] + O[x]^(nmax+3);
row[n_] := CoefficientList[Coefficient[g, x, n+2], y];
Table[row[n], {n, 0, nmax}] // Flatten (* Jean-François Alcover, Jul 24 2018 *)

T(n,m):=sum(binomial(n-k,m)*sum(binomial(n-m-k,i)*(-1)^(n+m-i)*binomial(k+i,k)*binomial(2*i+1,i+1),i,0,n-m-k),k,0,n); /* Vladimir Kruchinin, Jan 26 2022 */

G.f.: A(x, y)=(1/2x)((1-(4x/((1+x)(1+x-xy))))^(-1/2) - 1).

T(n,m) = Sum_{k=0..n} C(n-k,m)*Sum_{i=0..n-m-k} (-1)^(n+m-i) *C(n-m-k,i) *C(k+i,k) *C(2*i+1,i+1). - Vladimir Kruchinin, Jan 26 2022

A295679 Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 5, 8, 1, 1, 1, 2, 5, 13, 16, 1, 1, 1, 2, 5, 14, 35, 32, 1, 1, 1, 2, 5, 14, 41, 96, 64, 1, 1, 1, 2, 5, 14, 42, 124, 267, 128, 1, 1, 1, 2, 5, 14, 42, 131, 384, 750, 256, 1, 1, 1, 2, 5, 14, 42, 132, 420, 1210, 2123, 512, 1

Offset: 0

Andrew Howroyd, Nov 30 2017

Definition: Given a primitive k-th root of unity w, a binary operation a*b=a+wb, and sufficiently general fixed complex numbers x_0, ..., x_n, the k-modular Catalan numbers C_{n,k} enumerate parenthesizations of x_0*x_1*...*x_n that give distinct values.
Theorem: C_{n,k} enumerates the following objects:
(1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),
(2) plane trees with n+1 nodes whose non-root nodes have degree less than k,
(3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,
(4) partitions with n nonnegative parts bounded by the staircase partition (n-1,n-2,...,1,0) such that each positive number appears fewer than k times,
(5) standard 2-by-n Young tableaux whose top row avoids contiguous labels of the form i,j+1,j+2,...,j+k for all i(6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.
Columns of the array converge rowwise to A000108. The diagonal k=n-1 is A001453. - Andrey Zabolotskiy, Dec 02 2017

			Array begins (n >= 0, k > 0):
======================================================
n\k| 1   2    3    4    5    6    7    8    9   10
---|--------------------------------------------------
0  | 1   1    1    1    1    1    1    1    1    1 ...
1  | 1   1    1    1    1    1    1    1    1    1 ...
2  | 1   2    2    2    2    2    2    2    2    2 ...
3  | 1   4    5    5    5    5    5    5    5    5 ...
4  | 1   8   13   14   14   14   14   14   14   14 ...
5  | 1  16   35   41   42   42   42   42   42   42 ...
6  | 1  32   96  124  131  132  132  132  132  132 ...
7  | 1  64  267  384  420  428  429  429  429  429 ...
8  | 1 128  750 1210 1375 1420 1429 1430 1430 1430 ...
9  | 1 256 2123 3865 4576 4796 4851 4861 4862 4862 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Nickolas Hein, Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics, 61 (2017), 197-218, arXiv:1508.01688 [math.CO], 2015-2016.

Columns 3..9 are A005773, A159772, A261588, A261589, A261590, A261591, A261592.

Cf. A288942, A000108, A001453.

A295679 := proc(n,k)
    if n = 0 then
        1;
    else
        add((-1)^j/n*binomial(n,j)*binomial(2*n-j*k,n+1),j=0..(n-1)/k) ;
    end if ;
end proc:
seq(seq( A295679(n,d-n),n=0..d-1),d=1..12) ; # R. J. Mathar, Oct 14 2022

rows = cols = 12;
col[k_] := Module[{G}, G = InverseSeries[x*(1-x)/(1-x^k) + O[x]^cols, x]; CoefficientList[1/(1 - G), x]];
A = Array[col, cols];
T[n_, k_] := A[[k, n+1]];
Table[T[n-k+1, k], {n, 0, rows-1}, {k, n+1, 1, -1}] // Flatten (* Jean-François Alcover, Dec 05 2017, adapted from PARI *)

T(n,k)=polcoeff(1/(1-serreverse(x*(1-x)/(1-x^k) + O(x^max(2,n+1)))), n);
for(n=0, 10, for(k=1, 10, print1(T(n, k), ", ")); print);

G.f. of column k: 1/(1-G(x)) where G(x) is the reversion of x*(1-x)/(1-x^k).

A328347 Number T(n,k) of n-step walks on cubic lattice starting at (0,0,0), ending at (0,k,n-k) and using steps (0,0,1), (0,1,0), (1,0,0), (-1,1,1), (1,-1,1), and (1,1,-1); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 3, 4, 3, 7, 15, 15, 7, 19, 52, 72, 52, 19, 51, 175, 300, 300, 175, 51, 141, 576, 1185, 1480, 1185, 576, 141, 393, 1869, 4473, 6685, 6685, 4473, 1869, 393, 1107, 6000, 16380, 28392, 33880, 28392, 16380, 6000, 1107, 3139, 19107, 58572, 115332, 159264, 159264, 115332, 58572, 19107, 3139

Offset: 0

Alois P. Heinz, Oct 13 2019

These walks are not restricted to the first (nonnegative) octant.

			Triangle T(n,k) begins:
     1;
     1,    1;
     3,    4,     3;
     7,   15,    15,     7;
    19,   52,    72,    52,    19;
    51,  175,   300,   300,   175,    51;
   141,  576,  1185,  1480,  1185,   576,   141;
   393, 1869,  4473,  6685,  6685,  4473,  1869,  393;
  1107, 6000, 16380, 28392, 33880, 28392, 16380, 6000, 1107;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Columns k=0-1 give: A002426, A132894 = n*A005773(n).
Row sums give A084609.
T(2n,n) gives A328426.
Cf. A007318, A328300, A328345.

b:= proc(l) option remember; `if`(l[-1]=0, 1, (r-> add(add(
      add(`if`(i+j+k=1, (h-> `if`(add(t, t=h)<0, 0, b(h)))(
      sort(l-[i, j, k])), 0), k=r), j=r), i=r))([$-1..1]))
    end:
T:= (n, k)-> b(sort([0, k, n-k])):
seq(seq(T(n, k), k=0..n), n=0..12);

b[l_List] := b[l] = If[l[[-1]] == 0, 1, Sum[If[i + j + k == 1, Function[h, If[Total[h] < 0, 0, b[h]]][Sort[l - {i, j, k}]], 0], {i, {-1, 0, 1}}, {j, {-1, 0, 1}}, {k, {-1, 0, 1}}]];
T[n_, k_] := b[Sort[{0, k, n - k}]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 30 2020, after Alois P. Heinz *)

T(n,k) = T(n,n-k).

Previous Showing 21-30 of 103 results. Next

cp's OEIS Frontend

A057682 a(n) = Sum_{j=0..floor(n/3)} (-1)^j*binomial(n,3*j+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Sage

Formula

Extensions

A085810 Number of three-choice paths along a corridor of height 5, starting from the lower side.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A057960 Number of base-5 (n+1)-digit numbers starting with a zero and with adjacent digits differing by one or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A005774 Number of directed animals of size n (k=1 column of A038622); number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, where s(0) = 2; also sum of row n+1 of array T in A026323.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A132894 Number of (1,0) steps in all paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e., in all length-n left factors of Motzkin paths).

Views

Author

A057682 a(n) = Sum_{j=0..floor(n/3)} (-1)^jbinomial(n,3j+1).