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,5

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.

Links

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

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]

Example

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.

Sequence in context: A309495 A080955 A340108 * A125231 A117919 A309106

Adjacent sequences: A340104 A340105 A340106 * A340108 A340109 A340110

Keyword

nonn,tabl

Author

Xiangyu Chen, Dec 28 2020

Status

approved