cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 41-44 of 44 results.

A370315 Number of unlabeled simple graphs with n possibly isolated vertices and up to n edges.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 54, 146, 436, 1372, 4577, 15971, 58376, 221876, 876012, 3583099, 15159817, 66248609, 298678064, 1387677971, 6637246978, 32648574416, 165002122350, 855937433641, 4553114299140, 24813471826280, 138417885372373, 789683693019999, 4603838061688077
Offset: 0

Views

Author

Gus Wiseman, Feb 18 2024

Keywords

Examples

			The a(1) = 1 through a(4) = 9 graph edge sets:
  {}  {}    {}          {}
      {12}  {12}        {12}
            {12-13}     {12-13}
            {12-13-23}  {12-34}
                        {12-13-14}
                        {12-13-23}
                        {12-13-24}
                        {12-13-14-23}
                        {12-13-24-34}

Links

Crossrefs

The case of exactly n edges is A001434, covering A006649.
The connected covering case is A005703, labeled A129271.
Partial row sums of A008406, covering A370167.
The labeled version is A369192.
The version with loops is A370168, labeled A066383.
The covering case is A370316, labeled A369191.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000666, A322661, A322700, A369194, A369196, A369197, A369199, A370169.

Programs

  • Mathematica
    brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]], Length[#]<=n&]]],{n,0,5}]
  • PARI
    a(n) = if(n<=1, n>=0, polcoef(G(n, O(x*x^n))/(1-x),n)) \\ G(n) defined in A008406. - Andrew Howroyd, Feb 20 2024

Formula

Sum of first n+1 terms of row n of A008406.

A370318 Number of labeled simple graphs with n vertices and the same number of edges as covered vertices, such that the edge set is connected.

Original entry on oeis.org

0, 0, 0, 1, 19, 307, 5237, 99137, 2098946, 49504458, 1291570014, 37002273654, 1156078150969, 39147186978685, 1428799530304243, 55933568895261791, 2338378885159906196, 103995520598384132516, 4903038902046860966220, 244294315694676224001852, 12827355456239840407125363
Offset: 0

Views

Author

Gus Wiseman, Feb 18 2024

Keywords

Comments

The case of an empty edge set is excluded.

Links

Crossrefs

The covering case is A057500, which is also the covering case of A370317.
This is the connected case of A367862, covering A367863.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by edge count.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A001429, A006649, A061540, A116508, A323818, A367916, A368951, A369197.

Programs

  • Mathematica
    csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}], Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==Length[Union@@#] && Length[csm[#]]==1&]],{n,0,5}]
  • PARI
    \\ Compare A370317; use A057500 for efficiency.
a(n)=n!*polcoef(polcoef(exp(x*y + O(x*x^n))*(-x+log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

Formula

Binomial transform of A057500 (if the null graph is not connected).
a(n) = n!*[x^n][y^n] exp(x*y)*(-x + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

A368834 Number of unlabeled simple graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 27, 62, 165, 423, 1140, 3060, 8427, 23218, 64782, 181370, 511004, 1444285, 4097996, 11656644, 33243265, 94992847, 271953126, 779790166, 2239187466, 6438039076, 18532004323, 53400606823, 154024168401, 444646510812, 1284682242777
Offset: 0

Views

Author

Gus Wiseman, Jan 23 2024

Keywords

Examples

			Representatives of the a(2) = 1 through a(5) = 10 simple graphs:
  {12}  {12}{13}      {12}{34}          {12}{13}{45}
        {12}{13}{23}  {12}{13}{14}      {12}{13}{14}{15}
                      {12}{13}{24}      {12}{13}{14}{25}
                      {12}{13}{14}{23}  {12}{13}{23}{45}
                      {12}{13}{24}{34}  {12}{13}{24}{35}
                                        {12}{13}{14}{15}{23}
                                        {12}{13}{14}{23}{25}
                                        {12}{13}{14}{23}{45}
                                        {12}{13}{14}{25}{35}
                                        {12}{13}{24}{35}{45}

Links

Crossrefs

Without the choice condition we have A002494, labeled A006129.
The connected case is A005703, labeled A129271.
This is the covering case of A134964, complement A140637.
The labeled version is A367869, complement A367868.
The version with loops is A369200, complement A369147.
The complement is counted by A369202.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A006649, A001434, A055621, A116508, A133686, A137916, A137917, A368984, A369146.

Programs

  • Mathematica
    brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]],{n,0,5}]

Formula

Euler transform of A005703 with A005703(1) = 0.
First differences of A134964.
a(n) = A002494(n) - A369202(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

Views

Author

Geoffrey Critzer, Mar 23 2013

Keywords

Comments

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)

Examples

			  ... 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;

References

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

Crossrefs

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

Programs

  • Mathematica
    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
  • PARI
    \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
  • Sage
    # 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

Formula

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.
Previous Showing 41-44 of 44 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.