Combinatorics and Graph Theory


A Class of Multinomial Permutations Avoiding Object Clusters

Authors: Richard J. Mathar

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.

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

Download: PDF

Submission history

[v1] 2015-11-02 15:32:57

Unique-IP document downloads: 168 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus