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

Links

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

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.

Cf. A338526, A338838, A338849.

Cf. A340107, A340108.

Sequence in context: A082137 A091187 A318607 * A259824 A065173 A330965

Adjacent sequences: A340103 A340104 A340105 * A340107 A340108 A340109

Keyword

nonn,tabl

Author

Xiangyu Chen, Dec 28 2020

Status

approved