A277609 Fourth column of Euler's difference table in A068106. It is 6 times the sequence A000261.

0, 0, 6, 18, 78, 426, 2790, 21234, 183822, 1781802, 19104774, 224406930, 2864826126, 39486808938, 584328412518, 9238767895026, 155416555683150, 2771424197143914, 52216883883837702, 1036463580947218962, 21616958644969620174, 472612476001411964970, 10808196686285486012646

Offset

1,3

Comments

For n >= 4, this is the number of permutations that avoid substrings j(j+3), 1 <= j <= n-3.

For n>=4, the number of circular permutations (in cycle notation) on [n+1] that avoid substrings (j,j+4), 1<=j<=n-3. For example, for n=4, there are 18 circular permutations in S5 that avoid the substring {15}. Note that each of these circular permutations represent 5 permutations in one-line notation (see link 2017). - Enrique Navarrete, Feb 22 2017

Links

Indranil Ghosh, Table of n, a(n) for n = 1..400

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

Enrique Navarrete, Forbidden Substrings in Circular K-Successions, arXiv:1702.02637 [math.CO], 2017.

Formula

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

a(n) ~ exp(-1) * n!. - Vaclav Kotesovec, Oct 28 2016

Example

a(5) = 78 since there are 78 permutations in S5 that avoid the substrings {14,25}.

Mathematica

Table[Sum[(-1)^j*Binomial[n - 3, j] (n - j)!, {j, 0, n - 3}], {n, 23}] (* Michael De Vlieger, Oct 27 2016 *)
Flatten[{0, 0, Table[n!*Hypergeometric1F1[3-n, -n, -1], {n, 3, 20}]}] (* Vaclav Kotesovec, Oct 28 2016 *)

Prog

(PARI) a(n) = sum(j=0, n-3, (-1)^j*binomial(n-3, j)*(n-j)!); \\ Michel Marcus, Oct 29 2016

Crossrefs

Cf. A068106, A000261.

Sequence in context: A332939 A299412 A218080 * A188119 A239420 A219590

Adjacent sequences: A277606 A277607 A277608 * A277610 A277611 A277612

Keyword

nonn

Author

Enrique Navarrete, Oct 23 2016

Status

approved