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

Comments

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.

Links

Table of n, a(n) for n=3..68.

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

Example

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

Crossrefs

Sequence in context: A334997 A030111 A096921 * A275416 A037161 A202175

Adjacent sequences: A308200 A308201 A308202 * A308204 A308205 A308206

Keyword

easy,nonn,tabl

Author

Christian Barrientos, May 15 2019

Status

approved