A173219 -id:A173219 - cp's OEIS frontend

A054548 Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.

1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 3, 16, 15, 6, 1, 0, 0, 0, 30, 135, 222, 205, 120, 45, 10, 1, 0, 0, 0, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 0, 0, 0, 0, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175

Offset: 0

Vladeta Jovovic, Apr 09 2000

			From _Gus Wiseman_, Feb 14 2024: (Start)
Triangle begins:
   1
   0
   0   1
   0   0   3   1
   0   0   3  16  15   6   1
   0   0   0  30 135 222 205 120  45  10   1
Row n = 4 counts the following graphs:
  .  .  12-34  12-13-14  12-13-14-23  12-13-14-23-24  12-13-14-23-24-34
        13-24  12-13-24  12-13-14-24  12-13-14-23-34
        14-23  12-13-34  12-13-14-34  12-13-14-24-34
               12-14-23  12-13-23-24  12-13-23-24-34
               12-14-34  12-13-23-34  12-14-23-24-34
               12-23-24  12-13-24-34  13-14-23-24-34
               12-23-34  12-14-23-24
               12-24-34  12-14-23-34
               13-14-23  12-14-24-34
               13-14-24  12-23-24-34
               13-23-24  13-14-23-24
               13-23-34  13-14-23-34
               13-24-34  13-14-24-34
               14-23-24  13-23-24-34
               14-23-34  14-23-24-34
               14-24-34
(End)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.4.

Michael De Vlieger, Table of n, a(n) for n = 0..10700
A. N. Bhavale and B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.
Ashok Nivrutti Bhavale, Equivalence of labeled graphs and lattices, arXiv:2501.05064 [math.CO], 2025. See pp. 1-2, 13.
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.

Row sums give A006129. Cf. A054547.
The connected case is A062734, with loops A369195.
This is the covering case of A084546.
Column sums are A121251, with loops A173219.
The version with loops is A369199, row sums A322661.
The unlabeled version is A370167, row sums A002494.
A006125 counts simple graphs; also loop-graphs if shifted left.
Cf. A000666, A006649, A062740, A066383, A121252, A133686, A322700, A368597, A369196, A369197.

nn=5; s=Sum[(1+y)^Binomial[n,2]  x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[ s Exp[-x], {x,0,nn}], {x,y}] //Grid  (* returns triangle indexed at n = 0, Geoffrey Critzer, Oct 07 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{k}],Union@@#==Range[n]&]],{n,0,5},{k,0,Binomial[n,2]}] (* Gus Wiseman, Feb 14 2024 *)

T(n, k) = Sum_{i=0..n} (-1)^(n-i)*C(n, i)*C(C(i, 2), k), k=0...n*(n-1)/2.

E.g.f.: exp(-x)*Sum_{n>=0} (1 + y)^C(n,2)*x^n/n!. - Geoffrey Critzer, Oct 07 2012

a(0) prepended by Gus Wiseman, Feb 14 2024

A369199 Irregular triangle read by rows where T(n,k) is the number of labeled loop-graphs covering n vertices with k edges.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 1, 0, 0, 6, 17, 15, 6, 1, 0, 0, 3, 46, 150, 228, 206, 120, 45, 10, 1, 0, 0, 0, 45, 465, 1803, 3965, 5835, 6210, 4955, 2998, 1365, 455, 105, 15, 1, 0, 0, 0, 15, 645, 5991, 27364, 79470, 165555, 264050, 334713, 344526, 291200, 202860, 116190, 54258, 20349, 5985, 1330, 210, 21, 1

Offset: 0

Gus Wiseman, Jan 18 2024

			Triangle begins:
   1
   0   1
   0   1   3   1
   0   0   6  17  15   6   1
   0   0   3  46 150 228 206 120  45  10   1
Row n = 3 counts the following loop-graphs (loops shown as singletons):
  {1,23}   {1,2,3}     {1,2,3,12}    {1,2,3,12,13}   {1,2,3,12,13,23}
  {2,13}   {1,2,13}    {1,2,3,13}    {1,2,3,12,23}
  {3,12}   {1,2,23}    {1,2,3,23}    {1,2,3,13,23}
  {12,13}  {1,3,12}    {1,2,12,13}   {1,2,12,13,23}
  {12,23}  {1,3,23}    {1,2,12,23}   {1,3,12,13,23}
  {13,23}  {1,12,13}   {1,2,13,23}   {2,3,12,13,23}
           {1,12,23}   {1,3,12,13}
           {1,13,23}   {1,3,12,23}
           {2,3,12}    {1,3,13,23}
           {2,3,13}    {1,12,13,23}
           {2,12,13}   {2,3,12,13}
           {2,12,23}   {2,3,12,23}
           {2,13,23}   {2,3,13,23}
           {3,12,13}   {2,12,13,23}
           {3,12,23}   {3,12,13,23}
           {3,13,23}
           {12,13,23}

Andrew Howroyd, Table of n, a(n) for n = 0..1560 (rows 0..20)

The version without loops is A054548.
This is the covering case of A084546.
Column sums are A173219.
Row sums are A322661, unlabeled A322700.
The connected case is A369195, without loops A062734.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts simple graphs; also loop-graphs if shifted left.
A006129 counts covering graphs, unlabeled A002494.
A368927 counts choosable loop-graphs, covering A369140.
A369141 counts non-choosable loop-graphs, covering A369142.
Cf. A000666, A006649, A062740, A066383, A133686, A368597, A369196, A369197.

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}],{k}],Length[Union@@#]==n&]],{n,0,5},{k,0,Binomial[n+1,2]}]

T(n)={[Vecrev(p) | p<-Vec(serlaplace(exp(-x + O(x*x^n))*(sum(j=0, n, (1 + y)^binomial(j+1, 2)*x^j/j!)))) ]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Feb 02 2024

E.g.f.: exp(-x) * (Sum_{j >= 0} (1 + y)^binomial(j+1, 2)*x^j/j!). - Andrew Howroyd, Feb 02 2024

A370167 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with k = 0..binomial(n,2) edges.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 2, 1, 1, 0, 0, 0, 1, 4, 5, 5, 4, 2, 1, 1, 0, 0, 0, 1, 3, 9, 15, 20, 22, 20, 14, 9, 5, 2, 1, 1, 0, 0, 0, 0, 1, 6, 20, 41, 73, 110, 133, 139, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1, 0, 0, 0, 0, 1, 3, 15, 50, 124, 271, 515, 832, 1181, 1460, 1581, 1516, 1291, 970, 658, 400, 220, 114, 56, 24, 11, 5, 2, 1, 1

Offset: 0

Gus Wiseman, Feb 15 2024

			Triangle begins:
  1
  0
  0  1
  0  0  1  1
  0  0  1  2  2  1  1
  0  0  0  1  4  5  5  4  2  1  1
  0  0  0  1  3  9 15 20 22 20 14  9  5  2  1  1

Andrew Howroyd, Table of n, a(n) for n = 0..1350 (rows 0..20)

Column sums are A000664.
Row sums are A002494.
This is the covering case of A008406, labeled A084546.
The labeled version is A054548, row sums A006129, column sums A121251.
The connected case is A054924, row sums A001349, column sums A002905.
The labeled connected case is A062734, with loops A369195.
The connected case with loops is A283755, row sums A054921.
The labeled version w/ loops is A369199, row sums A322661, col sums A173219.
Cf. A000666, A006125, A006649, A054547, A066383, A322700.

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}],{k}],Union@@#==Range[n]&]]], {n,0,5},{k,0,Binomial[n,2]}]

\\ G(n) defined in A008406.
row(n)={Vecrev(G(n)-if(n>0, G(n-1)), binomial(n,2)+1)}
{ for(n=0, 7, print(row(n))) } \\ Andrew Howroyd, Feb 19 2024

a(42) onwards from Andrew Howroyd, Feb 19 2024

A331278 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k distinct columns and any number of nonzero rows with column sums n and columns in decreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 12, 4, 1, 0, 1, 124, 124, 8, 1, 0, 1, 1800, 10596, 1280, 16, 1, 0, 1, 33648, 1764244, 930880, 13456, 32, 1, 0, 1, 769336, 484423460, 1849386640, 85835216, 143808, 64, 1, 0, 1, 20796960, 198461691404, 7798297361808, 2098356708016, 8206486848, 1556416, 128, 1

Offset: 0

Andrew Howroyd, Jan 13 2020

The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.

A(n,k) is the number of n-uniform k-block sets of multisets.

			Array begins:
====================================================================
n\k | 0  1      2          3                4                   5
----+---------------------------------------------------------------
  0 | 1  1      0          0                0                   0 ...
  1 | 1  1      1          1                1                   1 ...
  2 | 1  2     12        124             1800               33648 ...
  3 | 1  4    124      10596          1764244           484423460 ...
  4 | 1  8   1280     930880       1849386640       7798297361808 ...
  5 | 1 16  13456   85835216    2098356708016  140094551934813712 ...
  6 | 1 32 143808 8206486848 2516779512105152 ...
  ...
The A(2,2) matrices are:
  [1 0]  [1 0]  [1 0]  [2 0]  [1 1]  [1 0]
  [1 0]  [0 1]  [0 1]  [0 1]  [1 0]  [1 1]
  [0 1]  [1 0]  [0 1]  [0 1]  [0 1]  [0 1]
  [0 1]  [0 1]  [1 0]
.
  [1 0]  [1 0]  [1 0]  [2 1]  [2 0]  [1 0]
  [1 0]  [0 2]  [0 1]  [0 1]  [0 2]  [1 2]
  [0 2]  [1 0]  [1 1]

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

Rows n=1..2 are A000012, A173219.
Columns k=0..2 are A000012, A011782, A331396.
The version with binary entries is A331277.
The version with not necessarily distinct columns is A331315.
Cf. A316674 (unrestricted version), A330942, A331395.

T(n,k)={my(m=n*k); sum(j=0, m, binomial(binomial(j+n-1,n),k)*sum(i=j, m, (-1)^(i-j)*binomial(i,j)))}

