|
%I #145 Mar 01 2024 17:25:02
%S 0,1,2,4,8,15,28,52,96,177,326,600,1104,2031,3736,6872,12640,23249,
%T 42762,78652,144664,266079,489396,900140,1655616,3045153,5600910,
%U 10301680,18947744,34850335,64099760,117897840,216847936,398845537,733591314,1349284788
%N a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.
%C 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
%C Row sums of Riordan array (1/(1-x), x(1+x+x^2)). - _Paul Barry_, Feb 16 2005
%C Diagonal sums of Riordan array (1/(1-x)^2, x(1+x)/(1-x)), A104698.
%C 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
%C Officially, to match A000073, this should start with a(0)=a(1)=0, a(2)=1. - _N. J. A. Sloane_, Sep 12 2020
%D A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 41.
%H Vincenzo Librandi, <a href="/A008937/b008937.txt">Table of n, a(n) for n = 0..200</a>
%H Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, <a href="https://arxiv.org/abs/2006.13002">From Unequal Chance to a Coin Game Dance: Variants of Penney's Game</a>, arXiv:2006.13002 [math.HO], 2020.
%H O. Dunkel, <a href="http://www.jstor.org/stable/2298801">Solutions of a probability difference equation</a>, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
%H T. Langley, J. Liese, and J. Remmel, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Langley/langley2.html">Generating Functions for Wilf Equivalence Under Generalized Factor Order</a>, J. Int. Seq. 14 (2011), Article # 11.4.2.
%H William Verreault, <a href="https://arxiv.org/abs/2107.10318">MacMahon Partition Analysis: a discrete approach to broken stick problems</a>, arXiv:2107.10318 [math.CO], 2021.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,0,-1).
%F a(n) = A018921(n-2) = A027084(n+1) + 1.
%F a(n) = (A000073(n+2) + A000073(n+4) - 1)/2.
%F From Mario Catalani (mario.catalani(AT)unito.it), Aug 09 2002: (Start)
%F G.f.: x/((1-x)*(1-x-x^2-x^3)).
%F a(n) = 2*a(n-1) - a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4. (End)
%F 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
%F 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
%F a(n) = -A077908(-n-3). - _Alois P. Heinz_, Jul 24 2008
%F a(n) = (A000213(n+2) - 1) / 2. - _Reinhard Zumkeller_, Apr 07 2012
%F 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
%F a(n) = Sum_{k=0..floor(n/2)} (n-2*k)*hypergeom([-k,-n+2*k+1], [2], 2). - _Peter Luschny_, Nov 09 2017
%F 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
%F 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
%e 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]
%p A008937 := proc(n) option remember; if n <= 3 then 2^n else 2*procname(n-1)-procname(n-4) fi; end;
%p 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
%t CoefficientList[Series[x/(1-2x+x^4), {x, 0, 40}], x]
%t Accumulate[LinearRecurrence[{1,1,1},{0,1,1},40]] (* _Harvey P. Dale_, Dec 04 2017 *)
%t LinearRecurrence[{2, 0, 0, -1},{0, 1, 2, 4},40] (* _Ray Chandler_, Mar 01 2024 *)
%o (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
%o (Haskell)
%o a008937 n = a008937_list !! n
%o a008937_list = tail $ scanl1 (+) a000073_list
%o -- _Reinhard Zumkeller_, Apr 07 2012
%o (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 */
%o (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
%o (Sage)
%o def A008937_list(prec):
%o P = PowerSeriesRing(ZZ, 'x', prec)
%o x = P.gen().O(prec)
%o return (x/(1-2*x+x^4)).list()
%o A008937_list(40) # _G. C. Greubel_, Sep 13 2019
%o (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
%Y Cf. A000073, A000213, A018921, A027084, A077908, A209972.
%Y Row sums of A055216.
%Y Column k = 1 of A140997 and second main diagonal of A140994.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Alejandro Teruel (teruel(AT)usb.ve)
|
