login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073. 36
0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, 117897840, 216847936, 398845537, 733591314, 1349284788 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
a(n+1) is the number of n-bit sequences that avoid 1100. - David Callan, Jul 19 2004 [corrected by Kent E. Morrison, Jan 08 2019]. Also the number of n-bit sequences avoiding one of the patterns 1000, 0011, 1110, ... or any binary string of length 4 without overlap at beginning and end. Strings where it is not true are: 1111, 1010, 1001, ... and their bitwise complements. - Alois P. Heinz, Jan 09 2019
Row sums of Riordan array (1/(1-x), x(1+x+x^2)). - Paul Barry, Feb 16 2005
Diagonal sums of Riordan array (1/(1-x)^2, x(1+x)/(1-x)), A104698.
A shifted version of this sequence can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925) with r = 3. (Equation (3) follows equation (4) in the paper!) The whole paper is a study of the properties of this and other similar sequences indexed by the parameter r. For r = 2, we get a shifted version of A000071. For r = 4, we get a shifted version of A107066. For r = 5, we get a shifted version of A001949. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 14 2019
Officially, to match A000073, this should start with a(0)=a(1)=0, a(2)=1. - N. J. A. Sloane, Sep 12 2020
REFERENCES
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 41.
LINKS
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
O. Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article # 11.4.2.
William Verreault, MacMahon Partition Analysis: a discrete approach to broken stick problems, arXiv:2107.10318 [math.CO], 2021.
FORMULA
a(n) = A018921(n-2) = A027084(n+1) + 1.
a(n) = (A000073(n+2) + A000073(n+4) - 1)/2.
From Mario Catalani (mario.catalani(AT)unito.it), Aug 09 2002: (Start)
G.f.: x/((1-x)*(1-x-x^2-x^3)).
a(n) = 2*a(n-1) - a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4. (End)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3). E.g., a(11) = 1 + 600 + 326 + 177 = 1104. - Philippe LALLOUET (philip.lallouet(AT)orange.fr), Oct 29 2007
a(n) = term (4,1) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,0; 1,0,0,1]^n. - Alois P. Heinz, Jul 24 2008
a(n) = -A077908(-n-3). - Alois P. Heinz, Jul 24 2008
a(n) = (A000213(n+2) - 1) / 2. - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k+1) *binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
a(n) = Sum_{k=0..floor(n/2)} (n-2*k)*hypergeom([-k,-n+2*k+1], [2], 2). - Peter Luschny, Nov 09 2017
a(n) = 2^(n-1)*hypergeom([1-n/4, 1/4-n/4, 3/4-n/4, 1/2-n/4], [1-n/3, 1/3-n/3, 2/3-n/3], 16/27)) for n > 0. - Peter Luschny, Aug 20 2020
a(n-1) = T(n) + T(n-3) + T(n-6) + ... + T(2+((n-2) mod 3)), for n >= 4, where T is A000073(n+1). - Jeffrey Shallit, Dec 24 2020
EXAMPLE
G.f. = x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 28*x^6 + 52*x^7 + 96*x^8 + 177*x^9 + ... [edited by Petros Hadjicostas, Jun 12 2019]
MAPLE
A008937 := proc(n) option remember; if n <= 3 then 2^n else 2*procname(n-1)-procname(n-4) fi; end;
a:= n-> (Matrix([[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 0], [1, 0, 0, 1]])^n)[4, 1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 24 2008
MATHEMATICA
CoefficientList[Series[x/(1-2x+x^4), {x, 0, 40}], x]
Accumulate[LinearRecurrence[{1, 1, 1}, {0, 1, 1}, 40]] (* Harvey P. Dale, Dec 04 2017 *)
LinearRecurrence[{2, 0, 0, -1}, {0, 1, 2, 4}, 40] (* Ray Chandler, Mar 01 2024 *)
PROG
(Magma) [ n eq 1 select 0 else n eq 2 select 1 else n eq 3 select 2 else n eq 4 select 4 else 2*Self(n-1)-Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 21 2011
(Haskell)
a008937 n = a008937_list !! n
a008937_list = tail $ scanl1 (+) a000073_list
-- Reinhard Zumkeller, Apr 07 2012
(PARI) {a(n) = if( n<0, polcoeff( - x^3 / (1 - 2*x^3 + x^4) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^4) + x * O(x^n), n))}; /* Michael Somos, Aug 23 2014 */
(PARI) a(n) = sum(j=0, n\2, sum(k=0, j, binomial(n-2*j, k+1)*binomial(j, k)*2^k)); \\ Michel Marcus, Sep 08 2017
(Sage)
def A008937_list(prec):
P = PowerSeriesRing(ZZ, 'x', prec)
x = P.gen().O(prec)
return (x/(1-2*x+x^4)).list()
A008937_list(40) # G. C. Greubel, Sep 13 2019
(GAP) a:=[0, 1, 1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Sep 13 2019
CROSSREFS
Row sums of A055216.
Column k = 1 of A140997 and second main diagonal of A140994.
Sequence in context: A008936 A320452 A073769 * A128805 A141018 A049864
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Alejandro Teruel (teruel(AT)usb.ve)
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 13:24 EDT 2024. Contains 371870 sequences. (Running on oeis4.)