login
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}.
5

%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