A131518 Number of partitions of the graph G_n (defined below) into "strokes".

2, 6, 14, 122, 362, 5282, 20582, 397154, 2027090, 46177922, 303147902, 7699478162, 63517159994, 1745540360930, 17676592058582, 517137940132802, 6290714838241442, 194139271606482434, 2782486941099788270, 90105513853333901042, 1495993248737211995402, 50671468195931300884322

Offset: 1

Author

Yasutoshi Kohmoto, Aug 15 2007, Oct 03 2007

Keywords

• nonn

Comments

Here G_n = {V_n, E_n}, V_n = {v_1, v_2}, E_n = {e_1, e_2, ..., e_n}; for all i, e_i = v_1v_2.

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.

Examples

			G_2 : o=o, two edges exist between v_1 and v_2.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..440
• R. J. Mathar, Explanation of the Alekseyev formula

Crossrefs

Cf. A131520, A354228.

Programs

Mathematica

f[n_, k_]:= If[EvenQ[n-k], Binomial[(n+k)/2, k], 0];
A088009[n_]:= n!*Sum[f[n-1, k-1]/k!, {k, 0, n}];
A131518[n_]:= If[EvenQ[n], 2*A088009[n] + n!*(n/2 +1), 2*A088009[n]];
Table[A131518[n], {n,1,30}] (* G. C. Greubel, Feb 14 2021 *)

Sage

def f(n, k): return binomial((n+k)/2, k) if (n-k)%2==0 else 0
def A088009(n): return factorial(n)*sum(f(n-1, k-1)/factorial(k) for k in (0..n))
def A131518(n): return 2*A088009(n) + (n/2 +1)*factorial(n) if (n%2==0) else 2*A088009(n)
[A131518(n) for n in (1..30)] # G. C. Greubel, Feb 14 2021

Formula

For odd n, a(n)=2*A088009(n); for even n, a(n)=2*A088009(n)+n!*(n/2+1). The first term stands for partitions with paths starting and ending in different vertices. The second term (that exists only for even n) stands for partitions with paths starting and ending at the same vertex (there are at most 2 such paths starting and ending in v_1 and v_2 respectively, each path consists of even number of edges). - Max Alekseyev, Sep 29 2007

Extensions

More terms from Max Alekseyev, Sep 29 2007