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

Author

John P. McSorley, Jul 10 2012

Keywords

• nonn
• tabl

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.

Examples

			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.
		

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.

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.

Programs

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

Formula

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

Extensions

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