%I #31 Sep 11 2024 00:40:06
%S 1,1,1,1,2,4,6,8,11,17,27,41,60,88,132,200,301,449,669,1001,1502,2252,
%T 3370,5040,7543,11297,16919,25329,37912,56752,84968,127216,190457,
%U 285121,426841,639025,956698,1432276,2144238,3210104,4805827,7194801
%N Number of permutations satisfying -k <= p(i)-i <= r and p(i)-i not in I, i=1..n, with k=1, r=4, I={1,2}.
%C Number of compositions (ordered partitions) of n into elements of the set {1,4,5}.
%C a(n+3) is the number of length-n binary words with no substring 1x1 of 1xy1 (that is, no 1's occur with distance two or three), see fxtbook link. - _Joerg Arndt_, May 27 2011
%D D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.
%H Michael De Vlieger, <a href="/A079972/b079972.txt">Table of n, a(n) for n = 0..5708</a>
%H Michael A. Allen, <a href="https://arxiv.org/abs/2409.00624">Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings</a>, arXiv:2409.00624 [math.CO], 2024. See p. 18.
%H Said Amrouche, Hacène Belbachir, <a href="https://doi.org/10.3906/mat-1811-109">Unimodality and linear recurrences associated with rays in the Delannoy triangle</a>, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 14.10.3, p. 322
%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1,1).
%F a(n) = a(n-1) + a(n-4) + a(n-5).
%F G.f.: 1/(1-x-x^4-x^5).
%F a(n) = Sum_{k=0..n} Sum_{j=floor((n-k)/4)..floor((n-k)/3)} binomial(k,j)*binomial(j,n-k-3*j). - _Vladimir Kruchinin_, May 26 2011
%t CoefficientList[Series[1/(1 - x - x^4 - x^5), {x, 0, 41}], x] (* _Michael De Vlieger_, Feb 03 2020 *)
%o (Maxima)
%o a(n):=sum(sum(binomial(k,j)*binomial(j,n-k-3*j),j,floor((n-k)/4),floor((n-k)/3)),k,0,n); /* _Vladimir Kruchinin_, May 26 2011 */
%Y Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.
%K nonn
%O 0,5
%A _Vladimir Baltic_, Feb 17 2003