|
%I #16 Jul 15 2017 09:35:06
%S 90,468,2982,22320,191106,1838220,19599822,229257288,2917290090,
%T 40107565764,592302134070,9349254600288,157059054215442,
%U 2797498002296700,52657059745734366,1044337677676754040,21765735199891598202,475573090189331643828,10870086948032475194310
%N Number of permutations on [n+4] with no circular 4-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=4, i.e., permutations with no circular 4-succession, then a(n) counts d*(n+4,4).
%C For example, a(1)=90 since there are 90 permutations in S5 with no circular 4-succession, i.e., permutations that avoid the substring {15} such as 15234 or 53241.
%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+4)* Sum_{j=0..n} (-1)^j*binomial(n,j)*(n-j+3)!.
%F Conjecture: a(n) = (n+4)*A277609(n+3). - _R. J. Mathar_, Jul 15 2017
%e a(2)=468 since there are 468 permutations in S6 with no circular 4-succession, i.e., permutations that avoid substrings {15,26} such as 261345 or 653142.
%p A284845 := proc(n)
%p local j;
%p add( (-1)^j*binomial(n,j)*(n-j+3)!,j=0..n) ;
%p %*(n+4) ;
%p end proc:
%p seq(A284845(n),n=1..20) ; # _R. J. Mathar_, Jul 15 2017
%t Table[(n + 4) Sum[(-1)^j Binomial[n, j] * (n - j + 3)!, {j, 0, n}], {n,0, 20}] (* or *) Table[(4+n) (3+n)! Hypergeometric1F1[-n,-3-n,-1],{n, 0, 20}] (* _Indranil Ghosh_, Apr 07 2017 *)
%K nonn
%O 1,1
%A _Enrique Navarrete_, Apr 03 2017
|
