login
A185722
Triangle read by rows: The number of m-path covers of the n-cycle C_n.
1
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
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
KEYWORD
nonn,tabl
AUTHOR
John P. McSorley, Jul 10 2012
EXTENSIONS
Terms a(37) and beyond from Andrew Howroyd, Oct 08 2017
STATUS
approved