cp's OEIS Frontend

A144161 Triangle read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges that are node-disjoint unions of undirected cycle subgraphs.

%I A144161 #26 May 30 2021 09:57:21
%S A144161 1,1,0,1,0,0,1,0,0,1,1,0,0,4,3,1,0,0,10,15,12,1,0,0,20,45,72,70,1,0,0,
%T A144161 35,105,252,490,465,1,0,0,56,210,672,1960,3720,3507,1,0,0,84,378,1512,
%U A144161 5880,16740,31563,30016,1,0,0,120,630,3024,14700,55800,157815,300160,286884
%N A144161 Triangle read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges that are node-disjoint unions of undirected cycle subgraphs.
%H A144161 Alois P. Heinz, <a href="/A144161/b144161.txt">Rows n = 0..140, flattened</a>
%F A144161 T(n,0) = 1, T(n,k) = 0 if k<0 or n<k, else T(n,k) = T(n-1,k) + 1/2 * Sum_{j=2..k} T(n-1-j,k-j-1) * Product_{i=1..j} (n-i).
%e A144161 T(4,3) = 4, because there are 4 simple graphs with 3 edges that are node-disjoint unions of undirected cycle subgraphs:
%e A144161   .1.2. .1.2. .1-2. .1-2.
%e A144161   ../|. .|\.. ..\|. .|/..
%e A144161   .3-4. .3-4. .3.4. .3.4.
%e A144161 T(6,6) = C(6,3)/2+5!/2 = 70.
%e A144161 Triangle begins:
%e A144161   1;
%e A144161   1, 0;
%e A144161   1, 0, 0;
%e A144161   1, 0, 0,  1;
%e A144161   1, 0, 0,  4,  3;
%e A144161   1, 0, 0, 10, 15, 12;
%e A144161   1, 0, 0, 20, 45, 72, 70;
%e A144161   ...
%p A144161 T:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n<k then 0 else T(n-1,k) +add(mul(n-i, i=1..j) *T(n-1-j, k-j-1), j=2..k)/2 fi end: seq(seq(T(n,k), k=0..n), n=0..12);
%t A144161 T[n_, k_] := T[n, k] = Module[{i, j}, If[k == 0, 1, If[k < 0 || n < k, 0, T[n - 1, k] + Sum[Product[n - i, {i, 1, j}]*T[n - 1 - j, k - j - 1], {j, 2, k}]/2 ]]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 27 2013, translated from Maple *)
%o A144161 (Python)
%o A144161 from sympy.core.cache import cacheit
%o A144161 from operator import mul
%o A144161 from functools import reduce
%o A144161 @cacheit
%o A144161 def T(n, k): return 1 if k==0 else 0 if k<0 or n<k else T(n - 1, k) + sum([reduce(mul, [n - i for i in range(1, j + 1)])*T(n - 1 - j, k - j - 1) for j in range(2, k + 1)])//2
%o A144161 for n in range(21): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Aug 07 2017
%Y A144161 Columns k=0, 1+2, 3-4 give: A000012, A000004, A000292, A050534.
%Y A144161 Main diagonal gives A001205.
%Y A144161 Row sums give: A108246.
%Y A144161 Cf. A007318, A000142.
%K A144161 nonn,tabl
%O A144161 0,14
%A A144161 _Alois P. Heinz_, Sep 12 2008