A144228 -id:A144228 - cp's OEIS frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

1, 1, 2, 8, 57, 608, 8524, 145800, 2918123, 66617234, 1704913434, 48300128696, 1499864341015, 50648006463048, 1847622972848648, 72406232075624192, 3033607843748296089, 135313823447621913500, 6402077421524339766058, 320237988317922139148736

Offset: 0

Washington Bomfim, May 12 2008

The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.

Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once. The connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023

			Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table
   j|1|2|3| 4|  5|
----+-+-+-+--+---+
a(j)|1|1|4|31|347|
1*5 -> 5!1^5 / (1!^5 * 5!) = 1
2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
5*1 -> 5!347^1 / (5!^1 * 1!) = 347
Total 608

Alois P. Heinz, Table of n, a(n) for n = 0..386
Wikipedia, Pseudoforest

Cf. A129137, A005703, A000272, A057500, A137916, A001858.
Row sums of triangle A144228. - Alois P. Heinz, Sep 15 2008
Cf. A137352. - Vladeta Jovovic, Sep 16 2008
The unlabeled version is A134964.
The complement is counted by A367867, covering A367868, connected A140638.
The covering case is A367869, connected A129271.
For set-systems we have A367902, ranks A367906.
The complement for set-systems is A367903, ranks A367907.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts graphs by number of connected components.
Cf. A001187, A058891, A116508, A355740, A367769, A367770, A367863, A367901.

