%I #17 Nov 02 2016 15:40:12

%S 1,14,104,904,8004,71004,630004,5590004,49600004,440100004,3905000004,

%T 34649000004,307440000004,2727910000004,24204700000004,

%U 214767900000004,1905632000000004,16908641000000004,150030090000000004,1331214490000000004,11811844000000000004,104806295100000000004,929944511000000000004,8251382159000000000004,73214376480000000000004,649629943210000000000004

%N Number of partitions into "bus routes" of an n X 1 grid.

%C If we make bus routes on a graph G, the routes should satisfy the following conditions.

%C 1. One and only one route exists on all edges of G

%C 2. Terminals of two different routes don't meet on the same point

%C This definition is equivalent to a "partition of graph G into undirected strokes". It is defined as follows.

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

%C So the case of undirected paths is the following.

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

%C The first differences 90, 800, 7100, 63000, 559000,... are A177187 multiplied by powers of 10. - _R. J. Mathar_, Nov 02 2016

%H Colin Barker, <a href="/A131709/b131709.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (11,-20,10).

%F 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:

%F v_i E V_n, G_n={V_n,E_n}, "E" means element

%F m_i means number of matching of incident edges of v_i

%F c_j means cycles in G_n

%F se_j means number of start-end points in c_j

%F v_k E G_n and not(v_k E c_j)

%F m_k means number of matching of incident edges of v_k

%F If (G_n-c_j) is empty then Product_{v_k E (G_n-c_j)} m_k = 1.

%F For n>=3, a(n)=10*(a(n-1)-a(n-2))+4. - _Max Alekseyev_, Apr 25 2013

%F G.f.: -(30*x^3-30*x^2+3*x+1) / ((x-1)*(10*x^2-10*x+1)). - _Colin Barker_, Feb 11 2015

%o (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

%Y Cf. A131518.

%K nonn,easy

%O 0,2

%A _Yasutoshi Kohmoto_, Oct 03 2007, revised Nov 20 2007

%E Terms a(4) onward from _Max Alekseyev_, Apr 25 2013