cp's OEIS Frontend

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

%I A131518 #13 Jul 18 2022 20:42:42
%S A131518 2,6,14,122,362,5282,20582,397154,2027090,46177922,303147902,
%T A131518 7699478162,63517159994,1745540360930,17676592058582,517137940132802,
%U A131518 6290714838241442,194139271606482434,2782486941099788270,90105513853333901042,1495993248737211995402,50671468195931300884322
%N A131518 Number of partitions of the graph G_n (defined below) into "strokes".
%C A131518 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.
%C A131518 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.
%H A131518 G. C. Greubel, <a href="/A131518/b131518.txt">Table of n, a(n) for n = 1..440</a>
%H A131518 R. J. Mathar, <a href="/A131518/a131518.pdf">Explanation of the Alekseyev formula</a>
%F A131518 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
%e A131518 G_2 : o=o, two edges exist between v_1 and v_2.
%t A131518 f[n_, k_]:= If[EvenQ[n-k], Binomial[(n+k)/2, k], 0];
%t A131518 A088009[n_]:= n!*Sum[f[n-1, k-1]/k!, {k, 0, n}];
%t A131518 A131518[n_]:= If[EvenQ[n], 2*A088009[n] + n!*(n/2 +1), 2*A088009[n]];
%t A131518 Table[A131518[n], {n,1,30}] (* _G. C. Greubel_, Feb 14 2021 *)
%o A131518 (Sage)
%o A131518 def f(n, k): return binomial((n+k)/2, k) if (n-k)%2==0 else 0
%o A131518 def A088009(n): return factorial(n)*sum(f(n-1, k-1)/factorial(k) for k in (0..n))
%o A131518 def A131518(n): return 2*A088009(n) + (n/2 +1)*factorial(n) if (n%2==0) else 2*A088009(n)
%o A131518 [A131518(n) for n in (1..30)] # _G. C. Greubel_, Feb 14 2021
%Y A131518 Cf. A131520, A354228.
%K A131518 nonn
%O A131518 1,1
%A A131518 _Yasutoshi Kohmoto_, Aug 15 2007, Oct 03 2007
%E A131518 More terms from _Max Alekseyev_, Sep 29 2007