A338838 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] where adjacent values cannot be consecutive modulo n.

1, 1, 1, 1, 2, 0, 1, 3, 0, 0, 1, 4, 4, 0, 0, 1, 5, 10, 10, 10, 10, 1, 6, 18, 36, 60, 84, 60, 1, 7, 28, 84, 210, 434, 630, 462, 1, 8, 40, 160, 544, 1552, 3440, 5168, 3920, 1, 9, 54, 270, 1170, 4338, 13158, 30366, 47178, 36954, 1, 10, 70, 420, 2220, 10220, 39780, 125220, 298060, 476220, 382740

Offset

0,5

Comments

In a convex n-gon, the number of paths using k-1 diagonals and k non-repeated vertices.

Links

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

Formula

T(n,k) = n*(A338526(n-1,k-1)-S(n-1,k-1)) for k>0 except T(2,2)=0, T(n,0)=1, where S(n,k) = 2*A338526(n-1,k-1)-S(n-1,k-1) for k>0, S(n,0)=0.

Example

n\k  0    1    2    3    4    5    6    7    8
0    1
1    1    1
2    1    2    0
3    1    3    0    0
4    1    4    4    0    0
5    1    5    10   10   10   10
6    1    6    18   36   60   84   60
7    1    7    28   84   210  434  630  462
8    1    8    40   160  544  1552 3440 5168 3920

Prog

(PARI) isokd(d, n) = my(x=abs(d)); (x==1) || (x==(n-1));
isok(s, p, n) = {my(w = vector(#s, k, s[p[k]])); for (i=1, #s-1, if (isokd(w[i+1] - w[i], n) == 1, return (0))); return (1); }
T(n, k) = {my(nb = 0); forsubset([n, k], s, for(i=1, k!, if (isok(s, numtoperm(k, i), n), nb++); ); ); nb; } \\ Michel Marcus, Nov 21 2020

Crossrefs

Right diagonal is A002493.

Cf. A011973, A034807, A338526, A338849, A000166.

Sequence in context: A062283 A136493 A338849 * A132213 A202502 A219839

Adjacent sequences: A338835 A338836 A338837 * A338839 A338840 A338841

Keyword

nonn,tabl

Author

Xiangyu Chen, Nov 11 2020

Status

approved