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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284843 Number of permutations on [n+2] with no circular 2-successions. 0
3, 12, 55, 318, 2163, 16952, 150183, 1483290, 16153027, 192234372, 2481692343, 34538108822, 515428409715, 8210201868528, 139028223047143, 2493848817565362, 47236883312958723, 942120664413581180, 19735072617803491767, 433187081497364626542 (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 = 2, i.e., permutations with no circular 2-succession, then a(n) counts d*(n+2, 2).

For example, for n = 1, the permutations in S3 that contain the substring {13} in circular 2-succession are 132, 213, 321, therefore d*(3,2) consists of the permutations 123, 231, 312, and a(1) = 3.

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+2) * Sum_{j = 0..n} (-1)^j * (n - j + 1) * n!/j!.

EXAMPLE

For n = 2, the permutations in S4 that contain the substrings {13, 24} in circular 2-successions are 1243, 1324, 1342, 2134, 2413, 2431, 3124, 3241, 3421, 4132, 4213, 4312, therefore d*(4,2) consists of the complementary permutations in S4, and a(2) = 12.

MATHEMATICA

Table[(n + 2) Sum[(-1)^j * (n - j + 1) * n!/j!, {j, 0, n}], {n, 20}] (* Michael De Vlieger, Apr 05 2017 *)

PROG

(PARI) a(n) = (n + 2) * sum(j=0, n, (-1)^j * (n - j + 1) * n!/j!); \\ Indranil Ghosh, Apr 06 2017

(Python)

from sympy import factorial

print [(n + 2) * sum([(-1)**j * (n - j + 1) * factorial(n)/factorial(j) for j in range(n + 1)]) for n in range(1, 50)] # Indranil Ghosh, Apr 06 2017

CROSSREFS

Sequence in context: A263533 A064314 A185630 * A107318 A176281 A050147

Adjacent sequences:  A284840 A284841 A284842 * A284844 A284845 A284846

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 18 15:25 EST 2021. Contains 340254 sequences. (Running on oeis4.)