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

Author

Xiangyu Chen, Nov 11 2020

Keywords

• nonn
• tabl

Comments

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

Examples

			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
		

Crossrefs

Right diagonal is A002493.

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

Programs

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

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.