By Doron Zeilberger
To use it, download it, save it as GraphEnumeration, and type
The main functions are
BnSeq(n): the first n terms of the enumerating sequence for the number of "irreducible" Boolean functions,
i.e. the number of equivalence classes of Boolean functions where f(x1, ..., xm) is considered equivalent
to g(x1,x2,...,xm) if there exist a permutation π and a subset S of {1, ..., m}, such that
permuting the variables under π and then negating the variables in S transforms f to g.
BnxSeq(n,x): Like the above but with generating functions according to the number of true rows in the truth table.
Cseq(n): The first n terms of the sequence enumerating unlabeled connected graphs.
Cseqx(n,x): like the above, but with generating functions according to the number of edges.
HGseq(k,n): the first n terms in the enumerating sequence for unlabeled regular k-hyper-graphs
HGseqx(k,n,x): as above, but generating functions according to "edges"
Gseq(n): the first n terms in the enumerating sequence for unlabeled graphs (same as HGseq(2,n) )
Gseqx: as above, but generating functions according to edges
RTseq(n): the first n terms in the enumerating sequence for unlabeled rooted trees (following Cayley)
Tseq(n):the first n terms in the enumerating sequence for unlabeled trees (following Cayley)
[Note: this is the default sequence in Sloane (viewed July 20, 2010)]
UGdeg(L): the number of all (connected or not) unlabeled (simple) graphs
with degree sequence L
UMGdeg(L): the number of all (connected or not) unlabeled multi-graphs
with degree sequence L
To see the first 10 terms of the sequence enumerating equivalence classes of Boolean functions under permutation of variables and negation
[Note: this is Sloane's
A000616, first computed by M.A. Harrison;
we computed two extra terms].
To see the first 7 terms of the the sequence of weight-enumerators
enumerating equivalence classes of Boolean functions under permutation of variable and negation the
To see the first 20 terms of the sequence enumerating connected unlabeled graphs the
[Note: this is Sloane'sA001349]
To see the first 20 terms of the sequence enumerating unlabeled graphs the
input
gives the output.
[Note: this is Sloane'sA000088]
To see the
first 60 terms of the sequence enumerating unlabeled trees, the
[Note: this is Sloane'sA000055,
apparently Neil's favorite sequence, since this is the sequence that you get as "default"]
To see
the first 20 terms of the sequence enumerating regular 3-hypergraphs
[Note: this is Sloane'sA000665, except that he only gives
11 terms.]
To get
the number of unlabeled simple graphs with 6 vertices where each vertex has degree 3 equals
To get the number of unlabeled multigraphsgraphs with 6 vertices where each vertex has degree 3 equals
Written: July 20, 2010.
This page is a short description of the Maple package
GraphEnumeration.
It implements the Polya-Redfield method as it is described in Frank Harary and
Edgar Palmer clasic masterpiece "Graph Enumeration".
ezra();
for the list of the main procedures. For help with a specific procedure type: ezra(ProcedureName);
For example, with help with procedure Tseq, type:
ezra(Tseq);
Sample Input and Output for GraphEnumeration
the
input
gives the output.
input
gives the output.
input
gives the output.
input
gives the output.
the
input
gives the output.
the input
gives the output.
the
input
gives the output.
Doron Zeilberger's Maple Programs