login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284845 Number of permutations on [n+4] with no circular 4-successions. 1
90, 468, 2982, 22320, 191106, 1838220, 19599822, 229257288, 2917290090, 40107565764, 592302134070, 9349254600288, 157059054215442, 2797498002296700, 52657059745734366, 1044337677676754040, 21765735199891598202, 475573090189331643828, 10870086948032475194310 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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).

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.

LINKS

Table of n, a(n) for n=1..19.

Enrique Navarrete, Generalized K-Shift Forbidden Substrings in Permutations, arXiv:1610.06217 [math.CO], 2016.

FORMULA

a(n) = (n+4)* Sum_{j=0..n} (-1)^j*binomial(n,j)*(n-j+3)!.

Conjecture: a(n) = (n+4)*A277609(n+3). - R. J. Mathar, Jul 15 2017

EXAMPLE

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.

MAPLE

A284845 := proc(n)

    local j;

    add( (-1)^j*binomial(n, j)*(n-j+3)!, j=0..n) ;

    %*(n+4) ;

end proc:

seq(A284845(n), n=1..20) ; # R. J. Mathar, Jul 15 2017

MATHEMATICA

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 *)

CROSSREFS

Sequence in context: A187300 A237129 A250870 * A203741 A203734 A066116

Adjacent sequences:  A284842 A284843 A284844 * A284846 A284847 A284848

KEYWORD

nonn

AUTHOR

Enrique Navarrete, Apr 03 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 06:14 EST 2021. Contains 340333 sequences. (Running on oeis4.)