A106234 -id:A106234 - cp's OEIS frontend

A368835 Number of unlabeled n-edge loop-graphs with at most n vertices such that it is not possible to choose a different vertex from each edge.

0, 0, 0, 1, 5, 23, 98, 394, 1560, 6181, 24655, 99701, 410513, 1725725, 7423757, 32729320, 148027044, 687188969, 3275077017, 16022239940, 80431483586, 414094461610, 2185052929580, 11808696690600, 65312048149993, 369408792148714, 2135111662435080, 12601466371445619

Offset: 0

Gus Wiseman, Jan 13 2024

nonn

			Non-isomorphic representatives of the a(4) = 5 loop-graphs:
  {{1,1},{2,2},{3,3},{1,2}}
  {{1,1},{2,2},{1,2},{1,3}}
  {{1,1},{2,2},{1,2},{3,4}}
  {{1,1},{2,2},{1,3},{2,3}}
  {{1,1},{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The case of a unique choice is A000081, row sums of A106234.
The labeled version is A368596, covering A368730.
Without the choice condition we have A368598.
The complement is A368984, row sums of A368926.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A116508, A129271, A133686, A137916, A137917, A333331, A367863, A368836, A368924, A368927.

Table[Length[Union[sysnorm /@ Select[Subsets[Subsets[Range[n],{1,2}],{n}],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A368598(n) - A368984(n). - Andrew Howroyd, Jan 14 2024

a(8) onwards from Andrew Howroyd, Jan 14 2024

A368926 Triangle read by rows where T(n,k) is the number of unlabeled loop-graphs on n vertices with k loops and n-k non-loops such that it is possible to choose a different element from each edge.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 2, 1, 1, 2, 5, 3, 1, 1, 5, 12, 7, 3, 1, 1, 14, 29, 19, 8, 3, 1, 1, 35, 75, 47, 21, 8, 3, 1, 1, 97, 191, 127, 54, 22, 8, 3, 1, 1, 264, 504, 331, 149, 56, 22, 8, 3, 1, 1, 733, 1339, 895, 395, 156, 57, 22, 8, 3, 1, 1

Offset: 0

Gus Wiseman, Jan 13 2024

Also the number of unlabeled loop-graphs covering n vertices with k loops and n-k non-loops such that each connected component has the same number of edges as vertices.

			Triangle begins:
   1
   0  1
   0  1  1
   1  2  1  1
   2  5  3  1  1
   5 12  7  3  1  1
  14 29 19  8  3  1  1
  35 75 47 21  8  3  1  1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

The case of a unique choice is A106234, row sums A000081.
Column k = 0 is A137917, labeled version A137916.
Without the choice condition we have A368836.
The labeled version is A368924, row sums maybe A333331.
Row sums are A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A057500, A116508, A133686, A367863, A367869, A368596, A368597, A368598, A368601, A368836, A368927.

Table[Length[Union[sysnorm /@ Select[Subsets[Subsets[Range[n],{1,2}],{n}],Count[#,{_}]==k && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]], {n,0,5},{k,0,n}]

\\ TreeGf gives gf of A000081; G(n,1) is gf of A368983.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
G(n,y)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); 1 + (sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2 - (g(1)^2 + g(2)))/2 + (y-1)*g(1)}
EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
T(n)={[Vecrev(p) | p <- Vec(EulerMTS(G(n,y) - 1))]}
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 14 2024

a(36) onwards from Andrew Howroyd, Jan 14 2024

A106236 Triangle of the numbers of different forests with m rooted trees having distinct orders.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 4, 2, 0, 0, 9, 6, 0, 0, 0, 20, 13, 2, 0, 0, 0, 48, 37, 4, 0, 0, 0, 0, 115, 86, 17, 0, 0, 0, 0, 0, 286, 239, 46, 0, 0, 0, 0, 0, 0, 719, 577, 142, 8, 0, 0, 0, 0, 0, 0, 1842, 1607, 367, 18, 0, 0, 0, 0, 0, 0, 0, 4766, 4025, 1136, 76, 0, 0, 0, 0, 0, 0, 0, 0, 12486, 11185, 2945, 248, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Washington Bomfim, Apr 28 2005

a(n) = 0 if and only if n < m + (((1+m)*m - 1)^2 -1)/8, where m is the number of trees in the forests counted by a(n).

			a(3) = 0 because m = 2 and (see comments) 3 < (2 + 3).
a(4) > 0 because m = 1. Note that (((1+m)*m - 1)^2 -1)/8 = 0, if m = 1. It is clear that n >= m.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000081, A106234.

with(numtheory):
g:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      expand(add(x^j*b(n-i*j, i-1)*binomial(g(i)+j-1, j),
      j=0..min(1, n/i)))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Jun 25 2014

g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Expand[Sum[x^j*b[n - i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0,Min[1, n/i]}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Feb 23 2015, after Alois P. Heinz *)

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m distinct parts, of Product_{i=1..N}binomial(A000081(i)+Ki-1, Ki). Because all the multiplicities of the parts of the considered partitions are 1, or 0, we can simplify the formula to a(n)= sum over the partitions of N with exactly m distinct parts, of Product_{i=1..N}A000081(i). (Naturally, we do not consider the parts with multiplicity 0.)

G.f.: Product_{k>0} (1 + y*A000081(k)*x^k). - Vladeta Jovovic, May 14 2005

A106235 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices.

Original entry on oeis.org

0, 1, 0, 2, 0, 0, 4, 1, 0, 0, 9, 2, 0, 0, 0, 20, 7, 1, 0, 0, 0, 48, 17, 2, 0, 0, 0, 0, 115, 48, 7, 1, 0, 0, 0, 0, 286, 124, 21, 2, 0, 0, 0, 0, 0, 719, 336, 60, 7, 1, 0, 0, 0, 0, 0, 1842, 888, 171, 21, 2, 0, 0, 0, 0, 0, 0, 4766, 2393, 488, 65, 7, 1, 0, 0, 0, 0, 0, 0

Offset: 1

Washington Bomfim, Apr 26 2005

Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree. A033185(n) = A106235(n) + A106234(n).

			a(12)=2 because 5 nodes can be partitioned in two trees only in a way: one tree gets 3 nodes and the other tree gets 2. Since A000081(3) = 2 and A000081(2)=1, there are two forests.
Triangle T(n,k) begins:
    0;
    1,   0;
    2,   0,  0;
    4,   1,  0, 0;
    9,   2,  0, 0, 0;
   20,   7,  1, 0, 0, 0;
   48,  17,  2, 0, 0, 0, 0;
  115,  48,  7, 1, 0, 0, 0, 0;
  286, 124, 21, 2, 0, 0, 0, 0, 0;
  719, 336, 60, 7, 1, 0, 0, 0, 0, 0;

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A033185, A106234.

with(numtheory):
g:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1,
      0, expand(add(x^j*b(n-i*j, i-1)*
      binomial(g(i)+j-1, j), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Jun 25 2014

g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 1, 0, Expand[Sum[x^j*b[n-i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0, n/i}]]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 05 2015, after Alois P. Heinz *)

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and no part equal to 1, of Product_{i=1..N} binomial(A000081(i)+Ki-1, Ki).

cp's OEIS Frontend

A368835 Number of unlabeled n-edge loop-graphs with at most n vertices such that it is not possible to choose a different vertex from each edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A368926 Triangle read by rows where T(n,k) is the number of unlabeled loop-graphs on n vertices with k loops and n-k non-loops such that it is possible to choose a different element from each edge.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A106236 Triangle of the numbers of different forests with m rooted trees having distinct orders.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A106235 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula