OFFSET
0,2
COMMENTS
A partition of an undirected graph G=(V,E) into bus routes is a collection of edge-disjoint undirected paths in G such that (i) no two of the paths can be concatenated to form a new path; (ii) the union of the edges from all paths is E. In each path, the vertices may be repeated, but not the edges.
This is an undirected analog of partitions into strokes, which are defined in A089243.
Here, the n X 1 grid is the product P_{n+1} x P_2 of two paths with n and 1 edges respectively.
The first differences 10, 90, 800, 7100, 63000, 559000,... are A177187 multiplied by powers of 10. - R. J. Mathar, Nov 02 2016
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (11,-20,10).
FORMULA
For n>=3, a(n) = 10*(a(n-1)-a(n-2)) + 4. - Max Alekseyev, Apr 25 2013
G.f.: -(20*x^3-10*x^2-7*x+1) / ((x-1)*(10*x^2-10*x+1)). - Colin Barker, Feb 11 2015
E.g.f.: 4*exp(x) - 2 - exp(5*x)*(3*cosh(sqrt(15)*x) - sqrt(15)*sinh(sqrt(15)*x))/3. - Stefano Spezia, Jan 23 2026
MATHEMATICA
LinearRecurrence[{11, -20, 10}, {1, 4, 14, 104}, 30] (* Paolo Xausa, Jan 22 2026 *)
PROG
(PARI) Vec(-(20*x^3-10*x^2-7*x+1)/((x-1)*(10*x^2-10*x+1)) + O(x^100)) \\ Colin Barker, Feb 11 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yasutoshi Kohmoto, Oct 03 2007, revised Nov 20 2007
EXTENSIONS
Terms a(4) onward from Max Alekseyev, Apr 25 2013
Missing a(1) inserted and entry edited by Andrei Zabolotskii, Jan 21 2026
STATUS
approved