|
%I #18 Dec 09 2017 14:57:35
%S 16,70,384,2534,19424,169254,1650160,17784646,209855856,2689946246,
%T 37210700576,552433526310,8759992172224,147751562532454,
%U 2641055171379984,49869279287055494,991843699479853520,20724299315437752006,453861919477920665536,10395594941305558134886
%N Number of permutations on [n+3] with no circular 3-successions.
%C Define a circular k-succession in a permutation p on [n] as either a pair p(i),p(i+1) if p(i+1)=p(i)+k, or as the pair p(n),p(1) if p(1)=p(n)+k. If we let d*(n,k) be the number of permutations on [n] that avoid substrings (j,j+k), 1 <= j <= n, k=3, i.e., permutations with no circular 3-succession, then a(n) counts d*(n+3,3).
%C For example, for n=1, the permutations in S4 that contain the substring {14} in circular 3-succession are 1423, 1432, 2143, 2314, 3142, 3214, 4231, 4321, therefore d*(4,3) consists of the complementary permutations in S4, and a(1)=16.
%H Enrique Navarrete, <a href="http://arxiv.org/abs/1610.06217">Generalized K-Shift Forbidden Substrings in Permutations</a>, arXiv:1610.06217 [math.CO], 2016.
%F a(n) = (n+3)* Sum_{j=0..n} (-1)^j*binomial(n,j)*(n-j+2)!.
%F Conjecture: a(n) = (n+3)*A055790(n+1). - _R. J. Mathar_, Jul 15 2017
%e a(2)=70 since there are 70 permutations in S5 with no circular 3-succession, i.e., permutations that avoid substrings {14,25} such as 25134 or 51342.
%p A284844 := proc(n)
%p local j;
%p add( (-1)^j*binomial(n,j)*(n-j+2)!,j=0..n) ;
%p %*(n+3) ;
%p end proc:
%p seq(A284844(n),n=1..20) ; # _R. J. Mathar_, Jul 15 2017
%t a[n_] := ((n+3)*((n*(n+5)+5)*Subfactorial[n+2]+(-1)^(n+1)*(n+1)))/((n+2)*(n+1));
%t Array[a, 20] (* _Jean-François Alcover_, Dec 09 2017 *)
%K nonn
%O 1,1
%A _Enrique Navarrete_, Apr 03 2017
|