cy:= proc(n) option remember; binomial(n-1, 2)*
        add((n-3)!/(n-2-t)! *n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember;
      if k=0 then 1
    elif k<0 or n add(T(n,k), k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2),{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)

x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017

a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.
a(n) = Sum_{k=0..n} A144228(n,k). - Alois P. Heinz, Sep 15 2008
E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008
E.g.f.: A(x)*B(x) where A(x) is the e.g.f. for A137916 and B(x) is the e.g.f. for A001858. - Geoffrey Critzer, Mar 23 2013
a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013
E.g.f.: exp(B(x) - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023

Corrected and extended by Alois P. Heinz and Vladeta Jovovic, Sep 15 2008

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

Original entry on oeis.org

1, 0, 0, 1, 15, 222, 3670, 68820, 1456875, 34506640, 906073524, 26154657270, 823808845585, 28129686128940, 1035350305641990, 40871383866109888, 1722832666898627865, 77242791668604946560, 3670690919234354407000, 184312149879830557190940, 9751080154504005703189791

Offset: 0

Washington Bomfim, Feb 22 2008

Also the number of labeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. The version without the choice condition is A116508, covering A367863. - Gus Wiseman, Jan 25 2024

			a(6) = 3670 because A057500(6) = 3660 and two triangles can be labeled in 10 ways.
From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(4) = 15 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}
                        {12,13,14,24}
                        {12,13,14,34}
                        {12,13,23,24}
                        {12,13,23,34}
                        {12,13,24,34}
                        {12,14,23,24}
                        {12,14,23,34}
                        {12,14,24,34}
                        {12,23,24,34}
                        {13,14,23,24}
                        {13,14,23,34}
                        {13,14,24,34}
                        {13,23,24,34}
                        {14,23,24,34}
(End)

V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999.

Alois P. Heinz, Table of n, a(n) for n = 0..386 (terms n = 151..200 from Andrew Howroyd)
Eric Weisstein's World of Mathematics, Pseudoforest.
Wikipedia, Pseudoforest.

The connected case is A057500.
Row sums of A106239.
The unlabeled version is A137917.
Diagonal of A144228.
The version with loops appears to be A333331, unlabeled A368984.
Column k = 0 of A368924.
The complement is counted by A369143, unlabeled A369201, covering A369144.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable simple graphs, covering A367869.
A140637 counts unlabeled non-choosable graphs, covering A369202.
A367867 counts non-choosable graphs, covering A367868.
Cf. A001434, A006649, A053530, A116508, A129271, A134964, A140638, A367862, A367863, A369191.

cy:= proc(n) option remember;
       binomial(n-1, 2)*add((n-3)!/(n-2-t)!*n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember; `if`(k=0, 1, `if`(k<0 or n T(n,n):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 15 2008

nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]! CoefficientList[Series[Exp[Log[1/(1 - t)]/2 - t/2 - t^2/4], {x, 0, nn}], x], 1] (* Geoffrey Critzer, Jan 24 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

A057500(p) = (p-1)! * p^p /2 * sum(k = 3,p, 1/(p^k*(p-k)!)); /* Vladeta Jovovic, A057500. */
F(n,N) = { my(s = 0, K, D, Mc); forpart(P = n, D = Set(P); K = vector(#D);
for(i=1, #D, K[i] = #select(x->x == D[i], Vec(P)));
Mc = n!/prod(i=1,#D, K[i]!);
s += Mc * prod(i = 1, #D, A057500(D[i])^K[i] / ( D[i]!^K[i])) , [3, n], [N, N]); s };
a(n)= {my(N); sum(N = 1, n, F(n,N))};

seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-log(1+w)/2 + w/2 - w^2/4)))} \\ Andrew Howroyd, May 18 2021

a(n) = Sum_{N = 1..n} ((n!/N!) * Sum_{n_1 + n_2 + ... + n_N = n} Product_{i = 1..N} ( A057500(n_i) / n_i! ) ). [V. F. Kolchin p. 31, (1.4.2)] replacing numerator terms n_i^(n_i-2) by A057500(n_i).
a(n) = A144228(n,n). - Alois P. Heinz, Sep 15 2008
E.g.f.: exp(B(T(x))) where B(x) = (log(1/(1-x))-x-x^2/2)/2 and T(x) is the e.g.f. for A000169 (labeled rooted trees). - Geoffrey Critzer, Jan 24 2012
a(n) ~ 2^(-1/4)*exp(-3/4)*GAMMA(3/4)*n^(n-1/4)/sqrt(Pi) * (1-7*Pi/(12*GAMMA(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Aug 16 2013
E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A057500. - Andrew Howroyd, May 18 2021

a(0)=1 prepended by Andrew Howroyd, May 18 2021

A369828 Number of simple graphs on 2n labeled nodes with n edges where each maximally connected subgraph has at most one cycle.

Original entry on oeis.org

1, 1, 15, 455, 20475, 1220499, 90612753, 8055867105, 834505143615, 98716154311775, 13130233759131489, 1939826433518297961, 315169336802124178465, 55852728904993187133225, 10721612205253023622081875, 2216303140328629150998750435, 490841301461498403844464646155

Offset: 0

Alois P. Heinz, Feb 02 2024

nonn

All terms are odd.

Alois P. Heinz, Table of n, a(n) for n = 0..310

Cf. A144228.

a(n) = A144228(2n,n).

A217756 Triangular array read by rows: T(n,k) is the number of simple labeled graphs on n nodes with exactly k components where each component has at most one cycle; n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 4, 3, 1, 31, 19, 6, 1, 347, 195, 55, 10, 1, 4956, 2707, 720, 125, 15, 1, 85102, 46319, 12082, 2030, 245, 21, 1, 1698712, 930947, 242774, 40397, 4830, 434, 28, 1, 38562309, 21372678, 5620177, 938826, 112287, 10206, 714, 36, 1

Offset: 1

Geoffrey Critzer, Mar 23 2013

The Bell transform of A129271(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016
From Washington Bomfim, May 10 2020: (Start)
The second formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].
Some special cases of T(n,k) are
Column 2 = n! * Sum_{j=1..floor(n/2)} f(j)/j! * f(n-j)/(n-j)!, odd n.
           n!/2 *( (f(n/2)/(n/2)!)^2 + 2 * Sum_{j=1..floor(n/2)-1} f(j)/j! * f(n-j)/(n-j)!), even n.
Diagonal T(n,n-3) = 1/48*n^6 +1/48*n^5 -13/48*n^4 -37/48*n^3 +13/4*n^2 -9/4*n,
Diagonal T(n,n-2) = 1/8*n^4 -1/12*n^3 -5/8*n^2 +7/12*n = A215862(n-2),
Diagonal T(n,n-1) = 1/2*n^2- 1/2*n = A000217(n-1),
and Diagonal T(n,n) = 1. (End)

			  ... o-o ........... o o ........... o o ..........
  ...     ........... |   ........... |\  ..........
  ... o-o ........... o-o ........... o-o ..........
T(4,2) = 19 because the above graphs on 4 nodes have 2 components with at most one cycle.  They have respectively 3 + 12 + 4 = 19 labelings.
1;
1,     1;
4,     3,     1;
31,    19,    6,     1;
347,   195,   55,    10,   1;
4956,  2707,  720,   125,  15,  1;
85102, 46319, 12082, 2030, 245, 21, 1;

V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.

Row sums = A133686.
Column 1 = A129271.
Cf. A144228, A000217, A215862.

nn=10;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];f[list_]:=Select[list,#>0&];Map[f,Drop[Range[0,nn]!CoefficientList[Series[Exp[y(t/2-3t^2/4)]/(1-t)^(y/2),{x,0,nn}],{x,y}],1]]//Grid

\p 1000  \\ See Peter Luschny formula in A129271.
f(p) = round(((p-1) * exp(p) * incgam(p-1,p) + p^(p-2) * (3-p)) /2);
T(n,k) = { my(S=0, D, p, c); forpart(a = n, D = Set(a);
   S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (f(p)/p!)^c /c!)
, [1, n], [k, k]); n! * S }; \\ Washington Bomfim, Jun 16 2020

# uses[bell_matrix from A264428]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A129271(n+1), 10) # Peter Luschny, Jan 18 2016

E.g.f.: exp(y*A(x)) where A(x) is the e.g.f. for A133686.

T(n,k) = n!/k! * Sum_{compositions p_1 + ... + p_k = n, p_i >= 1} Product_{j=1..k} f(p_j)/p_j!, where f(p)=A129271(p) = ((p-1)*e^p*GAMMA(p-1,p)+p^(p-2)*(3-p))/2.

cp's OEIS Frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A369828 Number of simple graphs on 2n labeled nodes with n edges where each maximally connected subgraph has at most one cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A217756 Triangular array read by rows: T(n,k) is the number of simple labeled graphs on n nodes with exactly k components where each component has at most one cycle; n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Mathematica

PARI

Sage

Formula