login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A033303
Expansion of (1 + x)/(1 - 2*x - x^2 + x^3).
8
1, 3, 7, 16, 36, 81, 182, 409, 919, 2065, 4640, 10426, 23427, 52640, 118281, 265775, 597191, 1341876, 3015168, 6775021, 15223334, 34206521, 76861355, 172705897, 388066628, 871977798, 1959316327
OFFSET
0,2
COMMENTS
Also the number of one-sided n-step prudent walks that avoid 3 or more consecutive east steps. - Shanzhen Gao, Apr 27 2011
Equivalently, number of ternary strings of length n with subwords (0,0) and (1,2) not allowed. - Olivier Gérard, Aug 28 2012
First differences are in A052534.
a(n) is the number of vertices of the Minkowski sum of n simplices with vertices e_(i+1), e_(i+2), e_(i+3) for i=0,...,n-1, where e_i is a standard basis vector. - Alejandro H. Morales, Oct 05 2022
REFERENCES
R. P. Stanley, Enumerative Combinatorics I, p. 244.
LINKS
L. Escobar, P. Gallardo, J. González-Anaya, J. L. González, G. Montúfar, and A. H. Morales, Enumeration of max-pooling responses with generalized permutohedra, arXiv:2209.14978 [math.CO], 2022. (See Ex. 4.7)
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
FORMULA
a(0)=1, a(1)=h(n), and a(n) = h(n) + h(n-1) for n >= 2, where h(n) = Sum_{k=1..n} Sum_{j=0..k} binomial(k, j) * binomial(j, n-3*k+2*j) * 2^(3*k-n-j) * (-1)^(k-j). - Vladimir Kruchinin, Sep 09 2010
a(0)=1, a(1)=3, a(2)=7, a(n) = 2*a(n-1) + a(n-2) - a(n-3). - Harvey P. Dale, Oct 31 2013
a(n) = A006054(n+1)+A006054(n+2). - R. J. Mathar, Jul 08 2022
MATHEMATICA
CoefficientList[Series[(1 + x)/(1 - 2*x - x^2 + x^3), {x, 0, 100}], x] (* Vincenzo Librandi, Oct 20 2012 *)
LinearRecurrence[{2, 1, -1}, {1, 3, 7}, 40] (* Harvey P. Dale, Oct 31 2013 *)
PROG
(Maxima) h(n):=sum(sum(binomial(k, j)*binomial(j, n-3*k+2*j)*2^(3*k-n-j)*(-1)^(k-j), j, 0, k), k, 1, n); a(n):=if n=0 then 1 else if n=2 then h(n) else h(n)+h(n-1); /* Vladimir Kruchinin, Sep 09 2010 */
(PARI) a(n)=([0, 1, 0; 0, 0, 1; -1, 1, 2]^n*[1; 3; 7])[1, 1] \\ Charles R Greathouse IV, Feb 19 2017
CROSSREFS
Sequence in context: A077852 A218983 A020746 * A078056 A173761 A361507
KEYWORD
nonn,nice,easy
STATUS
approved