A155761 -id:A155761 - cp's OEIS frontend

A003229 a(n) = a(n-1) + 2*a(n-3) with a(0)=a(1)=1, a(2)=3.

1, 1, 3, 5, 7, 13, 23, 37, 63, 109, 183, 309, 527, 893, 1511, 2565, 4351, 7373, 12503, 21205, 35951, 60957, 103367, 175269, 297183, 503917, 854455, 1448821, 2456655, 4165565, 7063207, 11976517, 20307647, 34434061, 58387095, 99002389

Offset: 0

N. J. A. Sloane

Equals eigensequence of an infinite lower triangular matrix with 1's in the main diagonal, 0's in the subdiagonal and 2's in the subsubdiagonal (the triangle in the lower section of A155761). - Gary W. Adamson, Jan 28 2009
The operation in the comment of Jan 28 2009 is equivalent to the INVERT transform of (1, 0, 2, 0, 0, 0, ...). - Gary W. Adamson, Jan 21 2017
For n>=1, a(n) equals the number of ternary words of length n-1 having at least 2 zeros between every two successive nonzero letters. - Milan Janjic, Mar 09 2015

D. E. Daykin and S. J. Tucker, Introduction to Dragon Curves. Unpublished, 1976. See links below for an earlier version.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.
D. E. Daykin, Letter to N. J. A. Sloane, Dec 1973.
D. E. Daykin, Letter to N. J. A. Sloane, Mar 1974.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 1.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 2.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 3.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, page 4.
D. E. Daykin and S. J. Tucker, Sequences from Folding Paper, Unpublished manuscript, 1975, cached copy, reverse side of page 4.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 417.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for linear recurrences with constant coefficients, signature (1,0,2).

Cf. A077949, A077974. First differences of A003479. Partial sums of A052537. Equals |A077906(n)|+|A077906(n+1)|.

Cf. A155761, A003230.

a003229 n = a003229_list !! n
a003229_list = 1 : 1 : 3 : zipWith (+)
                           (map (* 2) a003229_list) (drop 2 a003229_list)
-- Reinhard Zumkeller, Jan 01 2014

I:=[1, 1, 3]; [n le 3 select I[n] else Self(n-1)+2*Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 12 2012

seq(add(binomial(n-2*k,k)*2^k,k=0..floor(n/3)),n=1..38); # Zerinvary Lajos, Apr 03 2007
with(combstruct): SeqSeqSeqL := [T, {T=Sequence(S), S=Sequence(U, card >= 1), U=Sequence(Z, card >=3)}, unlabeled]: seq(count(SeqSeqSeqL, size=n+4), n=0..35); # Zerinvary Lajos, Apr 04 2009
a := n -> `if`(n<3,[1,1,3][n+1], hypergeom([-n/3, -(1+n)/3, (1-n)/3], [-n/2, -(1+n)/2], -27/2)); seq(simplify(a(n)),n=0..35); # Peter Luschny, Mar 09 2015

LinearRecurrence[{1,0, 2},{1,1,3},40] (* Vincenzo Librandi, Jun 12 2012 *)

G.f.: (1+2*z^2)/(1-z-2*z^3). - Simon Plouffe in his 1992 dissertation
a(n) = A077949(n+1) = |A077974(n+1)|.
a(n) = u(n+1) - 3*u(n) + 2*u(n-1) where u(i) = A003230(i) [Daykin and Tucker]. - N. J. A. Sloane, Jul 08 2014
a(n) = hypergeom([-n/3,-(1+n)/3,(1-n)/3],[-n/2,-(1+n)/2],-27/2) for n>=3. - Peter Luschny, Mar 09 2015

A151281 Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, 0), (1, 0), (1, 1)}.

Original entry on oeis.org

1, 2, 6, 16, 48, 136, 408, 1184, 3552, 10432, 31296, 92544, 277632, 824448, 2473344, 7365120, 22095360, 65920000, 197760000, 590790656, 1772371968, 5299916800, 15899750400, 47578857472, 142736572416, 427357700096, 1282073100288, 3840133464064, 11520400392192, 34517383151616, 103552149454848

Offset: 0

Manuel Kauers, Nov 18 2008

