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.

Showing 1-6 of 6 results.

A003189 Erroneous version of A051240.

Original entry on oeis.org

1, 1, 1, 2, 6, 156, 7013488, 29288387523484992, 234431745534048922731115019069056
Offset: 1

Views

Author

Keywords

Links

A000088 Number of simple graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler transform of the sequence A001349.
Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
  • F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
  • Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
  • Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
  • M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
  • R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
  • R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

Programs

  • Maple
    # To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019
  • Mathematica
    Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
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]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)
  • PARI
    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)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017
  • Python
    from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<>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 02 2024
  • Sage
    def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

Formula

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
1+
2^( -n + 1)*n$2+
2^(-2*n + 3)*n$3*(n-7/3)+
2^(-3*n + 6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Extensions

Harary gives an incorrect value for a(8); compare A007149

A309858 Number A(n,k) of k-uniform hypergraphs on n unlabeled nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

2, 1, 2, 1, 2, 2, 1, 1, 3, 2, 1, 1, 2, 4, 2, 1, 1, 1, 4, 5, 2, 1, 1, 1, 2, 11, 6, 2, 1, 1, 1, 1, 5, 34, 7, 2, 1, 1, 1, 1, 2, 34, 156, 8, 2, 1, 1, 1, 1, 1, 6, 2136, 1044, 9, 2, 1, 1, 1, 1, 1, 2, 156, 7013320, 12346, 10, 2, 1, 1, 1, 1, 1, 1, 7, 7013320, 1788782616656, 274668, 11, 2
Offset: 0

Views

Author

Alois P. Heinz, Aug 20 2019

Keywords

Comments

See A000088 and A000665 for more references.

Examples

			Square array A(n,k) begins:
  2, 1,    1,       1,       1,    1, 1, 1, ...
  2, 2,    1,       1,       1,    1, 1, 1, ...
  2, 3,    2,       1,       1,    1, 1, 1, ...
  2, 4,    4,       2,       1,    1, 1, 1, ...
  2, 5,   11,       5,       2,    1, 1, 1, ...
  2, 6,   34,      34,       6,    2, 1, 1, ...
  2, 7,  156,    2136,     156,    7, 2, 1, ...
  2, 8, 1044, 7013320, 7013320, 1044, 8, 2, ...

Links

Crossrefs

Columns k=0..10 give: A007395, A000027, A000088, A000665, A051240, A051249, A309860, A309861, A309862, A309863, A309864.
Cf. A301922, A309865 (the same as triangle).

Programs

  • Maple
    g:= (l, i, n)-> `if`(i=0, `if`(n=0, [[]], []), [seq(map(x->
     [x[], j], g(l, i-1, n-j))[], j=0..min(l[i], n))]):
h:= (p, v)-> (q-> add((s-> add(`if`(andmap(i-> irem(k[i], p[i]
     /igcd(t, p[i]))=0, [$1..q]), mul((m-> binomial(m, k[i]*m
     /p[i]))(igcd(t, p[i])), i=1..q), 0), t=1..s)/s)(ilcm(seq(
    `if`(k[i]=0, 1, p[i]), i=1..q))), k=g(p, q, v)))(nops(p)):
b:= (n, i, l, v)-> `if`(n=0 or i=1, 2^((p-> h(p, v))([l[], 1$n]))
     /n!, add(b(n-i*j, i-1, [l[], i$j], v)/j!/i^j, j=0..n/i)):
A:= proc(n, k) option remember; `if`(k>n, 1,
     `if`(k>n-k, A(n, n-k), b(n$2, [], k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);
  • PARI
    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}
rep(typ)={my(L=List(), k=0); for(i=1, #typ, k+=typ[i]; listput(L, k); while(#L0, u=vecsort(apply(f, u)); d=lex(u, v)); !d}
Q(n, k, perm)={my(t=0); forsubset([n, k], v, t += can(Vec(v), t->perm[t])); t}
T(n, k)={my(s=0); forpart(p=n, s += permcount(p)*2^Q(n, k, rep(p))); s/n!} \\ Andrew Howroyd, Aug 22 2019

Formula

A(n,k) = A(n,n-k) for 0 <= k <= n.
A(n,k) - A(n-1,k) = A301922(n,k) for n,k >= 1.

A309865 Number T(n,k) of k-uniform hypergraphs on n unlabeled nodes; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

2, 2, 2, 2, 3, 2, 2, 4, 4, 2, 2, 5, 11, 5, 2, 2, 6, 34, 34, 6, 2, 2, 7, 156, 2136, 156, 7, 2, 2, 8, 1044, 7013320, 7013320, 1044, 8, 2, 2, 9, 12346, 1788782616656, 29281354514767168, 1788782616656, 12346, 9, 2
Offset: 0

Views

Author

Alois P. Heinz, Aug 20 2019

Keywords

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k<=n. T(n,k) = 1 for k>n.
See A000088 and A000665 for more references.

Examples

			Triangle T(n,k) begins:
  2;
  2, 2;
  2, 3,    2;
  2, 4,    4,       2;
  2, 5,   11,       5,       2;
  2, 6,   34,      34,       6,    2;
  2, 7,  156,    2136,     156,    7, 2;
  2, 8, 1044, 7013320, 7013320, 1044, 8, 2;
  ...

Links

Crossrefs

Columns k=0..10 give: A007395, A000027, A000088, A000665, A051240, A051249, A309860, A309861, A309862, A309863, A309864.
Cf. A309858 (the same as square array).

Programs

  • Maple
    g:= (l, i, n)-> `if`(i=0, `if`(n=0, [[]], []), [seq(map(x->
     [x[], j], g(l, i-1, n-j))[], j=0..min(l[i], n))]):
h:= (p, v)-> (q-> add((s-> add(`if`(andmap(i-> irem(k[i], p[i]
     /igcd(t, p[i]))=0, [$1..q]), mul((m-> binomial(m, k[i]*m
     /p[i]))(igcd(t, p[i])), i=1..q), 0), t=1..s)/s)(ilcm(seq(
    `if`(k[i]=0, 1, p[i]), i=1..q))), k=g(p, q, v)))(nops(p)):
b:= (n, i, l, v)-> `if`(n=0 or i=1, 2^((p-> h(p, v))([l[], 1$n]))
     /n!, add(b(n-i*j, i-1, [l[], i$j], v)/j!/i^j, j=0..n/i)):
T:= proc(n, k) option remember; `if`(k>n-k,
      T(n, n-k), b(n$2, [], k))
    end:
seq(seq(T(n, k), k=0..n), n=0..9);

Formula

T(n,k) = T(n,n-k) for 0 <= k <= n.

A051249 Pure 4-dimensional simplicial complexes on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 7, 1044, 1788782616656, 234431745534048922731115555415680, 1994324729203114587259985605157804740271034553359179870979936357974016
Offset: 0

Views

Author

Vladeta Jovovic

Keywords

Links

Crossrefs

Cf. A000088, A000665, A051240.
Column k=5 of A309858.

Extensions

a(0)=1 prepended by Alois P. Heinz, Aug 20 2019

A092337 Triangle read by rows: T(n,m) = number of 3-uniform hypergraphs with m hyperedges on n unlabeled nodes, where 0 <= m <= C(n,3).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 3, 7, 21, 43, 94, 161, 249, 312, 352, 312, 249, 161, 94, 43, 21, 7, 3, 1, 1, 1, 1, 3, 10, 38, 137, 509, 1760, 5557, 15709, 39433, 87659, 172933, 303277, 473827, 660950, 824410, 920446, 920446, 824410, 660950
Offset: 3

Views

Author

Gordon F. Royle, Mar 18 2004

Keywords

Comments

A 3-uniform hypergraph is a set of 3-subsets of the nodes with isomorphism determined by permutations of the node set. The numbers are calculated using Polya enumeration from the cycle index of the symmetric group Sym(n) in its action on 3-subsets of an n-set, which can easily be computed by MAGMA or GAP. A000665 is the sum of each row of the triangle.

Examples

			Triangle T(n,m) begins:
1, 1;
1, 1, 1, 1,  1;
1, 1, 2, 4,  6,  6,  6,   4,   2,   1,   1;
1, 1, 3, 7, 21, 43, 94, 161, 249, 312, 352, 312, 249, 161, 94, 43, 21, 7, 3, 1, 1;

Links

Crossrefs

Cf. A000665, A051240.

Programs

  • Mathematica
    Needs["Combinatorica`"]; Table[A = Subsets[Range[n], {3}];
  CoefficientList[CycleIndex[Replace[Map[Sort,System`PermutationReplace[A, SymmetricGroup[n]], {2}],Table[A[[i]] -> i, {i, 1, Length[A]}], 2], s] /.
Table[s[i] -> 1 + x^i, {i, 1, Binomial[n, 3]}], x], {n,3,7}] // Grid (* Geoffrey Critzer, Oct 28 2015 *)
Showing 1-6 of 6 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.