Yianni Alexander
CS4205 – Combinatorial Mathematics Research Project
Purpose:
The Combinatorial Mathematics Website Toolkit contains
various tools to accompany a textbook in combinatorial mathematics. The toolkit is meant to facilitate and
explore the concepts taught in an introductory combinatorial mathematics
course. The fundamentals of
combinatorial mathematics are centered on understanding all kinds of sequences,
and the associated finite calculus. The
first tools are designed to explore those fundamentals by spelling out all
kinds of sequences, which can contain iterations such as products and
summations, special combinatorial numbers such as Eulerain
and
Another important concept in understanding combinatorial mathematics is found in prime numbers and divisibility. These concepts can be studied by the student using the tools that explore prime factorization, the Extended Euclidean Algorithm, and residue encoding and decoding based upon the Chinese Remainder Theorem.
User Interface:
Expression and Sequence Evaluator:
The rules for using the Expression and Sequence Evaluator as follows: Please define the expression in terms of the variable ‘n’. For iterations (summations and products), use lower case letters to designate variables. There is NO implicit multiplication, so statements such as “3n” will be incorrectly evaluated, make sure to use an ‘*’ whenever possible, e.g. “3*n”. The “Difference” button is used to calculate difference curves for the sequence as long as there are enough terms to calculate it. The expression must be defined in the text box labeled “\f{n}=”. Check the “Evaluate Sequence” checkbox if you wish to evaluate the expression on the sequence from n = 0 to the integer listed in the text box labeled “n=”, otherwise only the expression will be evaluated on the specified n and designated in the “f(n)=” text box. All status messages concerning state of the evaluator as well as any error messages will be stated in the text area labeled “Status messages:”.
The order of precedence for operations is:
Special operations are:
|
Syntax |
Description |
|
\S{i,a,b,expr} |
Summation with index i=a to b on expr |
|
\P{i,a,b,expr} |
Product with index i=a to b on expr |
|
\LN{a} |
Natural logarithm |
|
\LG{a} |
Binary logarithm |
|
\LOG{b,a} |
Logarithm of 'a' with base 'b' |
|
\H{a} |
Harmonic number |
|
\C{a,b} |
'a' choose 'b' |
|
\STS{a,b} |
|
|
\STC{a,b} |
|
|
\EUL{a,b} |
Euler Number |
|
\BELL{a} |
|
|
\DER{a} |
Derangement Number |
|
\FIB{a} |
Fibonacci Number |
|
\FALL{a,b} |
Falling power: 'a' to the 'b' falling |
|
\FL{a} |
Floor of 'a' |
|
\CL{a} |
Ceiling of 'a' |
|
\E |
2.71828... |
|
\PI |
3.14159... |
Recursive Expression and Sequence Evaluator:
The rules for the Recursive Expression and Sequence Evaluator are the same as the Expression and Sequence Evaluator except for some modifications to accommodate recursive implementation. The main noticeable difference is the section used to define initial conditions for the recurrence. Define any recursive initial conditions in the “Recursive Initial Conditions” section. Double click the list to pop the highest recursive initial condition. Also, the lower case letter ‘f’ can no longer be used as a variable in iterations, as the syntax to designated recursive calls in the expression definition is “\f{expr}” where the expression “expr” must be evaluated to result in an integer greater than or equal to zero.
Double Sum Evaluator:
The Double Sum Evaluator is used to explore the terms and sums of a double sum. The indices are pre-defined as ‘i’ for the outer sum and ‘j’ for the inner sum. Thus, the bounds of the outer sum can be defined in terms of ‘n’, the bounds for the inner sum can be defined in terms of ‘n’ and ‘i’, and the summand expression can be defined in terms of ‘n’, ‘i’, and ‘j’. The rules for expression definition are similar to the Expression and Sequence Evaluator, except the special operations for summations and products are excluded. The variable ‘n’ must be defined as a positive integer; however, it is not required to be used in the definition of the bounds or the summand expression.
Polynomial Divider for OGF’s:
The polynomial divider is used to explore sequences for ordinary generating functions. The “Degree=” drop-down menu is used to specify the maximum degree, either for the numerator or denominator, with a maximum degree of 10. The first ‘n’ coefficients will be listed according to the definition of ‘n’. Coefficients specified in the numerator and denominator can be any type of number, where blanks specify an empty term, thus, the highest coefficient that is not blank will be the degree of the respective numerator and denominator.
Prime Factorization:
Prime Factorization is fairly straightforward, given a positive integer greater than 1, the tool will give each integer’s unique factorization into a power of primes. The largest stored prime in the tool is 62,081 so any integer greater than that cannot be evaluated.
Extended Euclidean Algorithm:
The Extended Euclidean Algorithm tool is fairly straightforward, given two positive integers where ‘n’ must be greater than ‘m’, will evaluate the greatest common denominator using the extended Euclidean algorithm and explore each step, ‘j’, in the process, as well as give integers N and M for each step where N*n + M*m = gcd(n,m). Also, for each step, the integer quotient will be designated as ‘q’.
Application of Chinese Remainder Theorem:
The Application of Chinese Remainder Theorem toolkit utilizes the Chinese Remainder Theorem to explore residue encoding and decoding. These applets has two parts: one for the encoding, one for decoding.
For encoding residues, you can have a system of up to 10 relatively prime moduli, and denote the value ‘n’ to which you want to encode the system.
For decoding residues, the system can be designated with a maximum of 6 tuples of moduli, decoding two at a time, until a single decoding remains.
Number Triangles:
The Number Triangles tool is fairly straightforward. Define an ‘n’ as a non-negative integer and select which triangle to explore using the “Triangle=” drop-down menu. There are only four number triangles possible: Pascal, Stirling Subset, Stirling Cycle, and Eulerian.
Bunside-Pólya Counting:
This tool allows you to explore Burnside-Pólya Counting to count equivalence relations under the Dihedral Group (all rotations and reflections) for two types of graphs: n * n checkerboards, and n-beaded necklaces. ‘n’ is a parameter specified by the user, and for the purposes of Polya counting, the user can select between 2 and 6 different colors (some of the computations for high-valued parameters may take a while…). For a counting, each symmetry will be listed along with its permutation in disjoint cycle form, the cycle structure resulting from the permutation, and the Pólya substitution for each cycle structure. Combining the cycle structures and Pólya substitution yields a cycle index polynomial and a Pólya polynomial, respectively.
Creation and Maintenance Notes:
The entire project was developed using Java applets. So make sure all your Java plug-in “stuff” is working properly. If your browser supports Java and you are still having problems, there may be some issues concerning security and firewalls so make sure that you’re settings aren’t too restrictive. If you have any questions concerning the project, think this readme needs updating or correction, and/or if the project or any of the applets need updating or correcting, or if you have any comments, please e-mail me at yianni.alexander@gmail.com.