The combstruct package contains functions that randomly generate a uniform distribution of objects belonging to a given combinatorial class, as well as to count the number of objects of a given size in that class. It is possible to list all the objects of a given size. For more information, see combstruct[allstructs].

In some cases, it is also possible to create an iterator which traverses all the objects in the given class one by one. For more information, see combstruct[iterstructs].

You can find the system of generating function equations that counts the objects in the class. For more information, see combstruct[gfeqns].

You can specify the truncated series corresponding to each generating function. For more information, see combstruct[gfseries].

In some cases, you can find the generating functions explicitly. For more information, see combstruct[gfsolve].

Properties of the structures can be defined by means of attribute grammars.

You can find the system of multi-variate generating functions. For more information, see combstruct[agfeqns].

You can specify the truncated series corresponding to each generating function.  For more information, see combstruct[agfseries].

A combinatorial class is defined by writing a grammar specification that describes it. In this way, an extensive collection of different classes can be defined. For example, the system applies to all regular and context-free grammars, grammars to define binary trees, plane general trees, necklaces, functional graphs, expression trees, and others. All grammar specifications can be labeled or unlabeled. For more details, see combstruct[specification].

There are also predefined structures built into the system (combinations, permutations, compositions, and integer partitions). For more information, see combstruct[structures].

You can control the choice of algorithms used by the system.  For details, see combstruct[options].

To learn more about the combstruct package, see the example worksheet Introduction to the Combinatorial Structures Package.

Each command in the combstruct package can be accessed by using either the long form or the short form of the command name in the command calling sequence.

The following is a list of available commands.

To display the help page for a particular combstruct command, see Getting Help with a Command in a Package.

$\mathrm{with}\left(\mathrm{combstruct}\right)$

$\left[\mathrm{agfeqns}\,\mathrm{agfmomentsolve}\,\mathrm{agfseries}\,\mathrm{allstructs}\,\mathrm{count}\,\mathrm{draw}\,\mathrm{finished}\,\mathrm{gfeqns}\,\mathrm{gfseries}\,\mathrm{gfsolve}\,\mathrm{iterstructs}\,\mathrm{nextstruct}\right]$

$\mathrm{bin}≔\left\{B=\mathrm{Union}\left(Z\,\mathrm{Prod}\left(B\,B\right)\right)\right\}\:$

$\mathrm{count}\left(\left[B\,\mathrm{bin}\,\mathrm{labeled}\right]\,\mathrm{size}=5\right)$

$1680$

$\mathrm{gfsolve}\left(\mathrm{bin}\,\mathrm{labeled}\,z\right)$

$\left\{B\left(z\right)=\frac{1}{2}-\frac{\sqrt{1-4z}}{2}\,Z\left(z\right)=z\right\}$

$\mathrm{necklace}≔\left\{N=\mathrm{Cycle}\left(\mathrm{Union}\left(\mathrm{red}\,\mathrm{blue}\right)\right)\,\mathrm{blue}=\mathrm{Atom}\,\mathrm{red}=\mathrm{Atom}\right\}\:$

$\mathrm{draw}\left(\left[N\,\mathrm{necklace}\,\mathrm{unlabeled}\right]\,\mathrm{size}=10\right)$

$\mathrm{Cycle}\left(\mathrm{red}\,\mathrm{red}\,\mathrm{red}\,\mathrm{red}\,\mathrm{blue}\,\mathrm{blue}\,\mathrm{red}\,\mathrm{red}\,\mathrm{blue}\,\mathrm{blue}\right)$

$\mathrm{allstructs}\left(\mathrm{Permutation}\left(\left[a\,b\,c\right]\right)\right)$

$\left[\left[a\,b\,c\right]\,\left[a\,c\,b\right]\,\left[b\,a\,c\right]\,\left[b\,c\,a\right]\,\left[c\,a\,b\right]\,\left[c\,b\,a\right]\right]$

Delest, M.P., and Fedou, J.M. "Attribute grammars are useful for combinatorics." Theoretical Computer Science. Vol. 98. (1992): 65-76.

Dutour, I., and Fedou, J.M. "Object grammars and random generation." Discrete Mathematics and Theoretical Computer Science. Vol. 2. (1998): 49-63.

Flajolet, P.; Zimmermann, P.; and Cutsem, B.V. "A calculus for the random generation of combinatorial structures." Theoretical Computer Science. (1194): 135.

Note: The previous reference provides the theoretical background of the labeled structures case.

Flajolet, P.; Salvy, B.; and Zimmermann, P. "Automatic average-case analysis of algorithms." Theoretical Computer Science. Series A Vol. 79 No. 1. (1991).

Flajolet P.; Salvy, B.; and Zimmermann, P. "Lambda-Upsilon-Omega: an assistant algorithms analyzer."  In: "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes," edited by T. Mora. Lecture Notes in Computer Science. Vol. 357. (1989).

Flajolet, P.; Salvy, B.; and Zimmermann, P. "Lambda-Upsilon-Omega, the 1989 cookbook." INRIA Research Reporti. No. 1073. (1989).

Mishna, M. "Attribute grammars and automatic complexity analysis." INRIA Research Report. No. 4021. (2000).

Murray, Eithne. "Random generation of unlabeled combinatorial structures." Summary of a seminar talk by Paul Zimmermann.  In: "Algorithms Seminar, 1993-1994," edited by Bruno Salvy. INRIA Research Report. No. 2381. (1994).

Zimmermann, Paul. "Gaïa: a package for the random generation of combinatorial structures." Maple Technical Newsletter, (1994).

Note: Gaïa is an earlier version of combstruct.

Note: This list also contains references relevant to a previous incarnation of this program called Lamba-Upsilon-Omega, (Lambda-Upsilon-Omega) (LUO).  They contain the theoretical foundations of this program and examples of other applications. The code for LUO, written in a combination of Maple and Caml, and electronic versions of these papers are available from http://algo.inria.fr/libraries/software.html#luo.