login
A340106
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.
2
1, 1, 1, 1, 2, 2, 1, 3, 6, 4, 1, 4, 12, 20, 18, 1, 5, 20, 54, 100, 92, 1, 6, 30, 112, 318, 600, 570, 1, 7, 42, 200, 768, 2208, 4244, 4082, 1, 8, 56, 324, 1570, 6080, 17682, 34300, 33292, 1, 9, 72, 490, 2868, 13980, 54552, 159702, 311808, 304490, 1, 10, 90, 704, 4830, 28392, 139130, 545528, 1604616, 3147164, 3086890
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, except side (1,n) is unrestricted.
FORMULA
T(n,k) = A340107(n,k) + 2*O(n-1,k-1) + O(n-2,k-2), where O(n,k) = 2*(k-1)*T(n-1,k-1)/(n-1) - 2*O(n-1,k-1) + 3*O(n-2,k-2) + 2*O(n-3,k-3) + O(n-4,k-4), O(n,k)=0 for k<=1.
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 4
4 1 4 12 20 18
5 1 5 20 54 100 92
6 1 6 30 112 318 600 570
7 1 7 42 200 768 2208 4244 4082
8 1 8 56 324 1570 6080 17682 34300 33292
CROSSREFS
Right diagonal is A095816.
Sequence in context: A082137 A091187 A318607 * A259824 A065173 A330965
KEYWORD
nonn,tabl
AUTHOR
Xiangyu Chen, Dec 28 2020
STATUS
approved