cp's OEIS Frontend

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

%I A131709 #17 Nov 02 2016 15:40:12
%S A131709 1,14,104,904,8004,71004,630004,5590004,49600004,440100004,3905000004,
%T A131709 34649000004,307440000004,2727910000004,24204700000004,
%U A131709 214767900000004,1905632000000004,16908641000000004,150030090000000004,1331214490000000004,11811844000000000004,104806295100000000004,929944511000000000004,8251382159000000000004,73214376480000000000004,649629943210000000000004
%N A131709 Number of partitions into "bus routes" of an n X 1 grid.
%C A131709 If we make bus routes on a graph G, the routes should satisfy the following conditions.
%C A131709 1. One and only one route exists on all edges of G
%C A131709 2. Terminals of two different routes don't meet on the same point
%C A131709 This definition is equivalent to a "partition of graph G into undirected strokes". It is defined as follows.
%C A131709 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 A131709 So the case of undirected paths is the following.
%C A131709 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 A131709 The first differences 90, 800, 7100, 63000, 559000,... are A177187 multiplied by powers of 10. - _R. J. Mathar_, Nov 02 2016
%H A131709 Colin Barker, <a href="/A131709/b131709.txt">Table of n, a(n) for n = 0..1000</a>
%H A131709 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (11,-20,10).
%F A131709 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 A131709 v_i E V_n, G_n={V_n,E_n}, "E" means element
%F A131709 m_i means number of matching of incident edges of v_i
%F A131709 c_j means cycles in G_n
%F A131709 se_j means number of start-end points in c_j
%F A131709 v_k E G_n and not(v_k E c_j)
%F A131709 m_k means number of matching of incident edges of v_k
%F A131709 If (G_n-c_j) is empty then Product_{v_k E (G_n-c_j)} m_k = 1.
%F A131709 For n>=3, a(n)=10*(a(n-1)-a(n-2))+4. - _Max Alekseyev_, Apr 25 2013
%F A131709 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 A131709 (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 A131709 Cf. A131518.
%K A131709 nonn,easy
%O A131709 0,2
%A A131709 _Yasutoshi Kohmoto_, Oct 03 2007, revised Nov 20 2007
%E A131709 Terms a(4) onward from _Max Alekseyev_, Apr 25 2013