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.

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

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, except side (1,n) is unrestricted.

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      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.

Cf. A338526, A338838, A338849.

Cf. A340107, A340108.

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.