login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284844 Number of permutations on [n+3] with no circular 3-successions. 1
16, 70, 384, 2534, 19424, 169254, 1650160, 17784646, 209855856, 2689946246, 37210700576, 552433526310, 8759992172224, 147751562532454, 2641055171379984, 49869279287055494, 991843699479853520, 20724299315437752006, 453861919477920665536, 10395594941305558134886 (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=3, i.e., permutations with no circular 3-succession, then a(n) counts d*(n+3,3).

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.

LINKS

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

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

FORMULA

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

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

EXAMPLE

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.

MAPLE

A284844 := proc(n)

    local j;

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

    %*(n+3) ;

end proc:

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

MATHEMATICA

a[n_] := ((n+3)*((n*(n+5)+5)*Subfactorial[n+2]+(-1)^(n+1)*(n+1)))/((n+2)*(n+1));

Array[a, 20] (* Jean-Fran├žois Alcover, Dec 09 2017 *)

CROSSREFS

Sequence in context: A063493 A220212 A027997 * A258724 A264888 A272964

Adjacent sequences:  A284841 A284842 A284843 * A284845 A284846 A284847

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 22:00 EDT 2018. Contains 316378 sequences. (Running on oeis4.)