cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A185722 #28 Oct 08 2017 20:41:41
%S A185722 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 A185722 120,127,1,47,131,191,223,239,247,255,1,76,241,367,439,475,493,502,
%U A185722 511,1,123,443,708,863,943,983,1003,1013,1023
%N A185722 Triangle read by rows: The number of m-path covers of the n-cycle C_n.
%C A185722 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 A185722 Andrew Howroyd, <a href="/A185722/b185722.txt">Table of n, a(n) for n = 1..1275</a>
%H A185722 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 A185722 T(n,m) = A247505(m, n). - _Andrew Howroyd_, Oct 08 2017
%e A185722 The triangle begins:
%e A185722   1,
%e A185722   1,   3;
%e A185722   1,   4,   7;
%e A185722   1,   7,  11,  15;
%e A185722   1,  11,  21,  26,  31;
%e A185722   1,  18,  39,  51,  57,  63;
%e A185722   1,  29,  71,  99, 113, 120, 127;
%e A185722   1,  47, 131, 191, 223, 239, 247,  255;
%e A185722   1,  76, 241, 367, 439, 475, 493,  502,  511;
%e A185722   1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023;
%e A185722 An m-path cover of a graph G is a covering of the vertices of G by paths of length at most m.
%e A185722 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 A185722 If we include the starting conditions c_m(i) = 2^i - 1, 1 <= i <= m, we get the following square:
%e A185722   1,   1,   1,   1,   1,   1,   1,    1,    1,    1 ...
%e A185722   1,   3,   3,   3,   3,   3,   3,    3,    3,    3 ...
%e A185722   1,   4,   7,   7,   7,   7,   7,    7,    7,    7 ...
%e A185722   1,   7,  11,  15,  15,  15,  15,   15,   15,   15 ...
%e A185722   1,  11,  21,  26,  31,  31,  31,   31,   31,   31 ...
%e A185722   1,  18,  39,  51,  57,  63,  63,   63,   63,   63 ...
%e A185722   1,  29,  71,  99, 113, 120, 127,  127,  127,  127 ...
%e A185722   1,  47, 131, 191, 223, 239, 247,  255,  255,  255 ...
%e A185722   1,  76, 241, 367, 439, 475, 493,  502,  511,  511 ...
%e A185722   1, 123, 443, 708, 863, 943, 983, 1003, 1013, 1023 ...
%e A185722   ...
%e A185722 Column m of the above square is formed from an m-anacci recurrence.
%o A185722 (PARI) \\ after Maple in A247505
%o A185722 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 A185722 for(n=1, 10, for(m=1, n, print1(T(n,m), ", ")); print) \\ _Andrew Howroyd_, Oct 08 2017
%Y A185722 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 A185722 Cf. A247505.
%K A185722 nonn,tabl
%O A185722 1,3
%A A185722 _John P. McSorley_, Jul 10 2012
%E A185722 Terms a(37) and beyond from _Andrew Howroyd_, Oct 08 2017