From Paul Barry, Jan 26 2009: (Start)
Image of 2^n under A155761. Binomial transform is A129637. Hankel transform is 2^C(n+1,2).
In general, the g.f. of the reversion of x*(1+c*x)/(1+a*x+b*x^2) is given by the continued fraction x/(1 -(a-c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 -(a-2*c)*x -(b-a*c+c^2)*x^2/(1 - .... (End)
a(n) is the number of nondeterministic Dyck meanders of length n. See A368164 or the de Panafieu-Wallner article for the definiton of nondeterministc walks. A nondeterministic meander contains at least one classical meander, i.e., a walk never crossing the x-axis. - Michael Wallner, Dec 18 2023

Robert Israel, Table of n, a(n) for n = 0..2000
Paul Barry, A Note on a One-Parameter Family of Catalan-Like Numbers, JIS 12 (2009) 09.5.4
A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
A. Bostan and M. Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
M. Bousquet-Mélou and M. Mishna, 2008. Walks with small steps in the quarter plane, ArXiv 0810.4387.
Elie De Panafieu, Mohamed Lamine Lamali, and Michael Wallner, Combinatorics of nondeterministic walks of the Dyck and Motzkin type, arXiv:1812.06650 [math.CO], 2018.
Élie de Panafieu and Michael Wallner, Combinatorics of nondeterministic walks, arXiv:2311.03234 [math.CO], 2023.

Cf. A000108, A120730, A129637, A151374, A155761.

Cf. A368164 (nondeterministic Dyck bridges), A368234 (nondeterministic Dyck excursions).

[n le 3 select Factorial(n) else (3*n*Self(n-1) + 8*(n-3)*Self(n-2) - 24*(n-3)*Self(n-3))/n: n in [1..41]]; // G. C. Greubel, Nov 09 2022

N:= 1000: # to get terms up to a(N)
S:= series((sqrt(1-8*x^2)+4*x-1)/(4*x*(1-3*x)),x,N+1):
seq(coeff(S,x,j),j=0..N); # Robert Israel, Feb 18 2013

aux[i_, j_, n_] := Which[Min[i, j, n]<0 || Max[i, j]>n, 0, n==0, KroneckerDelta[i, j, n], True, aux[i, j, n]= aux[-1+i, -1+j, -1+n] +aux[-1+i, j, -1+n] +aux[1+i, j, -1+n]]; Table[Sum[aux[i,j,n], {i,0,n}, {j,0,n}], {n,0,25}]
a[n_]:= a[n]= If[n<3, (n+1)!, (3*(n+1)*a[n-1] +8*(n-2)*a[n-2] -24*(n-2)*a[n-3])/(n+1)]; Table[a[n], {n, 0, 30}] (* G. C. Greubel, Nov 09 2022 *)

def a(n): # a = A151281
    if (n==0): return 1
    elif (n%2==1): return 3*a(n-1) - 2^((n-1)/2)*catalan_number((n-1)/2)
    else: return 3*a(n-1)
[a(n) for n in (0..40)] # G. C. Greubel, Nov 09 2022

From Paul Barry, Jan 26 2009: (Start)
G.f.: 1/(1 -2*x -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 -2*x^2/(1 - .... (continued fraction).
G.f.: c(2*x^2)/(1-2*x*c(2*x^2)) = (sqrt(1-8*x^2) + 4*x - 1)/(4*x*(1-3*x)).
a(n) = Sum_{k=0..n} ((k+1)/(n+k+1))*C(n, (n-k)/2)*(1 +(-1)^(n-k))*2^((n-k)/2)*2^k.
Reversion of x*(1 + 2*x)/(1 + 4*x + 6*x^2). (End)
From Philippe Deléham, Feb 01 2009: (Start)
a(n) = Sum_{k=0..n} A120730(n,k)*2^k.
a(2*n+2) = 3*a(2*n+1), a(2*n+1) = 3*a(2*n) - 2^n*A000108(n).
a(2*n+1) = 3*a(2*n) - A151374(n). (End)
(n+1)*a(n) = 3*(n+1)*a(n-1) + 8*(n-2)*a(n-2) - 24*(n-2)*a(n-3). - R. J. Mathar, Nov 26 2012
a(n) ~ 3^n/2. - Vaclav Kotesovec, Feb 13 2014

cp's OEIS Frontend

A003229 a(n) = a(n-1) + 2*a(n-3) with a(0)=a(1)=1, a(2)=3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Formula