This section is based upon the paper J. H. Redfield, ``The Theory of Group-Reduced Distributions'', American J. Math.,49 (1927) 433-455, and is an application of group theory to enumeration problems. It is a development of the work by P. A. MacMahon on the application of symmetric functions and Hammond operators to combinatorial theory.
The theory is based upon the power sum symmetric functions which are the sum of the -th powers of the variables. The cycle index of a permutation is an expression that specifies the sizes of the cycles of a permutation, and may be represented as a partition. A partition of a non-negative integer n is a collection of positive integers called its parts whose sum is n. For example, the partition will be used to represent and will indicate that the permutation has two cycles of length 3, one of length 2 and two of length 1. The cycle index of a permutation group is the sum of the cycle indices of its permutations divided by the number of permutations. The cycle indices of certain groups are provided.
The operation complete returns the cycle index of the symmetric group of order n for argument n. Alternatively, it is the -th complete homogeneous symmetric function expressed in terms of power sum symmetric functions.
The operation elementary computes the -th elementary symmetric function for argument n.
The operation alternating returns the cycle index of the alternating group having an even number of even parts in each cycle partition.
The operation cyclic returns the cycle index of the cyclic group.
The operation dihedral is the cycle index of the dihedral group.
The operation graphs for argument n returns the cycle index of the group of permutations on the edges of the complete graph with n nodes induced by applying the symmetric group to the nodes.
The cycle index of a direct product of two groups is the product of the cycle indices of the groups. Redfield provided two operations on two cycle indices which will be called ``cup'' and ``cap'' here. The cup of two cycle indices is a kind of scalar product that combines monomials for permutations with the same cycles. The cap operation provides the sum of the coefficients of the result of the cup operation which will be an integer that enumerates what Redfield called group-reduced distributions.
We can, for example, represent complete 2 * complete 2 as the set of objects a a b b and complete 2 * complete 1 * complete 1 as c c d e.
This integer is the number of different sets of four pairs.
For example,
This integer is the number of different sets of four pairs no two pairs being equal.
For example,
In this case the configurations enumerated are easily constructed, however the theory merely enumerates them providing little help in actually constructing them.
Here are the number of 6-pairs, first from a a a b b c, second from d d e e f g.
Here it is again, but with no equal pairs.
The number of 6-triples, first from a a a b b c, second from d d e e f g, third from h h i i j j.
The cycle index of vertices of a square is dihedral 4.
The number of different squares with 2 red vertices and 2 blue vertices.
The number of necklaces with 3 red beads, 2 blue beads and 2 green beads.
The number of graphs with 5 nodes and 7 edges.
The cycle index of rotations of vertices of a cube.
The number of cubes with 4 red vertices and 4 blue vertices.
The number of labeled graphs with degree sequence 2 2 2 1 1 with no loops or multiple edges.
Again, but with loops allowed but not multiple edges.
Again, but with multiple edges allowed, but not loops
Again, but with both multiple edges and loops allowed
Having constructed a cycle index for a configuration we are at liberty to evaluate the components any way we please. For example we can produce enumerating generating functions. This is done by providing a function f on an integer i to the value required of , and then evaluating eval(f, cycleindex).
For the integers 0 and 1, or two colors.
For the integers 0, 1, 2, ... we have this.
The coefficient of is the number of graphs with 5 nodes and n edges.
Note that there is an eval function that takes two arguments. It has the signature:
This function is not normally exposed (it will not normally be considered in the list of eval functions) as it is only useful for this particular domain. To use it we ask that it be considered thus:
and now we can use it:
The coefficient of is the number of necklaces with n red beads and n-8 green beads.
The coefficient of is the number of partitions of n into 4 or fewer parts.
The coefficient of is the number of partitions of n into 4 boxes containing ordered distinct parts.
The coefficient of is the number of different cubes with n red vertices and 8-n green ones.
The coefficient of is the number of different cubes with integers on the vertices whose sum is n.
The coefficient of is the number of graphs with 5 nodes and with integers on the edges whose sum is n. In other words, the enumeration is of multigraphs with 5 nodes and n edges.
Graphs with 15 nodes enumerated with respect to number of edges.
Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10 red beads.
The operation SFunction is the S-function or Schur function of a partition written as a descending list of integers expressed in terms of power sum symmetric functions.
In this case the argument partition represents a tableau shape. For example 3,2,2,1 represents a tableau with three boxes in the first row, two boxes in the second and third rows, and one box in the fourth row. SFunction [3,2,2,1] counts the number of different tableaux of shape 3, 2, 2, 1 filled with objects with an ascending order in the columns and a non-descending order in the rows.
This is the number filled with a a b b c c d d.
The configurations enumerated above are:
This is the number of tableaux filled with 1..8.
The coefficient of is the number of column strict reverse plane partitions of n of shape 3 2 2 1.
The smallest is
The domain constructor DeRhamComplex creates the class of differential forms of arbitrary degree over a coefficient ring. The De Rham complex constructor takes two arguments: a ring, coefRing, and a list of coordinate variables.
This is the ring of coefficients.
These are the coordinate variables.
This is the De Rham complex of Euclidean three-space using coordinates x, y and z.
This complex allows us to describe differential forms having expressions of integers as coefficients. These coefficients can involve any number of variables, for example, f(x,t,r,y,u,z). As we've chosen to work with ordinary Euclidean three-space, expressions involving these forms are treated as functions of x, y and z with the additional arguments t, r and u regarded as symbolic constants.
Here are some examples of coefficients.
We now define the multiplicative basis elements for the exterior algebra over R.
This is an alternative way to give the above assignments.
Now we define some one-forms.
A well-known theorem states that the composition of exteriorDifferentialexteriorDifferentialDeRhamComplex with itself is the zero map for continuous forms. Let's verify this theorem for alpha.
We see a lengthy output of the last expression, but nevertheless, the composition is zero.
Now we check that exteriorDifferentialexteriorDifferentialDeRhamComplex is a ``graded derivation'' D, that is, D satisfies:
We try this for the one-forms alpha and beta.
Now we define some ``basic operators'' (see OperatorXmpPage ).
We also define some indeterminate one- and two-forms using these operators.
This allows us to get formal definitions for the ``gradient'' ...
the ``curl'' ...
and the ``divergence.''
Note that the De Rham complex is an algebra with unity. This element 1 is the basis for elements for zero-forms, that is, functions in our space.
To convert a function to a function lying in the De Rham complex, multiply the function by ``one.''
A current limitation of Axiom forces you to write functions with more than four arguments using square brackets in this way.
Now note how the system keeps track of where your coordinate functions are located in expressions.
In this example of Euclidean three-space, the basis for the De Rham complex consists of the eight forms: 1, dx, dy, dz, dx*dy, dx*dz, dy*dz, and dx*dy*dz.
All rationals have repeating decimal expansions. Operations to access the individual digits of a decimal expansion can be obtained by converting the value to RadixExpansion(10). More examples of expansions are available in BinaryExpansionXmpPage , HexadecimalExpansionXmpPage , and RadixExpansionXmpPage .
The operation decimaldecimalDecimalExpansion is used to create this expansion of type DecimalExpansion.
Arithmetic is exact.
The period of the expansion can be short or long ...
or very long.
These numbers are bona fide algebraic objects.
DistributedMultivariatePolynomial which is abbreviated as DMP and HomogeneousDistributedMultivariatePolynomial, which is abbreviated as HDMP, are very similar to MultivariatePolynomial except that they are represented and displayed in a non-recursive manner.
The constructor DMP orders its monomials lexicographically while HDMP orders them by total order refined by reverse lexicographic order.
These constructors are mostly used in Gröbner basis calculations.
Note that we get a different Gröbner basis when we use the HDMP polynomials, as expected.
GeneralDistributedMultivariatePolynomial is somewhat more flexible in the sense that as well as accepting a list of variables to specify the variable ordering, it also takes a predicate on exponent vectors to specify the term ordering. With this polynomial type the user can experiment with the effect of using completely arbitrary term orderings. This flexibility is mostly important for algorithms such as Gr\"{o}bner basis calculations which can be very sensitive to term ordering.
For more information on related topics, see ugIntroVariablesPage in Section ugIntroVariablesNumber , ugTypesConvertPage in Section ugTypesConvertNumber , PolynomialXmpPage , UnivariatePolynomialXmpPage , and MultivariatePolynomialXmpPage .
Axiom provides two kinds of floating point numbers. The domain Float (abbreviation FLOAT) implements a model of arbitrary precision floating point numbers. The domain DoubleFloat (abbreviation DFLOAT) is intended to make available hardware floating point arithmetic in Axiom. The actual model of floating point DoubleFloat that provides is system-dependent. For example, on the IBM system 370 Axiom uses IBM double precision which has fourteen hexadecimal digits of precision or roughly sixteen decimal digits. Arbitrary precision floats allow the user to specify the precision at which arithmetic operations are computed. Although this is an attractive facility, it comes at a cost. Arbitrary-precision floating-point arithmetic typically takes twenty to two hundred times more time than hardware floating point.
The usual arithmetic and elementary functions are available for DoubleFloat. Use )show DoubleFloat to get a list of operations or the HyperDoc browse facility to get more extensive documentation about DoubleFloat.
By default, floating point numbers that you enter into Axiom are of type Float.
You must therefore tell Axiom that you want to use DoubleFloat values and operations. The following are some conservative guidelines for getting Axiom to use DoubleFloat.
To get a value of type DoubleFloat, use a target with @, ...
a conversion, ...
or an assignment to a declared variable. It is more efficient if you use a target rather than an explicit or implicit conversion.
You also need to declare functions that work with DoubleFloat.
this complains but succeeds
Use package-calling for operations from DoubleFloat unless the arguments themselves are already of type DoubleFloat.
By far, the most common usage of DoubleFloat is for functions to be graphed. For more information about Axiom's numerical and graphical facilities, see Section ugGraph , ugProblemNumeric , and FloatXmpPage .
The EqTable domain provides tables where the keys are compared using eq?eq?EqTable. Keys are considered equal only if they are the same instance of a structure. This is useful if the keys are themselves updatable structures. Otherwise, all operations are the same as for type Table. See TableXmpPage for general information about tables.
The operation tabletableEqTable is here used to create a table where the keys are lists of integers.
These two lists are equal according to =, but not according to eq?eq?List.
Because the two lists are not eq?eq?List, separate values can be stored under each.
The Equation domain provides equations as mathematical objects. These are used, for example, as the input to various solvesolveTransSolvePackage operations.
Equations are created using the equals symbol, =.
The left- and right-hand sides of an equation are accessible using the operations lhslhsEquation and rhsrhsEquation.
Arithmetic operations are supported and operate on both sides of the equation.
Equations may be created for any type so the arithmetic operations will be defined only when they make sense. For example, exponentiation is not defined for equations involving non-square matrices.
Note that an equals symbol is also used to test for equality of values in certain contexts. For example, x+1 and y are unequal as polynomials.
If an equation is used where a Boolean value is required, then it is evaluated using the equality test from the operand type.
If one wants a Boolean value rather than an equation, all one has to do is ask!
A function that does not return directly to its caller has Exit as its return type. The operation error is an example of one which does not return to its caller. Instead, it causes a return to top-level.
The function gasp is given return type Exit since it is guaranteed never to return a value to its caller.
The return type of half is determined by resolving the types of the two branches of the if.
Because gasp has the return type Exit, the type of if in half is resolved to be Integer.
For functions which return no value at all, use Void. See ugUserPage in Section ugUserNumber and VoidXmpPage for more information.
Expression is a constructor that creates domains whose objects can have very general symbolic forms. Here are some examples:
This is an object of type Expression Integer.
This is an object of type Expression Float.
This object contains symbolic function applications, sums, products, square roots, and a quotient.
As you can see, Expression actually takes an argument domain. The coefficients of the terms within the expression belong to the argument domain. Integer and Float, along with Complex Integer and Complex Float are the most common coefficient domains.
The choice of whether to use a Complex coefficient domain or not is important since Axiom can perform some simplifications on real-valued objects
... which are not valid on complex ones.
Many potential coefficient domains, such as AlgebraicNumber, are not usually used because Expression can subsume them.
Note that we sometimes talk about ``an object of type Expression.'' This is not really correct because we should say, for example, ``an object of type Expression Integer'' or ``an object of type Expression Float.'' By a similar abuse of language, when we refer to an ``expression'' in this section we will mean an object of type Expression R for some domain R.
The Axiom documentation contains many examples of the use of Expression. For the rest of this section, we'll give you some pointers to those examples plus give you some idea of how to manipulate expressions.
It is important for you to know that Expression creates domains that have category Field. Thus you can invert any non-zero expression and you shouldn't expect an operation like factor to give you much information. You can imagine expressions as being represented as quotients of ``multivariate'' polynomials where the ``variables'' are kernels (see KernelXmpPage ). A kernel can either be a symbol such as x or a symbolic function application like sin(x + 4). The second example is actually a nested kernel since the argument to sin contains the kernel x.
Actually, the argument to sin is an expression, and so the structure of Expression is recursive. KernelXmpPage demonstrates how to extract the kernels in an expression.
Use the HyperDoc Browse facility to see what operations are applicable to expression. At the time of this writing, there were 262 operations with 147 distinct name in Expression Integer. For example, numernumerExpression and denomdenomExpression extract the numerator and denominator of an expression.
Use DDExpression to compute partial derivatives.
See ugIntroCalcDerivPage in Section ugIntroCalcDerivNumber for more examples of expressions and derivatives.
See ugIntroCalcLimitsPage in Section ugIntroCalcLimitsNumber and ugIntroSeriesPage in Section ugIntroSeriesNumber for more examples of expressions and calculus. Differential equations involving expressions are discussed in ugProblemDEQPage in Section ugProblemDEQNumber . Chapter 8 has many advanced examples: see ugProblemIntegrationPage in Section ugProblemIntegrationNumber for a discussion of Axiom's integration facilities.
When an expression involves no ``symbol kernels'' (for example, x), it may be possible to numerically evaluate the expression.
If you suspect the evaluation will create a complex number, use complexNumeric.
If you know it will be real, use numeric.
The numeric operation will display an error message if the evaluation yields a calue with an non-zero imaginary part. Both of these operations have an optional second argument n which specifies that the accuracy of the approximation be up to n decimal places.
When an expression involves no ``symbolic application'' kernels, it may be possible to convert it a polynomial or rational function in the variables that are present.
This also works for the polynomial types where specific variables and their ordering are given.
Finally, a certain amount of simplication takes place as expressions are constructed.
For simplications that involve multiple terms of the expression, use simplify.
See ugUserRulesPage in Section ugUserRulesNumber for examples of how to write your own rewrite rules for expressions.
Factored creates a domain whose objects are kept in factored form as long as possible. Thus certain operations like * (multiplication) and gcdgcdFactored are relatively easy to do. Others, such as addition, require somewhat more work, and the result may not be completely factored unless the argument domain R provides a factorfactorFactored operation. Each object consists of a unit and a list of factors, where each factor consists of a member of R (the base), an exponent, and a flag indicating what is known about the base. A flag may be one of ``nil'', ``sqfr'', ``irred'' or ``prime'', which mean that nothing is known about the base, it is square-free, it is irreducible, or it is prime, respectively. The current restriction to factored objects of integral domains allows simplification to be performed without worrying about multiplication order.
In this section we will work with a factored integer.
Let's begin by decomposing g into pieces. The only possible units for integers are 1 and -1.
There are three factors.
We can make a list of the bases, ...
and the exponents, ...
and the flags. You can see that all the bases (factors) are prime.
A useful operation for pulling apart a factored object into a list of records of the components is factorListfactorListFactored.
If you don't care about the flags, use factorsfactorsFactored.
Neither of these operations returns the unit.
Recall that we are working with this factored integer.
To multiply out the factors with their multiplicities, use expandexpandFactored.
If you would like, say, the distinct factors multiplied together but with multiplicity one, you could do it this way.
We're still working with this factored integer.
We'll also define this factored integer.
Operations involving multiplication and division are particularly easy with factored objects.
If we use addition and subtraction things can slow down because we may need to compute greatest common divisors.
Test for equality with 0 and 1 by using zero?zero?Factored and one?one?Factored, respectively.
Another way to get the zero and one factored objects is to use package calling (see ugTypesPkgCallPage in Section ugTypesPkgCallNumber ).
The mapmapFactored operation is used to iterate across the unit and bases of a factored object. See FactoredFunctionsTwoXmpPage for a discussion of mapmapFactored.
The following four operations take a base and an exponent and create a factored object. They differ in handling the flag component.
This factor has no associated information.
This factor is asserted to be square-free.
This factor is asserted to be irreducible.
This factor is asserted to be prime.
A partial inverse to factorListfactorListFactored is makeFRmakeFRFactored.
The first argument is the unit and the second is a list of records as returned by factorListfactorListFactored.
Some of the operations available for polynomials are also available for factored polynomials.
You can differentiate with respect to a variable.
The FactoredFunctions2 package implements one operation, mapmapFactoredFunctions2, for applying an operation to every base in a factored object and to the unit.
Actually, the mapmapFactoredFunctions2 operation used in this example comes from Factored itself, since double takes an integer argument and returns an integer result.
If we want to use an operation that returns an object that has a type different from the operation's argument, the mapmapFactoredFunctions2 in Factored cannot be used and we use the one in FactoredFunctions2.
In fact, the ``2'' in the name of the package means that we might be using factored objects of two different types.
It is important to note that both versions of mapmapFactoredFunctions2 destroy any information known about the bases (the fact that they are prime, for instance).
The flags for each base are set to ``nil'' in the object returned by mapmapFactoredFunctions2.
For more information about factored objects and their use, see FactoredXmpPage and ugProblemGaloisPage in Section ugProblemGaloisNumber .
The File(S) domain provides a basic interface to read and write values of type S in files.
Before working with a file, it must be made accessible to Axiom with the openopenFile operation.
The openopenFile function arguments are a FileName and a String specifying the mode. If a full pathname is not specified, the current default directory is assumed. The mode must be one of ``input'' or ``output''. If it is not specified, ``input'' is assumed. Once the file has been opened, you can read or write data.
The operations readreadFile and writewriteFile are provided.
You can change from writing to reading (or vice versa) by reopening a file.
The readreadFile operation can cause an error if one tries to read more data than is in the file. To guard against this possibility the readIfCanreadIfCanFile operation should be used.
You can find the current mode of the file, and the file's name.
When you are finished with a file, you should close it.
A limitation of the underlying LISP system is that not all values can be represented in a file. In particular, delayed values containing compiled functions cannot be saved.
For more information on related topics, see TextFileXmpPage , KeyedAccessFileXmpPage , LibraryXmpPage , and FileNameXmpPage .
The FileName domain provides an interface to the computer's file system. Functions are provided to manipulate file names and to test properties of files. The simplest way to use file names in the Axiom interpreter is to rely on conversion to and from strings. The syntax of these strings depends on the operating system.
On Linux, this is a proper file syntax:
Although it is very convenient to be able to use string notation for file names in the interpreter, it is desirable to have a portable way of creating and manipulating file names from within programs.
A measure of portability is obtained by considering a file name to consist of three parts: the directory, the name, and the extension.
The meaning of these three parts depends on the operating system. For example, on CMS the file ``SPADPROF INPUT M'' would have directory ``M'', name ``SPADPROF'' and extension ``INPUT''. It is possible to create a filename from its parts.
When writing programs, it is helpful to refer to directories via variables.
If the directory or the extension is given as an empty string, then a default is used. On AIX, the defaults are the current directory and no extension.
Three tests provide information about names in the file system.
The exists?exists?FileName operation tests whether the named file exists.
The operation readable?readable?FileName tells whether the named file can be read. If the file does not exist, then it cannot be read.
Likewise, the operation writable?writable?FileName tells whether the named file can be written. If the file does not exist, the test is determined by the properties of the directory.
The newnewFileName operation constructs the name of a new writable file. The argument sequence is the same as for filenamefilenameFileName, except that the name part is actually a prefix for a constructed unique name.
The resulting file is in the specified directory with the given extension, and the same defaults are used.
The FlexibleArray domain constructor creates one-dimensional arrays of elements of the same type. Flexible arrays are an attempt to provide a data type that has the best features of both one-dimensional arrays (fast, random access to elements) and lists (flexibility). They are implemented by a fixed block of storage. When necessary for expansion, a new, larger block of storage is allocated and the elements from the old storage area are copied into the new block.
Flexible arrays have available most of the operations provided by OneDimensionalArray (see OneDimensionalArrayXmpPage and VectorXmpPage ). Since flexible arrays are also of category ExtensibleLinearAggregate, they have operations concat!, delete!, insert!, merge!, remove!, removeDuplicates!, and select!. In addition, the operations physicalLength and physicalLength! provide user-control over expansion and contraction.
A convenient way to create a flexible array is to apply the operation flexibleArray to a list of values.
Create a flexible array of six zeroes.
For set the -th element to . Display f.
Initially, the physical length is the same as the number of elements.
Add an element to the end of f.
See that its physical length has grown.
Make f grow to have room for 15 elements.
Concatenate the elements of f to itself. The physical length allows room for three more values at the end.
Use insert! to add an element to the front of a flexible array.
Create a second flexible array from f consisting of the elements from index 10 forward.
Insert this array at the front of f.
Merge the flexible array f into g after sorting each in place.
Remove duplicates in place.
Remove all odd integers.
All these operations have shrunk the physical length of f.
To force Axiom not to shrink flexible arrays call the shrinkable operation with the argument false. You must package call this operation. The previous value is returned.