|
%I #27 Sep 28 2019 21:58:06
%S 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,
%T 18,45,20,36,1,1,5,10,40,45,135,36,72,1,1,5,15,40,136,135,378,72,136,
%U 1,1,6,15,75,136,544,378,1134,136,272,1
%N Array read by ascending antidiagonals: T(n,k) = number of non-isomorphic kC_n-snakes for n >= 3 and k >= 2.
%C A kC_n-snake is a connected graph in which the k >= 2 blocks are isomorphic to the cycle C_n and the block-cutpoint graph is a path.
%F For n >= 3 and k >= 2, T(n,k) = (floor(n/2)^(k-2) + floor(n/2)^(floor(k-1)/2))/2.
%F 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).
%e T(n,2)=1 because there is only one way to connect two copies of C_n.
%e 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.
%e 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.
%e Table begins:
%e 1 1 1 1 1 1 1 1 1 1 1
%e 1 2 3 6 10 20 36 72 136 272 528
%e 1 2 3 6 10 20 36 72 136 272 528
%e 1 3 6 18 45 135 378 1134 3321 9963 29646
%e 1 3 6 18 45 135 378 1134 3321 9963 29646
%e 1 4 10 40 136 544 2080 8320 32896 131584 524800
%e 1 4 10 40 136 544 2080 8320 32896 131584 524800
%e 1 5 15 75 325 1625 7875 39375 195625 978125 4884375
%e 1 5 15 75 325 1625 7875 39375 195625 978125 4884375
%e 1 6 21 126 666 3996 23436 140616 840456 5042736 30236976
%e 1 6 21 126 666 3996 23436 140616 840456 5042736 30236976
%e 1 7 28 196 1225 8575 58996 412972 2883601 20185207 141246028
%e 1 7 28 196 1225 8575 58996 412972 2883601 20185207 141246028
%e 1 8 36 288 2080 16640 131328 1050624 8390656 67125248 536887296
%e 1 8 36 288 2080 16640 131328 1050624 8390656 67125248 536887296
%e 1 9 45 405 3321 29889 266085 2394765 21526641 193739769 1743421725
%e 1 9 45 405 3321 29889 266085 2394765 21526641 193739769 1743421725
%e 1 10 55 550 5050 50500 500500 5005000 50005000 500050000 5000050000
%K easy,nonn,tabl
%O 3,5
%A _Christian Barrientos_, May 15 2019
|
