A185722 Triangle read by rows: The number of m-path covers of the n-cycle C_n.

1, 1, 3, 1, 4, 7, 1, 7, 11, 15, 1, 11, 21, 26, 31, 1, 18, 39, 51, 57, 63, 1, 29, 71, 99, 113, 120, 127, 1, 47, 131, 191, 223, 239, 247, 255, 1, 76, 241, 367, 439, 475, 493, 502, 511, 1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023

Offset

1,3

Comments

Let c_m(n) be the number of m-path covers of the n-cycle C_n. Then form the triangle where c_m(n) is the (n,m) entry. This sequence is this triangle when read by rows, for n >= 1 and 1 <= m <= n.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

John P. McSorley and Philip Feinsilver, The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences, International Journal of Combinatorics, Volume 2014 (2014), Article ID 258017, 13 pages.

Formula

T(n,m) = A247505(m, n). - Andrew Howroyd, Oct 08 2017

Example

The triangle begins:
  1,
  1,   3;
  1,   4,   7;
  1,   7,  11,  15;
  1,  11,  21,  26,  31;
  1,  18,  39,  51,  57,  63;
  1,  29,  71,  99, 113, 120, 127;
  1,  47, 131, 191, 223, 239, 247,  255;
  1,  76, 241, 367, 439, 475, 493,  502,  511;
  1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023;
An m-path cover of a graph G is a covering of the vertices of G by paths of length at most m.
The length of a path is the number of vertices in it. Let C_4 have vertices {1, 2, 3, 4} then c_3(4) = 11 because C_4 has 11 3-path covers: 1, 2, 3, 4; 12, 3, 4; 23, 1, 4; 34, 1, 2; 14, 2, 3; 12, 34; 14, 23; 123, 4; 234, 1; 143, 2; 214, 3. Here an m-path and its reverse are considered to be the same m-path.
If we include the starting conditions c_m(i) = 2^i - 1, 1 <= i <= m, we get the following square:
  1,   1,   1,   1,   1,   1,   1,    1,    1,    1 ...
  1,   3,   3,   3,   3,   3,   3,    3,    3,    3 ...
  1,   4,   7,   7,   7,   7,   7,    7,    7,    7 ...
  1,   7,  11,  15,  15,  15,  15,   15,   15,   15 ...
  1,  11,  21,  26,  31,  31,  31,   31,   31,   31 ...
  1,  18,  39,  51,  57,  63,  63,   63,   63,   63 ...
  1,  29,  71,  99, 113, 120, 127,  127,  127,  127 ...
  1,  47, 131, 191, 223, 239, 247,  255,  255,  255 ...
  1,  76, 241, 367, 439, 475, 493,  502,  511,  511 ...
  1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023 ...
  ...
Column m of the above square is formed from an m-anacci recurrence.

Prog

(PARI) \\ after Maple in A247505
T(n, m)=(-1)^n * polcoeff(Pol(deriv(log((1+sum(j=1, m, (-1)^(j+1)*x^j + O(x^(n+1))))^(-1)))), n-1);
for(n=1, 10, for(m=1, n, print1(T(n, m), ", ")); print) \\ Andrew Howroyd, Oct 08 2017

Crossrefs

The (n, m) entry of the triangle formed from sequence A126198 counts the compositions of the integer n in which each part is at most m. In our terminology this is the number of m-path covers of the path P_n with n vertices. The (m, m) term in the triangle formed from sequence A126198 is 2^(m - 1), in our triangle above the (m, m) term is 2^m - 1. Column m of the corresponding square of sequence A126198 also obeys an m-anacci recurrence, as above. Each of the 10 columns of the above square array appears as a sequence: for example, the second column (m = 2) is sequence A000204, and the third column (m = 3) is sequence A001644, etc.

Cf. A247505.

Sequence in context: A350584 A208339 A328463 * A287376 A209418 A193969

Adjacent sequences: A185719 A185720 A185721 * A185723 A185724 A185725

Keyword

nonn,tabl

Author

John P. McSorley, Jul 10 2012

Extensions

Terms a(37) and beyond from Andrew Howroyd, Oct 08 2017

Status

approved