A053400 -id:A053400 - cp's OEIS frontend

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 10, 11, 1, 1, 5, 20, 66, 34, 1, 1, 6, 35, 276, 792, 156, 1, 1, 7, 56, 900, 10688, 25506, 1044, 1, 1, 8, 84, 2451, 90005, 1601952, 2302938, 12346, 1, 1, 9, 120, 5831, 533358, 43571400, 892341888, 591901884, 274668, 1

Offset: 1

N. J. A. Sloane, Aug 25 2001

The first five rows admit the g.f. 1/(1-x), 1/(1-x)^2, 1/(1-x)^4 and those given in A063842, A063843. Is it known that the n-th row admits a rational g.f. with denominator (1-x)^A000124(n)? - M. F. Hasler, Jan 19 2012

T(n+1,k-1) is the number of unoriented ways to color the edges of a regular n-dimensional simplex using up to k colors. - Robert A. Russell, Aug 21 2019

			Table begins
===========================================================
n\k| 0    1       2         3           4             5
---|-------------------------------------------------------
1  | 1    1       1         1           1             1 ...
2  | 1    2       3         4           5             6 ...
3  | 1    4      10        20          35            56 ...
4  | 1   11      66       276         900          2451 ...
5  | 1   34     792     10688       90005        533358 ...
6  | 1  156   25506   1601952    43571400     661452084 ...
7  | 1 1044 2302938 892341888 95277592625 4364646955812 ...
...
T(3,2)=10 because there are 10 unlabeled graphs with 3 nodes with at most 2 edges connecting any pair.
(. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - _Geoffrey Critzer_, Jan 23 2012

Chai Wah Wu, Table of n, a(n) for n = 1..1584 (terms 1..820 from Andrew Howroyd)
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Columns give A000088, A004102, A053400, A053420, A053421.
Rows (4th and 5th) are listed in A063842, A063843.
Cf. A327084 (unoriented simplex edge colorings).

(* This code gives the array T(n,k). *) Needs["Combinatorica`"]; Transpose[Table[Table[PairGroupIndex[SymmetricGroup[n],s]/.Table[s[i]->k+1, {i,0,Binomial[n,2]}], {n,1,7}], {k,0,6}]]//Grid (* Geoffrey Critzer, Jan 23 2012 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
T[n_, k_] := (s=0; Do[s += permcount[p]*(k+1)^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[T[n-k, k], {n, 1, 10}, {k, n-1, 0, -1}] // Flatten (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
T(n, k) = {my(s=0); forpart(p=n, s+=permcount(p)*(k+1)^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A063841_T(n,k): return int(sum(Fraction((k+1)**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

T(n,k) = A327084(n-1,k+1) for n > 1. - Robert A. Russell, Aug 21 2019

More terms from Vladeta Jovovic, Sep 03 2001

A053420 Number of 4-multigraphs on n nodes.

Original entry on oeis.org

1, 5, 35, 900, 90005, 43571400, 95277592625, 925609100039625, 40119721052610123750, 7833164300852979350336250, 6953552738579427778531249187500, 28293472829338822230349054996265275000, 531350037528849507720092485196308155336875000

Offset: 1

Vladeta Jovovic, Jan 11 2000

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Column k=4 of A063841.

Cf. A000088, A004102, A053400.

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053420(n): return int(sum(Fraction(5**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

Terms a(12) and beyond from Andrew Howroyd, Oct 22 2017

A053421 Number of 5-multigraphs on n nodes.

Original entry on oeis.org

1, 6, 56, 2451, 533358, 661452084, 4364646955812, 152397092027960154, 28427450083725134688228, 28645398830642924774967347088, 157458251108667629202718200130101672, 4760428376101385226312810920945121043818096

Offset: 1

Vladeta Jovovic, Jan 11 2000

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Column k=5 of A063841.

Cf. A000088, A004102, A053400.

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053421(n): return int(sum(Fraction(6**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

a(12) from Andrew Howroyd, Oct 22 2017

A053466 Number of connected 3-multigraphs on n nodes.

Original entry on oeis.org

1, 3, 16, 250, 10364, 1590368, 890704748, 1798888780974, 13040687516840812, 341365122121400763818, 32525985067651643920408364, 11367070802646570246017825177796, 14669210743645179982935622385486358396, 70315832651324129302715163143607703940500714

Offset: 1

Vladeta Jovovic, Jan 13 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marko Riedel, Computation of a recurrence for the number of connected k-multigraphs on n nodes
Marko Riedel, Maple implementation of a recurrence for the number of connected k-multigraphs on n nodes

Cf. A053400, A053515.

Inverse Euler transform of A053400. - Andrew Howroyd, Nov 07 2019

Terms a(13) and beyond from Andrew Howroyd, Nov 07 2019

A053514 Number of 3-multigraphs with loops on n nodes.

Original entry on oeis.org

4, 40, 816, 48400, 9333312, 6202675584, 14372025574144, 117323908831879296, 3413309842639341263872, 357775914831345583881365504, 136403808102564598893326677037056, 190699341738365392248566307143860137984

Offset: 1

Vladeta Jovovic, Jan 14 2000

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

Cf. A000666, A053400, A053513.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2] + 1];
a[n_] := (s=0; Do[s += permcount[p]*4^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2 + 1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*4^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053514(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum(((q>>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items())<<1),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

a(12) from Andrew Howroyd, Oct 22 2017

A052107 Number of self-complementary 3-multigraphs on n nodes.

Original entry on oeis.org

1, 0, 0, 4, 16, 0, 0, 2080, 32896, 0, 0, 178990080, 11453771776, 0, 0, 3002404080455680, 768614611824951296, 0, 0, 10316167090130469587779584, 10563755026498136326181748736, 0, 0, 7561830376433501721102295492903043072, 30973257220603971305905396442627825467392

Offset: 1

Vladeta Jovovic, Jan 20 2000

nonn

V. Jovovic, On the number of m-place relations (in Russian), Logiko-algebraicheskie konstruktsii, Tver, 1992, 59-66.
J. Xu, Ch. R. Wang, J. F. Wang, The theory of self-complementary k-multigraphs (in Chinese), Pure Appl. Math. [Chuncui Shuxue yu Yingyong Shuxue] 10 (1994), Special Issue, 18-22.

Andrew Howroyd, Table of n, a(n) for n = 1..100
D. Wille, Enumeration of self-complementary structures, J. Comb. Theory B 25 (1978) 143-150.

Cf. A000171, A053588, A053400.

permcount[v_List] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_List] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + 2 Total[v];
a[n_] := Module[{s = 0}, If[Mod[n, 4] < 2, Do[s += permcount[4*p]* 4^edges[p]*If[OddQ[n], n*4^Length[p], 1], {p, IntegerPartitions[ Quotient[n, 4]]}]]; s/n!];
Array[a, 25] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {4*sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, 2*v[i])}
a(n) = {my(s=0); if(n%4<2, forpart(p=n\4, s+=permcount(4*Vec(p))*4^edges(p)*if(n%2, n*4^#p, 1))); s/n!} \\ Andrew Howroyd, Sep 17 2018

Terms a(24) and beyond from Andrew Howroyd, Sep 17 2018

cp's OEIS Frontend

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A053420 Number of 4-multigraphs on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Extensions

A053421 Number of 5-multigraphs on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Extensions

A053466 Number of connected 3-multigraphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A053514 Number of 3-multigraphs with loops on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A052107 Number of self-complementary 3-multigraphs on n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions