Combinatorics and Graph Theory

1511 Submissions

[2] viXra:1511.0225 [pdf] replaced on 2015-12-05 16:57:21

Counting 2-way Monotonic Terrace Forms over Rectangular Landscapes

Authors: Richard J. Mathar
Comments: 27 Pages. Added Section 6 (cut sets) and removed the inconclusive Appendix B.

A terrace form assigns an integer altitude to each point of a finite two-dimensional square grid such that the maximum altitude difference between a point and its four neighbors is one. It is 2-way monotonic if the sign of this altitude difference is zero or one for steps to the East or steps to the South. We provide tables for the number of 2-way monotonic terrace forms as a function of grid size and maximum altitude difference, and point at the equivalence to the number of 3-colorings of the grid.
Category: Combinatorics and Graph Theory

[1] viXra:1511.0015 [pdf] submitted on 2015-11-02 15:32:57

A Class of Multinomial Permutations Avoiding Object Clusters

Authors: Richard J. Mathar
Comments: Pages 9 to 21 are a JAVA program distributed under the LGPL v3.

The multinomial coefficients count the number of ways (of permutations) of placing a number of partially distinguishable objects on a line, taking ordering into account. A well-known two-parametric family of counts arises if there are objects of c distinguishable colors and m objects of each color, m*c objects in total, to be placed on line. In this work we propose an algorithm to count the permutations where no two objects of the same color appear side-by-side on the line. This eliminates all permutations with "clusters" of colors. Essentially we represent filling the line sequentially with objects as a tree of states where each node matches one partially filled line. Subtrees are merged if they have the same branching structure, and weights are assigned to nodes in the tree keeping track of how many mergers take place. This is implemented in a JAVA program; numerical results confirm Hardin's earlier counts for this kind of restricted permutations.
Category: Combinatorics and Graph Theory