login
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.
2
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.
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
KEYWORD
nonn,tabl
AUTHOR
Xiangyu Chen, Dec 28 2020
STATUS
approved