A(n,k) = Sum_{j=0..n*k} binomial(binomial(j+n-1,n),k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A316674(n, j)/k!.
A(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(k-1, k-j)*A331315(n, j).
A(n, k) = A011782(n) * A331277(n, k) for k > 0.
A331395(n) = Sum_{d|n} A(n/d, d).

A173218 G.f.: A(x) = Sum_{n>=0} (1 + x)^(n^2+n) / 2^(n+1).

Original entry on oeis.org

1, 4, 50, 1040, 30300, 1135080, 51972668, 2812429632, 175606496520, 12426817517920, 982846762742416, 85916923493646752, 8225856593959648696, 856044724445883011520, 96213518828394481754400

Offset: 0

Paul D. Hanna, Mar 05 2010

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Cf. A173217, A173219.

Table[Sum[StirlingS1[n, j] * Sum[Binomial[j, s] * HurwitzLerchPhi[1/2, -j - s, 0], {s, 0, j}], {j, 0, n}] / (2*n!), {n, 0, 20}] (* Vaclav Kotesovec, Oct 08 2019 *)

{a(n)=local(A=sum(m=0,n^2+100,(1+x +O(x^(n+2)))^(m*(m+1))/2^(m+1)));round(polcoeff(A,n))}

a(n) ~ 2^(2*n) * n^n / (2^(log(2)/8) * log(2)^(2*n+1) * exp(n)). - Vaclav Kotesovec, Oct 08 2019

A265937 G.f.: Sum_{n>=0} (1 + x)^(n*(n+1)/2) / 2^n.

Original entry on oeis.org

2, 4, 24, 248, 3600, 67296, 1538672, 41593920, 1297683360, 45891815040, 1814072216864, 79263667304640, 3793393788125760, 197339219789611200, 11087608251010390080, 669127189486395204544, 43167108189991530605184, 2964541208087967215725440, 215934869210274766223069440, 16627513858173093851116296960, 1349582577808759197056647917696, 115158206188199564942934814336896, 10305721256666828267464573643658240

Offset: 0

Paul D. Hanna, Dec 23 2015

nonn

			G.f.: A(x) = 2 + 4*x + 24*x^2 + 248*x^3 + 3600*x^4 + 67296*x^5 + 1538672*x^6 + 41593920*x^7 + 1297683360*x^8 + 45891815040*x^9 + 1814072216864*x^10 +...
where
A(x) = 1 + (1+x)/2 + (1+x)^3/2^2 + (1+x)^6/2^3 + (1+x)^10/2^4 + (1+x)^15/2^5 + (1+x)^21/2^6 + (1+x)^28/2^7 + (1+x)^36/2^8 +...+ (1+x)^(n*(n+1)/2)/2^n +...

Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Cf. A265936.

Table[Sum[StirlingS1[n, j] * Sum[Binomial[j, s] * HurwitzLerchPhi[1/2, -j - s, 0], {s, 0, j}] / 2^j, {j, 0, n}] / n!, {n, 0, 20}] (* Vaclav Kotesovec, Oct 08 2019 *)

/* Informal listing of terms: */
{Vec( round( sum(n=0, 600, (1+x +O(x^31))^(n*(n+1)/2)/2^n * 1.) ) )}
{Vec( round( sum(n=0, 200, (1.+x)^n/2^n * prod(k=1, n, (2 - (1+x)^(2*k-1)) / (2 - (1+x)^(2*k)) +O(x^21) ) ) ) )}

G.f.: Sum_{n>=0} (1+x)^n/2^n * Product_{k=1..n} (2 - (1+x)^(2*k-1))/(2 - (1+x)^(2*k)) due to a q-series identity.
G.f.: 1/(1 - (1+x)/2 /(1 - (1+x)*((1+x)-1)/2 /(1 - (1+x)^3/2 /(1 - (1+x)^2*((1+x)^2-1)/2 /(1 - (1+x)^5/2 /(1 - (1+x)^3*((1+x)^3-1)/2 /(1 - (1+x)^7/2 /(1 - (1+x)^4*((1+x)^4-1)/2 /(1 - ...))))))))), a continued fraction due to a partial elliptic theta function identity.
a(n) = Sum_{k>=(sqrt(8*n+1)-1)/2} binomial(k*(k+1)/2,n) / 2^k.
a(n) = 2*A173219(n). - Vaclav Kotesovec, Oct 08 2019
a(n) ~ 2^(n+1) * n^n / (2^(log(2)/4) * log(2)^(2*n+1) * exp(n)). - Vaclav Kotesovec, Oct 08 2019

cp's OEIS Frontend

A054548 Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A369199 Irregular triangle read by rows where T(n,k) is the number of labeled loop-graphs covering n vertices with k edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A370167 Irregular triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with k = 0..binomial(n,2) edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A331278 Array read by antidiagonals: A(n,k) is the number of nonnegative integer matrices with k distinct columns and any number of nonzero rows with column sums n and columns in decreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A173218 G.f.: A(x) = Sum_{n>=0} (1 + x)^(n^2+n) / 2^(n+1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A265937 G.f.: Sum_{n>=0} (1 + x)^(n*(n+1)/2) / 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula