|
|
A174072
|
|
Number of permutations of length n with no consecutive triples i,i+2,i+4.
|
|
9
|
|
|
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
|
|
|
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):
|
|
MATHEMATICA
|
b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[
If[x == 0 || x - y != 2 || y - j != 2,
b[s ~Complement~ {j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
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
|
|
STATUS
|
approved
|
|
|
|