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 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
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
More terms from Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de), Dec 17 1999
STATUS
approved