A340107 Triangle read by rows: T(n,k) is the number of permutations of k elements from [1..n] with longest consecutive chain size less than 3, when 1 and n are considered to be consecutive.

1, 1, 1, 1, 2, 2, 1, 3, 6, 0, 1, 4, 12, 16, 16, 1, 5, 20, 50, 90, 80, 1, 6, 30, 108, 300, 552, 516, 1, 7, 42, 196, 742, 2100, 3990, 3794, 1, 8, 56, 320, 1536, 5888, 16976, 32656, 31456, 1, 9, 72, 486, 2826, 13680, 53046, 154350, 299628, 290970, 1, 10, 90, 700, 4780, 27960, 136380, 532340, 1559040, 3044900, 2974380

Offset: 0

Author

Xiangyu Chen, Dec 28 2020

Keywords

• nonn
• tabl

Comments

In a convex n-gon, the number of paths using k non-repeated vertices and fewer than 3 vertices (2 sides) in a row.

Examples

			n\k   0     1     2     3     4     5     6     7     8
0     1
1     1     1
2     1     2      2
3     1     3      6      0
4     1     4     12     16     16
5     1     5     20     50     90    80
6     1     6     30    108    300   552    516
7     1     7     42    196    742  2100   3990  3794
8     1     8     56    320   1536  5888  16976 32656 31456
		

Crossrefs

Cf. A338526, A338838, A338849.

Cf. A340106, A340108.

Formula

T(n,k) = n*(A340106(n-1,k-1) - S(n-2,k-2)) except for T(n,0)=1, where S(n,k) = 2*A340106(n-1,k-1) - 2*A340106(n-2,k-2) + S(n-3,k-3), S(n,k)=0 for k <= 0. [exception added by Xiangyu Chen, Aug 19 2022]