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

1, 14, 104, 904, 8004, 71004, 630004, 5590004, 49600004, 440100004, 3905000004, 34649000004, 307440000004, 2727910000004, 24204700000004, 214767900000004, 1905632000000004, 16908641000000004, 150030090000000004, 1331214490000000004, 11811844000000000004, 104806295100000000004, 929944511000000000004, 8251382159000000000004, 73214376480000000000004, 649629943210000000000004

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

Cf. A131518.

Sequence in context: A266561 A370962 A222369 * A139614 A068390 A162632

Adjacent sequences: A131706 A131707 A131708 * A131710 A131711 A131712

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