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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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).

Crossrefs

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

Programs

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

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

Mathematica

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

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))

Sage

(1/(1-x^3-x^4)).series(x, 60).coefficients(x, sparse=False) # G. C. Greubel, Mar 05 2019

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

Extensions

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