Harary, Frank; Palmer, Edgar M. Graphical enumeration. (English) Zbl 0266.05108 New York-London: Academic Press. XIV, 271 p. $ 4.50 (1973). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 13 ReviewsCited in 354 Documents MathOverflow Questions: Is there a generalisation of the Polya Enumeration Theorem to actions of wreath products? MSC: 05C30 Enumeration in graph theory 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics × Cite Format Result Cite Review PDF Online Encyclopedia of Integer Sequences: Number of series-reduced trees with n nodes. Number of trees with n unlabeled nodes. Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point). Number of graphs on n unlabeled nodes. Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Number of dissections of an n-gon, rooted at an exterior edge, asymmetric with respect to that edge. Number of oriented rooted trees with n nodes. Also rooted trees with n nodes and 2-colored non-root nodes. Number of self-complementary graphs with n nodes. Number of inequivalent ways of dissecting a regular (n+2)-gon into n triangles by n-1 non-intersecting diagonals under rotations and reflections; also the number of (unlabeled) maximal outerplanar graphs on n+2 vertices. Number of asymmetric trees with n nodes (also called identity trees). Number of oriented trees with n nodes. Number of unlabeled simple digraphs with n nodes. Number of connected graphs with one cycle of length 4. Number of outcomes of unlabeled n-team round-robin tournaments. Number of n-state 2-input 1-output automata with one initial and one terminal state. a(-1)=1 by convention; for n >= 0, a(n) = number of irreducible Boolean functions of n variables. Number of 3-uniform hypergraphs on n unlabeled nodes, or equivalently number of relations with 3 arguments on n nodes. Number of symmetric relations on n nodes. Number of colorings of labeled graphs on n nodes using exactly 2 colors, divided by 4. Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements. Number of oriented graphs (i.e., digraphs with no bidirected edges) on n unlabeled nodes. Also number of complete digraphs on n unlabeled nodes. Number of antisymmetric relations (i.e., oriented graphs with loops) on n unlabeled nodes is A083670. Number of connected labeled graphs with n nodes. Number of connected graphs with n nodes. Number of unlabeled mappings (or mapping patterns) from n points to themselves; number of unlabeled endofunctions. Number of functional digraphs (digraphs of functions on n nodes where every node has outdegree 1 and loops of length 1 are forbidden). a(n) is the number of partitions of n into at most 3 parts; also partitions of n+3 in which the greatest part is 3; also number of unlabeled multigraphs with 3 nodes and n edges. Number of series-reduced planted trees with n nodes. Number of series-reduced rooted trees with n nodes. Number of rooted planar 2-trees with n nodes. Number of topologies, or transitive digraphs with n unlabeled nodes. Number of unlabeled nonseparable (or 2-connected) graphs (or blocks) with n nodes. Number of self-converse digraphs with n nodes. Number of self-converse relations on n points. Number of unlabeled Euler graphs with n nodes; number of unlabeled two-graphs with n nodes; number of unlabeled switching classes of graphs with n nodes; number of switching classes of unlabeled signed complete graphs on n nodes; number of Seidel matrices of order n. Number of unlabeled planar trees (also called plane trees) with n nodes. Number of acyclic digraphs (or DAGs) with n labeled nodes. Number of connected Eulerian graphs with n unlabeled nodes. Number of rooted triangular cacti with 2n+1 nodes (n triangles). Number of triangular cacti with 2n+1 nodes (n triangles). Number of multigraphs with 4 nodes and n edges. Sum a(n) x^n / n = log (1 + Sum g(n) x^n ), where g(n) is # graphs on n nodes (A000088). Related to number of digraphs. Number of weakly connected digraphs with n unlabeled nodes. Number of self-complementary digraphs with n nodes. Number of acyclic digraphs with n unlabeled nodes. Number of unilateral digraphs with n unlabeled nodes. Number of connected line graphs with n nodes. Number of species (or ”main classes” or ”paratopy classes”) of Latin squares of order n. a(n) = floor( 2^(n*(n-1)/2) / n! ). Number of labeled plane 2-trees with n nodes. Number of Hamiltonian graphs with n nodes. Erroneous version of A006841. The number of superpositions of cycles of order n of the groups E_3 and D_n. The number of superpositions of cycles of order n of the groups S_3 and D_n. Number of rooted planar trees with n non-root nodes: circularly cycling the subtrees at the root gives equivalent trees. Number of asymmetric (not necessarily connected) graphs with n nodes. Number of n-node unlabeled connected graphs without endpoints. Number of n-node unlabeled graphs without endpoints (i.e., no nodes of degree 1). Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group). Number of forests with n unlabeled nodes. Apéry numbers: n*C(2*n,n). Number of planted matched trees with n nodes. Number of 3-regular (trivalent) labeled graphs on 2n vertices with multiple edges and loops allowed. a(n) = 2^(n*(n-1)/2). Number of colorings of labeled graphs on n nodes using exactly 3 colors, divided by 48. Number of colorings of labeled graphs on n nodes using exactly 4 colors, divided by 4!*2^6. Permutation arrays of period n. Number of rooted connected graphs where every block is a complete graph. Number of homeomorphically irreducible (or series-reduced) trees with n pendant nodes, or continua with n non-cut points, or leaves. Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2). Number of labeled connected graphs with n nodes and 0 cutpoints (blocks or nonseparable graphs). Number of multigraphs with 5 nodes and n edges. Number of loopless multigraphs with 6 nodes and n edges. Number of loopless multigraphs with 7 nodes and n edges. Number of loopless multigraphs with 8 nodes and n edges. Number of rooted trees where root has degree 4. Number of labeled Eulerian graphs with n nodes. Number of connected graphs on n unlabeled nodes where every block is a complete graph. Number of rooted polygonal cacti (Husimi graphs) with n nodes. Number of polygonal cacti (Husimi graphs) with n nodes. Number of increasing rooted polygonal cacti (Husimi graphs) with n nodes. Number of labeled polygonal cacti (Husimi graphs) with n nodes. Number of unlabeled strongly connected digraphs with n nodes. a(n) = Sum_{k=1..n} n! * n^(n-k+1) / (n-k)!. Number of labeled 2-trees with n nodes. Number of labeled 3-trees with n nodes. Line-labeled 2-trees with n nodes. Number of labeled 4-trees with n nodes. Two-dimensional simplicial complexes on n labeled nodes. Two-dimensional simplicial complexes on n unlabeled nodes. Erroneous version of A003088. Erroneous version of A001930. Erroneous version of A058337. Number of n-node graphs containing a 4-cycle. Irregular triangle read by rows: T(n,k) = number of binary codes of length n with k words (n >= 0, 0 <= k <= 2^n); also number of 0/1-polytopes with vertices from the unit n-cube; also number of inequivalent Boolean functions of n variables with exactly k nonzero values under action of Jevons group. Number of loopless multigraphs on infinite set of nodes with n edges. Number of strongly connected tournaments on n nodes. Number of digraphs on n unlabeled nodes with a sink (or, with a source). Number of asymmetric digraphs with n nodes. Triangle read by rows: T(n,k) is the number of unlabeled directed graphs on n nodes with k arcs, k=0..n*(n-1). A simple grammar. Number of 3-multigraphs on n nodes. Number of 4-multigraphs on n nodes. Number of 5-multigraphs on n nodes. Number of labeled rooted connected graphs. a(n) = 2^(n^2 - n). Number of nonisomorphic binary n-state automata. Number of nonisomorphic n-state automata with binary inputs and outputs. Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones under action of dihedral group of the square D_4. Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges. Number of unlabeled 2-trees with n nodes. Triangular array T(n,k) giving the number of labeled even graphs with n nodes and k edges for n >= 0 and 0 <= k <= n*(n-1-[0 == n mod 2])/2 (with no trailing zeros). Number of inequivalent n-state 2-input 2-output automata with respect to input and output permutations. Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1). Finite automata. Number of nonisomorphic binary n-state automata without output under input permutations. Number of nonisomorphic connected binary n-state automata without output under input permutations. Number of inequivalent n-state 2-input 2-output automata with respect to an input permutation. Number of inequivalent n-state 1-input n-output automata. Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry. Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1). Triangle of trees with n nodes and k leaves, 2 <= k <= n. Expansion of log( dC(x)/dx ), C(x) = e.g.f. for labeled connected graphs (A001187). Triangle T(n,k) of number of unilaterally connected digraphs on n unlabeled nodes with k arcs, k=0..n*(n-1). Number of connected labeled graphs with n edges and n nodes. Number of connected loop-free Eulerian digraphs with n nodes. Number of digraphs with indegree = outdegree at each vertex, or Eulerian digraphs (including disconnected graphs) with n nodes. Triangle T(n,k) = C_n(k) where C_n(k) = number of k-colored labeled graphs with n nodes (n >= 1, 1<=k<=n). Number of 2-trees rooted at an edge. Number of 2-trees rooted at an asymmetric edge. Number of 2-colored labeled graphs with n nodes. Number of 3-colored labeled graphs with n nodes. Number of 4-colored labeled graphs with n nodes. Triangle T(n,k) = C_n(k)/2^(k*(k-1)/2) where C_n(k) = number of k-colored labeled graphs with n nodes (n >= 1, 1 <= k <= n). Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n). Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero. Triangle T(n,k) is the number of labeled graphs of even degree with n nodes and k edges (n >= 0, 0 <= k <= n(n-1)/2). Triangle read by rows: T(n,k) = number of connected graphs with one cycle of length m = n - k + 1 and n nodes (n >= 3 and 1 <= k <= n - 2). a(n) = (1/(2n)) * Sum_{d|n} phi(d) * 2^(2n/d) + (2^((n-4)/2), if n is even). Erroneous version of A051504. Erroneous version of A000665. Number of graphs with 3 distinct components. Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes. Number of n-node labeled graphs without endpoints. Number of labeled acyclic digraphs with n nodes containing exactly n-2 points of in-degree zero. Triangular array T(n,k) giving number of connected graphs with n labeled nodes and k edges (n >= 1, 0 <= k <= n(n-1)/2). Number of 2-trees rooted at an asymmetric end-edge. Number of 2-trees rooted at any symmetric edge. Number of 2-trees rooted at a triangle. Number of 2-trees rooted at a triangle with 3 similar edges. Number of 2-trees rooted at a triangle with two similar edges. G.f.: A(x) = (x-2*x^2-2*x^3-(1+x)*sqrt(1-4*x^2)+sqrt(1-4*x^6))/(2*x^2). Number of oriented trees rooted at an arc. Irregular triangle read by rows giving T(n,k) = number of rooted graphs on n + 1 nodes with k edges (n >= 0, 0 <= k <= n(n-1)/2). Total number of nodes in all labeled graphs on n nodes. Irregular triangle read by rows: coefficients of cycle index polynomial for the cyclic group C_n, Z(C_n,x), multiplied by n. Number of edge-rooted unlabeled graphs on n nodes. Triangle read by rows: T(n,k) = number of edge-rooted unlabeled graphs having n nodes and k edges, n > 0, 0 < k <= n*(n-1)/2. Number of edge-rooted unlabeled graphs with n edges. Number of connected nonhamiltonian graphs with n nodes. Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1). Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color. Table read by antidiagonals: T(n,k) = number of multigraphs with n vertices and k edges, with no loops allowed (n >= 1, k >= 0). Irregular triangular array read by rows T(n,k) is the number of 2-colored labeled graphs that have exactly k edges, n >= 2, 0 <= k <= A033638(n). Coefficients for the cycle index polynomial for the dihedral group D_n multiplied by 2n, n>=1, read as partition polynomial. Coefficients for the cycle index polynomial for the cyclic group C_n multiplied by n, n>=1, read as partition polynomial. Coefficients of the cycle index polynomial for the alternating group A_n multiplied by n!/2, n>=1, read as partition polynomial. Partition array for the number of representative necklaces (only cyclic symmetry) with n beads, each available in n colors. Only the color type (signature) matters. Partition array for the number of representative bracelets (dihedral symmetry D_n) with n beads, each available in n colors. Only the color type (signature) matters. Number of unlabeled graphs on n nodes that have exactly two non-isomorphic components. Number of rooted unlabeled trees where the root node has degree 2 and both branches are distinct. Number of 4-colored labeled graphs on n vertices. Triangle starting at row 3 read by rows of the number of permutations in the n-th Dihedral group which are the product of k disjoint cycles, d(n,k), n >= 3, 1 <= k <= n. Triangular array read by rows: T(n,k) is the number of rooted labeled simple graphs on {1,2,...,n} such that the root is in a component of size k; n>=1, 1<=k<=n. Multisets of multisets corresponding to integer partitions lambda, drawn from |lambda| symbols, where the sizes of the multisets are given by the elements of lambda as is the total number of occurrences of each symbol. Number of nonisomorphic subsets of n cards of a standard deck of 52 cards under action of symmetric group S_4 acting on the suits. Triangular array read by rows. T(n,k) is the number of labeled trees with black and white nodes having exactly k black nodes, n>=0, 0<=k<=n. Number of unlabeled unrooted trees on 2n vertices with all vertices of odd degree. a(n) = number of unlabeled rooted trees on n nodes with an even number of endpoints. a(n) = number of unlabeled rooted trees on n nodes with an odd number of endpoints. Number of multisets of n permutations of [n] with the symmetric group acting on the permutation elements. Number of colorings of an n X n grid with at most three interchangeable colors under rotational and reflectional symmetry. Number of colorings of an n X n grid with at most four interchangeable colors under rotational and reflectional symmetry. Number of colorings of an n X n grid with at most five interchangeable colors under rotational and reflectional symmetry. Number of colorings of an n X n grid with any number of interchangeable colors under rotational and reflectional symmetry. The exponential transform of sigma(n). The logarithmic transform of sigma(n). Number of n-node labeled graphs with one endpoint. Number of n-node labeled graphs with two endpoints. Number of n-node labeled graphs with three endpoints. Number of terms in the cycle index Z(S_n X S_n) of the Cartesian product of the symmetric group S_n with itself that contain q cycles, where 1 <= q <= n*n. (Triangular array.) Number of sets of sequences of total length n over an alphabet of n letters with the symmetric group acting on the letters. Irregular triangular array read by rows: T(n,k) is the number of non-isomorphic unlabeled weakly connected digraphs on n nodes and with k arcs. Irregular triangular array read by rows: T(n,k) = number of non-isomorphic unlabeled connected graphs with loops on n nodes and with k edges. Triangle read by rows, 1 <= k <= n: T(n,k) is the number of non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly three colors under translational symmetry. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly two colors under translational symmetry and swappable colors. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly three colors under translational symmetry and swappable colors. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly four colors under translational symmetry and swappable colors. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using exactly five colors under translational symmetry and swappable colors. Triangle read by rows, 1 <= k <= n: T(n,k) = non-isomorphic colorings of a toroidal n X k grid using any number of swappable colors. Number of configurations, excluding reflections and color swaps, of n beads each of three colors on a string. Number of configurations, excluding reflections and color swaps, of n beads each of four colors on a string. Number of configurations, excluding reflections and color swaps, of n beads each of five colors on a string. Number of configurations, excluding reflections and color swaps, of n beads each of six colors on a string. Triangle T(n,k) read by rows, giving number of bipartite graphs with n nodes (n >= 0) and k edges (0 <= k <= floor(n/2*n/2)). Number of SNPN-equivalence classes of Boolean functions of n or fewer variables. Non-isomorphic colorings of the edges of a cube using at most n colors under rotational symmetries and permutations of the colors. Non-isomorphic proper colorings of the 3 X 3 grid graph using at most n colors under rotational and reflectional symmetries. Non-isomorphic proper colorings of the 4 X 4 grid graph using at most n colors under rotational and reflectional symmetries. Non-isomorphic proper colorings of the 5 X 5 grid graph using at most n colors under rotational and reflectional symmetries. Number of labeled graphs on n nodes with two connected components. Number of labeled graphs on n nodes with three connected components. Number of labeled graphs on n nodes with four connected components. Number of unlabeled bicolored bipartite graphs on 2n nodes having n nodes of each color with no edges between vertices of the same color and edges having two colors and allowing the node color classes to be interchanged. Edge colors are swappable (permuted by the symmetric group). Number of unlabeled bicolored bipartite graphs on 2n nodes having n nodes of each color with no edges between vertices of the same color and edges having three colors and allowing the node color classes to be interchanged. Edge colors are swappable (permuted by the symmetric group). Triangular array T(n,k): the number of not necessarily proper colorings of the complete graph on n unlabeled vertices minus an edge using exactly k colors. T(n,k) is the number of labeled Eulerian graphs with n vertices and k edges (according to Harary and Palmer) or the number of labeled connected Eulerian graphs with n vertices and k edges (according to Mallows and Sloane); irregular triangle T, read by rows (n >= 0 and 0 <= k <= n*(n-1)/2). T(n,k) is the number of unlabeled even graphs with n vertices and k edges; irregular triangular array T read by rows (n >= 0, 0 <= k <= n*(n-1)/2). Number of colorings of an n X n grid with at most n interchangeable colors under rotational and reflectional symmetry. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 2, 2, ..., n, n] into k nonempty submultisets, for 1 <= k <= 2n. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 1, 2, 2, 2, ..., n, n, n] into k nonempty submultisets, for 1 <= k <= 3n. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 1, 1, 2, 2, 2, 2, ..., n, n, n, n] into k nonempty submultisets, for 1 <= k <= 4n. Number of multiset partitions of [1,1,1,1,2,2,2,2,...,n,n,n,n] into nonempty multisets. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 1, 2, 2, 2, ..., n, n, n] into k nonempty subsets, for 3 <= k <= 3n. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 1, 1, 2, 2, 2, 2, ..., n, n, n, n] into k nonempty subsets, for 4 <= k <= 4n. Triangle read by rows. Number T(n, k) of partitions of the multiset [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, ..., n, n, n, n, n] into k nonempty subsets, for 5 <= k <= 5n. Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n. Number of directed multigraphs including self-loops on n vertices and n edges. Number of bracelets consisting of three instances each of n swappable colors. Number of bracelets consisting of four instances each of n swappable colors. Number of bracelets consisting of five instances each of n swappable colors.