A216720 Duplicate of A174074.
2, 6, 22, 109, 657, 4625, 37186, 336336, 3379058, 37328103
Offset: 3
This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
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.
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
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];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)
For example, a(5) does not count the permutation (0,4,1,3,2) since 4,1,3 is an arithmetic progression of 2 mod(5).
Since a(5)=18, there are (5-1)!-18=4 circular permutations with modular consecutive triples i,i+2,i+4 in all circular permutations of length 5. These are exactly (0,2,4,1,3), (0,2,4,3,1), (0,4,2,1,3), and (0,3,2,4,1). Note some have more than one modular progression.
f[i_,n_,k_]:=If[i==0 && k==0,1,If[i==n && n==k,1,Binomial[k-1,k-i]*Binomial[n-k-1,k-i-1] + 2*Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i-1]+Binomial[k-1,k-i-1]*Binomial[n-k-1,k-i]]];
w1[i_,n_,k_]:=If[n-2k+i<0,0,If[n-2k+i==0,1,(n-2k+i-1)!]];
a[n_,k_]:=Sum[f[i,n,k]*w1[i,n,k],{i,0,k}];
A165962[n_]:=(n-1)!+Sum[(-1)^k*a[n,k],{k,1,n}];
b[n_,k_]:=Sum[Sum[Sum[f[j,n/2,p]*f[i-j,n/2,k-p]*w2[i,j,n,k,p],{p,0,k}],{j,0,i}],{i,0,k-1}];
w2[i_,j_,n_,k_,p_]:=If[n/2-2p+j<=0 || n/2-2(k-p)+(i-j)<=0,0,(n-2k+i-1)!];
A216727[n_?EvenQ]:=(n-1)!+Sum[(-1)^k*b[n,k],{k,1,n}];
A216727[n_?OddQ]:=A165962[n];
Table[A216727[n],{n,3,23}] (* David Scambler, Sep 18 2012 *)
Triangle begins:
2
6
22 2
109 10 1
657 55 7 1
4625 356 54 4 1
37186 2723 362 44 4 1
336336 23300 2837 368 34 4 1
3379058 220997 25408 2967 330 35 4 1
37328103 2308564 249736 26964 3100 292 36 4 1
...
For n=4 there is only (4-1)!-a(4) = 1 circular permutation with a consecutive triple i,i+d,i+2d. It is (0,1,2,3).
Comments