A017817 a(n) = a(n-3) + a(n-4), with a(0)=1, a(1)=a(2)=0, a(3)=1.

1, 0, 0, 1, 1, 0, 1, 2, 1, 1, 3, 3, 2, 4, 6, 5, 6, 10, 11, 11, 16, 21, 22, 27, 37, 43, 49, 64, 80, 92, 113, 144, 172, 205, 257, 316, 377, 462, 573, 693, 839, 1035, 1266, 1532, 1874, 2301, 2798, 3406, 4175, 5099, 6204, 7581, 9274, 11303, 13785, 16855, 20577, 25088

Offset

0,8

Comments

Number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=1, r=3, I={0,1}. - Vladimir Baltic, Mar 07 2012

Number of compositions (ordered partitions) of n into parts 3 and 4.

For n>=2, a(n-2) is the number of ways to tile the 1xn board with dominoes and squares (ie. monominoes) such that there are either one or two squares between dominoes, no squares at either end of the board, and there is at least one domino. - Enrique Navarrete, Sep 01 2024

For n>=3, a(n-3) is the number of ways to tile the 1xn board with triominoes (ie. size 1x3) and squares (ie. size 1x1) such that there are either none or one squares between triominoes, no squares at either end of the board, and there is at least one triomino. - Enrique Navarrete, Sep 07 2024

Links

Seiichi Manyama, Table of n, a(n) for n = 0..10000

Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135.

Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 484

Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.

E. Wilson, The Scales of Mt. Meru

Index entries for two-way infinite sequences

Index entries for linear recurrences with constant coefficients, signature (0,0,1,1).

Formula

G.f.: 1/(1-x^3-x^4).

a(n)/a(n-1) tends to A060007. - Gary W. Adamson, Oct 22 2006

a(n) = Sum_{k=0..floor(n/3)} binomial(k,n-3*k). - Seiichi Manyama, Mar 06 2019

Mathematica

LinearRecurrence[{0, 0, 1, 1}, {1, 0, 0, 1}, 60] (* G. C. Greubel, Mar 05 2019 *)

Prog

(PARI) a(n)=polcoeff(if(n<0, (1+x)/(1+x-x^4), 1/(1-x^3-x^4)) +x*O(x^abs(n)), abs(n))
(Magma) I:=[1, 0, 0, 1]; [n le 4 select I[n] else Self(n-3) +Self(n-4): n in [1..60]]; // G. C. Greubel, Mar 05 2019
(Sage) (1/(1-x^3-x^4)).series(x, 60).coefficients(x, sparse=False) # G. C. Greubel, Mar 05 2019
(GAP) a:=[1, 0, 0, 1];; for n in [5..60] do a[n]:=a[n-3]+a[n-4]; od; a; # G. C. Greubel, Mar 05 2019

Crossrefs

A003269(n) = a(-4-n)(-1)^n.

Sequence in context: A346798 A340274 A127838 * A363567 A284834 A279677

Adjacent sequences: A017814 A017815 A017816 * A017818 A017819 A017820

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Dec 17 1999

Status

approved