A185722 - OEIS

%I #28 Oct 08 2017 20:41:41

%S 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,

%T 120,127,1,47,131,191,223,239,247,255,1,76,241,367,439,475,493,502,

%U 511,1,123,443,708,863,943,983,1003,1013,1023

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

%C 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.

%H Andrew Howroyd, <a href="/A185722/b185722.txt">Table of n, a(n) for n = 1..1275</a>

%H John P. McSorley and Philip Feinsilver, <a href="http://dx.doi.org/10.1155/2014/258017">The m-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences</a>, International Journal of Combinatorics, Volume 2014 (2014), Article ID 258017, 13 pages.

%F T(n,m) = A247505(m, n). - _Andrew Howroyd_, Oct 08 2017

%e The triangle begins:

%e   1,

%e   1,   3;

%e   1,   4,   7;

%e   1,   7,  11,  15;

%e   1,  11,  21,  26,  31;

%e   1,  18,  39,  51,  57,  63;

%e   1,  29,  71,  99, 113, 120, 127;

%e   1,  47, 131, 191, 223, 239, 247,  255;

%e   1,  76, 241, 367, 439, 475, 493,  502,  511;

%e   1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023;

%e An m-path cover of a graph G is a covering of the vertices of G by paths of length at most m.

%e 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.

%e If we include the starting conditions c_m(i) = 2^i - 1, 1 <= i <= m, we get the following square:

%e   1,   1,   1,   1,   1,   1,   1,    1,    1,    1 ...

%e   1,   3,   3,   3,   3,   3,   3,    3,    3,    3 ...

%e   1,   4,   7,   7,   7,   7,   7,    7,    7,    7 ...

%e   1,   7,  11,  15,  15,  15,  15,   15,   15,   15 ...

%e   1,  11,  21,  26,  31,  31,  31,   31,   31,   31 ...

%e   1,  18,  39,  51,  57,  63,  63,   63,   63,   63 ...

%e   1,  29,  71,  99, 113, 120, 127,  127,  127,  127 ...

%e   1,  47, 131, 191, 223, 239, 247,  255,  255,  255 ...

%e   1,  76, 241, 367, 439, 475, 493,  502,  511,  511 ...

%e   1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023 ...

%e   ...

%e Column m of the above square is formed from an m-anacci recurrence.

%o (PARI) \\ after Maple in A247505

%o 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);

%o for(n=1, 10, for(m=1, n, print1(T(n,m), ", ")); print) \\ _Andrew Howroyd_, Oct 08 2017

%Y 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.

%Y Cf. A247505.

%K nonn,tabl

%O 1,3

%A _John P. McSorley_, Jul 10 2012

%E Terms a(37) and beyond from _Andrew Howroyd_, Oct 08 2017