OFFSET
0,2
COMMENTS
If we make bus routes on a graph G, the routes should satisfy the following conditions.
1. One and only one route exists on all edges of G
2. Terminals of two different routes don't meet on the same point
This definition is equivalent to a "partition of graph G into undirected strokes". It is defined as follows.
Given an undirected graph G=(V,E), its partition into strokes is a collection of directed edge-disjoint paths (viewed as sets of directed edges) on V such that (i) union of any two paths is not a path; (ii)union of corresponding undirected paths is E.
So the case of undirected paths is the following.
Definition. Given an undirected graph G=(V,E), its partition into strokes is a collection of edge-disjoint paths (viewed as sets of edges) on V such that (i) union of any two paths is not a path; (ii) union of paths is E.
The first differences 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
a(n) = Product_{v_i} m_i + Sum_{c_j} (se_j - 1)*(Product_{v_k E (G_n-c_j)} m_k - {number of partitions of (G_n-c_i) which has cycles}) where:
v_i E V_n, G_n={V_n,E_n}, "E" means element
m_i means number of matching of incident edges of v_i
c_j means cycles in G_n
se_j means number of start-end points in c_j
v_k E G_n and not(v_k E c_j)
m_k means number of matching of incident edges of v_k
If (G_n-c_j) is empty then Product_{v_k E (G_n-c_j)} m_k = 1.
For n>=3, a(n)=10*(a(n-1)-a(n-2))+4. - Max Alekseyev, Apr 25 2013
G.f.: -(30*x^3-30*x^2+3*x+1) / ((x-1)*(10*x^2-10*x+1)). - Colin Barker, Feb 11 2015
PROG
(PARI) Vec(-(30*x^3-30*x^2+3*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
STATUS
approved