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!)
A174072 Number of permutations of length n with no consecutive triples i,i+2,i+4. 8
1, 1, 2, 6, 24, 114, 674, 4714, 37754, 340404, 3412176, 37631268, 452745470, 5900431012, 82802497682, 1244815252434, 19958707407096, 339960096280062, 6130407887839754, 116675071758609742, 2337186717333367706, 49153251967227002616, 1082860432463176004544 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Note for n<5 there are no such subsequences, so those values are trivially n!.

LINKS

Table of n, a(n) for n=0..22.

Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, 2012. [broken link]

EXAMPLE

For n=5 (0,2,4,1,3) is an example of a permutation with an i,i+2,i+4 triple. If we look at 0,2,4 as a block, then we have 3! ways to permute the triple with the remaining 1 & 3. Hence a(5) = 5! - 3! = 114.

MAPLE

b:= proc(s, x, y) option remember; `if`(s={}, 1, add(

     `if`(x=0 or x-y<>2 or y-j<>2, b(s minus {j}, y, j), 0), j=s))

    end:

a:= n-> b({$1..n}, 0$2):

seq(a(n), n=0..14);  # Alois P. Heinz, Apr 13 2021

CROSSREFS

Cf. A002628, A174073, A174074, A174075.

First column of A216716.

Sequence in context: A189283 A177522 A216717 * A224255 A326348 A128088

Adjacent sequences:  A174069 A174070 A174071 * A174073 A174074 A174075

KEYWORD

nonn

AUTHOR

Isaac Lambert, Mar 06 2010

EXTENSIONS

a(0)-a(4) and a(10)-a(11) moved from a duplicate entry based on the Dymacek et al. paper on Apr 13 2021

a(12)-a(22) from Alois P. Heinz, Apr 13 2021

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 August 4 21:32 EDT 2021. Contains 346455 sequences. (Running on oeis4.)