Thank you for visiting the combinatorial object server, otherwise known as COS. We hope that you will find it informative and useful.
The idea is that you specify a type of combinatorial object, together with specific parameter values, and COS will return to you a list of all such objects. COS can generate permutations, combinations, various types of trees, unlabelled graphs, linear extensions of posets, pentomino puzzle solutions, numerical partitions, and a host of other combinatorial objects. In some instances you may specify the order in which the objects are generated (such as lexicographic or a Gray code order). Almost always the output may be presented in a variety of formats which you may specify. These different formats include well-known correspondences and representations of the objects. For example, permutations may be ouput in one-line notation, in cycle notation, or as a pair of Standard Young Tableau under the Schensted correspondence.
We hope that a great variety of people will use COS. It is meant to be used by researchers and educators who wish to easily produce list of combinatorial objects. The elementary objects such as permutations, combinations, and subsets are well-known and studied in the elementary and secondary schools. In fact, there's another version, called The Amazing Mathematical Object Factory, and directed to K12 students and educators, that used to run on Canada's "Schoolnet" before they broke it (the previous link is now to the local version) -- please give it a try if you're looking for something simpler and less comprehensive than COS. On COS, there are some recreational items, such as pentomino puzzle solutions which can be understood by anyone. And then there's more complicated objects such as graphical partitions, linear extensions of posets, primitive polynomials, and unlabelled graphs which will be of interest to university students and scientific/mathematical researchers.
We've made considerable effort to ensure that the output of each program is correct, but we make no guarantees.
We are always curious about who is using COS. Please send us a little note if you find COS useful in your work, if you have suggestions, or if you find something not working quite right.
|This icon, which appears at the top and bottom of each page, takes you to a list of pages which broadly classifies the objects. Select the appropriate classification for the type of object you wish to generate.|
|This icon, which appears at the top and bottom of each page, takes you to a list of information pages about various classes of combinatorial objects.|
|This icon, which appears at the top and bottom of each page, returns you to this page.|
With each type of object is an associated information page. This page provides explanation of the object, the COS options, and the algorithms used to generate the object. Where relevant we also give the number of objects of that type for small parameter values along with the corresponding number in Sloane and Plouffe's The Encyclopedia of Integer Sequences (Academic Press, 1995) or in Sloane's On-Line Encyclopedia of Integer Sequences. For some of the objects programs in Pascal and/or C may be downloaded from the information page.
Each generation page starts with a table asking What Type? where you specify the type of object and possibly the ordering. Next comes a table called Input where you specify the values of the input parameters. A final table called Output is where you specify the form of the output; i.e., the representations of the combinatorial objects that are to be used on output. Exactly one "What Type" option and at least one "Output" option must be specified. Every object (with the exception of pentominoes with custom shape) requires an input parameter named n. Some, such as combinations, require at least one other parameter. Required extra parameters are mentioned under "What Type". Sometimes parameters are optional and these are indicated in smaller font by a comment enclosed in square brackets.
Clicking on this icon, which appears on every information page,
takes you to the corresponding generation page.|
Clicking on this icon, which appears on every generation page and on
every output page, takes you to the corresponding information page.|
Don't you hate it when a link takes you a page that contains nothing
except a message saying it's under construction!
Lots of our pages are under construction, and we expect that we
will always have pages under construction.
However, you are warned of the state of all links and various
options before you use them by one of the following
|Partially functional, but not all
options implemented. Don't be deterred; most of it works well.|
|Don't waste your time.|
Most of the algorithms used are very fast and have the CAT property. This means that the total amount of computation, divided by the number of objects is bounded by a constant; i.e., only a constant amount of computation is done per object, in an amortized sense. Programs with this property have the following icon next to them.
= CAT (Constant Amortized Time) algorithm.
= CAT algorithm not previously published for this object.
The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
There have been 5783 visitors to this page since May 16, 2000 .
(These are hits to this page only; in total there have been 2738639 hits on the pages of COS since May 16, 2000.)
(Previously, there were over 230,000 hits on the pages of COS.)
It was last updated Monday, 23-May-2011 12:56:55 PDT.
©Frank Ruskey, 1995-2002.
The small print: This is an experimental prototype.
Much work will be required to bring it to full functionality.
The 200 object limit is for testing purposes, eventually it will be
If you like what you see so far, please send us some encouragement.
This page and its successors are designed to be viewed with
[You are using CCBot/2.0].
On viewers that don't support tables and subscripts it won't look so good.
Here are some acknowledgements, awards, and
a list of links to our pages.