A109502 Array read by antidiagonals: T(m,n) is the number of closed walks of length n on the complete graph on m nodes, m >= 1, n >= 0.

1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 3, 2, 1, 0, 1, 0, 4, 6, 6, 0, 0, 1, 0, 5, 12, 21, 10, 1, 0, 1, 0, 6, 20, 52, 60, 22, 0, 0, 1, 0, 7, 30, 105, 204, 183, 42, 1, 0, 1, 0, 8, 42, 186, 520, 820, 546, 86, 0, 0, 1, 0, 9, 56, 301, 1110, 2605, 3276, 1641, 170, 1, 0

Offset

1,13

Links

Table of n, a(n) for n=1..78.

Formula

T(m,n) = ((m-1)^n + (m-1)(-1)^n)/m.

G.f.: T(m, n) = [z^n](1 - (m-2)z)/(1 - (m-2)z - (m-1)z^2).

Example

Array begins:
  m\n| 0  1  2  3   4    5     6      7       8        9        10
  ---+------------------------------------------------------------
   1 | 1  0  0  0   0    0     0      0       0        0         0
   2 | 1  0  1  0   1    0     1      0       1        0         1
   3 | 1  0  2  2   6   10    22     42      86      170       342
   4 | 1  0  3  6  21   60   183    546    1641     4920     14763
   5 | 1  0  4 12  52  204   820   3276   13108    52428    209716
   6 | 1  0  5 20 105  520  2605  13020   65105   325520   1627605
   7 | 1  0  6 30 186 1110  6666  39990  239946  1439670   8638026
   8 | 1  0  7 42 301 2100 14707 102942  720601  5044200  35309407
   9 | 1  0  8 56 456 3640 29128 233016 1864136 14913080 119304648
  10 | 1  0  9 72 657 5904 53145 478296 4304673 38742048 348678441

Crossrefs

Rows are A078008, A054878, A109499, A109500, A109501.

Sequence in context: A306605 A363929 A054876 * A323887 A349913 A346236

Adjacent sequences: A109499 A109500 A109501 * A109503 A109504 A109505

Keyword

nonn,easy,tabl

Author

Mitch Harris, Jun 30 2005

Extensions

Corrected by Franklin T. Adams-Watters, Sep 18 2006

Status

approved