A308203 Array read by ascending antidiagonals: T(n,k) = number of non-isomorphic kC_n-snakes for n >= 3 and k >= 2.
1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 3, 3, 6, 1, 1, 3, 6, 6, 10, 1, 1, 4, 6, 18, 10, 20, 1, 1, 4, 10, 18, 45, 20, 36, 1, 1, 5, 10, 40, 45, 135, 36, 72, 1, 1, 5, 15, 40, 136, 135, 378, 72, 136, 1, 1, 6, 15, 75, 136, 544, 378, 1134, 136, 272, 1
Offset: 3
Examples
T(n,2)=1 because there is only one way to connect two copies of C_n. T(3,k)=1 because C_3 is isomorphic to K_3 and all the selections of 2 cutpoints, in each interior copy of C_3, are equivalent. T(5,4)=3 there are only 3 non-equivalent strings of length 2 corresponding to the distances between consecutive cutpoints: 11, 12, and 2,2. Table begins: 1 1 1 1 1 1 1 1 1 1 1 1 2 3 6 10 20 36 72 136 272 528 1 2 3 6 10 20 36 72 136 272 528 1 3 6 18 45 135 378 1134 3321 9963 29646 1 3 6 18 45 135 378 1134 3321 9963 29646 1 4 10 40 136 544 2080 8320 32896 131584 524800 1 4 10 40 136 544 2080 8320 32896 131584 524800 1 5 15 75 325 1625 7875 39375 195625 978125 4884375 1 5 15 75 325 1625 7875 39375 195625 978125 4884375 1 6 21 126 666 3996 23436 140616 840456 5042736 30236976 1 6 21 126 666 3996 23436 140616 840456 5042736 30236976 1 7 28 196 1225 8575 58996 412972 2883601 20185207 141246028 1 7 28 196 1225 8575 58996 412972 2883601 20185207 141246028 1 8 36 288 2080 16640 131328 1050624 8390656 67125248 536887296 1 8 36 288 2080 16640 131328 1050624 8390656 67125248 536887296 1 9 45 405 3321 29889 266085 2394765 21526641 193739769 1743421725 1 9 45 405 3321 29889 266085 2394765 21526641 193739769 1743421725 1 10 55 550 5050 50500 500500 5005000 50005000 500050000 5000050000
Formula
For n >= 3 and k >= 2, T(n,k) = (floor(n/2)^(k-2) + floor(n/2)^(floor(k-1)/2))/2.
For n even, T(n, 2)=1, if k is odd T(n,k)=(n/2)*T(n,k-1), if k is even T(n,k)=(n/2)*T(n,k-1)-((n-2)/4)*(n/2)^((k-2)/2).
Comments