ABSTRACT
An elaborate enumeration procedure, including some recursion relations, has been supplied in respect of the (132)-avoiding patterns of some special class of permutation subwords. It has been discovered that the (132)-avoiding subwords of these patterns portray some useful algebraic characteristics which also possess some important number-theoretic consequences. This report also established an algorithmic method of constructing graphical models for these patterns. It was therefore discovered that in comparison with the special (123)-avoiding category reported earlier, this scheme gives rise to some multigraphs each of which contains an Eulerian circuit. The emerging permutation patterns were also used in the construction of nxn Latin squares. Further, the length |An,subwords| reproduces the sequence A005408. We have thus achieved another combinatorial interpretation of this sequence of odd numbers.
PDF Abstract XML References
How to cite this article
URL: https://scialert.net/abstract/?doi=tasr.2007.334.340
INTRODUCTION
Given a sequence η nsisting of n ements arranged in a given pattern and another sequence ω having m elements such that m<n then; ω is said to be contained as a pattern in η provided η has a subsequence which is order isomorphic to ω. If η does not contain ω we say that it avoids ω. According to Cameron (2002), there are many ways of viewing a permutation of the finite set {1,...,n}. For instance, there is a combinatorial approach and a group-theoretic approach. This versatility in the subject matter of permutation avoidance is obviously a factor that attracted increased attention of researchers to this growing discipline over the last decade.
A classical definition of pattern was given by Anders (2001) and requires that a pattern σεSk and a permutation πεSn avoids σ if there is no subsequence in π whose letters are in the exact relative order as those of σ. For instance, σεSn avoids (123) if there exist no 1<i<j<k<n such that π (I) <π (j) <π (k).
It is some times useful to differentiate between a subsequence and a subword. Thus, according to Sergi and Marc (2003), a permutation pattern say, π contains another subpattern say π as a subword if there exists some m consecutive elements πl+1,...,πl+m much that ρ (πl+1,...,πl+m) where ρ is a reduction consisting in the relabelling of the desired elements with {1,...,m} so that they keep the same unique order relationships they had in π.
The combinatorics of succession involving 5-element samples was earlier reported by the author (Ibrahim 2004;2006a). Furthermore, an elaborate enumeration procedure was communicated (Ibrahim, 2006a) using (123)-avoiding patterns of these numbers where; for the first time, the sample size was allowed to vary. However, only sample sizes whose order is a prime number were found to be applicable. That is, the enumeration scheme completely breaks down every time a non-prime is introduced.
The above limiting factor represents the fundamental difference in terms of the nature and enumeration methods as well as the analytical properties of the two schemes. It is also the basis upon which this paper is built. Thus, while the basis set for the special (123)-avoiding patterns is a regular subgroup of alternating group An (Ibrahim, 2006b), the basis set for this special (132)-avoiding subwords is the set of natural numbers. The enumeration scheme therefore, holds true for all sample sizes whose order is at least three. Further, the simple recursion relations obtained clearly manifest the fact that the (132)-avoiding patterns of the numbers provide a straight forward method of establishing a combinatorial discourse of these types of configurations whose order of arrangement is strictly consecutive. For instance, if we are given η = 123451234 then, under the given conditions it is very easy to see that this sequence avoids any subsequence whose pattern is (132). The key factor utilized in this respect is the consecutiveness in both the natural order {1,2,...,n} and the order s1<s2<...<sn in the arrangement of the terms of the sequence.
METHOD OF CONSTRUCTION
The Key factor in the theory of pattern-avoiding classes is to determine their enumeration procedure. This, according to Atkinson (2005), involves finding the number of permutations of each length in a given class. In what follows, the fundamental procedure for obtaining this class of permutation patterns is supplied. The governing conditions as well as the basic assumptions involved will also be highlighted.
Enumeration Scheme
• | Elements are arranged consecutively such that any pair λi λj are in (132)-avoiding pattern if and only if |
j = I+1, with j≤m and m ≥3 | (1) |
where m is the number of element that are consecutively arranged in a given pattern.
• | The enumeration scheme involves doubt regarding which of the elements comes first in the desired pattern. |
• | Absolute certainty is required that a desired pattern, which ever it is, is achieved, by the end of the enumeration scheme. |
• | Both the number m of the elements in the desired pattern and their respective identities are known. |
• | Each of the m elements is as likely as any other to be the first element in the desired pattern. |
By desired pattern here is meant the pairing procedure (Ibrahim, 2005). Thus, the central problem which this enumeration scheme tries to solve concerns the lack of knowledge of the first element in the desired pattern. It follows that once this is known the enumeration scheme becomes undesirable since the remaining elements automatically follow due to the requirement of strict consecutiveness in this category of permutation patterns.
Relationship Between the Length of the Special (132)-avoiding Permutation Sequences and Their Corresponding Subwords
Based on the outlines of the enumeration scheme the following relations can be used to determine the size |An,subwords| of these patterns for a given (132)-avoiding sequences consisting of n elements.
|An,subwords| = n+(m-1) | (2) |
where m≤n represents the size of subwords of the (132)-avoiding patterns of these numbers. It is also required that m≥3.
In view of the assumption that the identity of the first element is in doubt, coupled with the requirement that a desired pattern be established, (2) can be used to construct a set of equally likely subwords thus:
N (An,subwords) = n | (3) |
where, N (An,subwords) represents the number of subwords which are (132)-avoiding and n≥3.
APPLICATION
In what follows, some applications are derived with respect to some algebraic methods.
Cyclic Methods
Without loss of generality, let us consider a mapping β that preserves consecutiveness. That is, β generates elements that are consecutively moved by some composition of mapping for some finite i = 1,2,...,n so that the first element moves through a maximum of n positions. We therefore state the following claim:
Claim
Up to isomorphism, βn reproduces n sets of consecutively arranged elements of the (132) -avoiding subwords each of length n.
Proof
Observe that under the given condition, for some non empty set Ω of n symbols such that Ω = {1,2,...,n}.
It then follows that
Observe that under the usual cycle notion; CC1 to CCn represent the same element (1 2 . . . n). However, since order is important under the prevailing conditions of arrangement of members of Ω, each CCi is distinct for any i>0. Hence the result.
As an illustration, some permutation patterns as well as their corresponding (132)-avoiding subwords are provided in Table 1 for samples of size up to seven.
Observe that the length |An,subwords\| corresponding to the number of digits in the sequence appearing in the first row of each entry m of Table 1 gives rise to the sequence 3,5,7,9,11,13,15,17,19,... which reproduces the terms of the sequence A005408 (Sloane, 2003).
Table 1: | Some special patterns that are (132)-avoiding for samples of size 3 to 7 |
Note: In table 1 commas have been used in the listing of two digit numbers so as distinguish them from the one digit type |
Construction of Latin Square
We attempt below to use the pattern of arrangement as established in the aforementioned section to construct a Latin square. We begin with a proposition
Proposition
The special (132)- avoiding order of arrangement An,subwords of elements of Ω can be used to construct Latin squares whose size depend on n, the number of elements in Ω.
Proof
Denote that A = 1, B = 2, C = 3, D = 4 in that order for elements of Ω then, carryout a rearrangement as follows:
Step 1
Write down the symbols in the top row so that A comes first, B comes second C comes third and subsequently
Step 2
In the second row, shift all the symbols to the left one place forward so that A moves to the second position B moves to the third and subsequently for the remaining symbols.
Step 3
Continue this process shifting each one place to the right of the previous position until all the symbols are exhausted.
We can also denote that A = 1, B =2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, J = 9, K = 10, L = 11 and M = 12. Then, using m = 7 (Table 1) we note that the sequence 123456789,10,11,12,123456 translates into ABCDEFGHIJKLMABCDEF. Furthermore, the corresponding subwords can be used to construct a 7x7 Latin square thus
Graph Theoretic Consequences
Graph models have proved useful in construction of interconnection networks (Drager and Fettweis, 2002; nd). Further, Graph algorithms have also served as means of optimization especially with regards to transportation networks (Ibrahim, 2007). The purpose in this paper is to provide a theoretical basis for constructing Eulerian circuits using a defined algorithm. Consider the arrangements of points of Ω such that three, four, five, etc. of the points are arranged consecutively to each other. That is, they form subwards which are (132) avoiding (Table 1).
In order for the realization of graph models for the subwords as in Table 1 the following algorithm can be used.
This algorithm can be extended up to a suitably chosen m the number of vertices (nodes) in accordance with the size of the special subwords as mentioned before.
Graphical Illustrations
Using the algorithms as in the aforementioned we can construct some multigraphs Fig. 1.
Fig. 1a-c: | multigraphs for the length m of subwoards equal to 3, 4 and 5, respectively |
SUMMARY OF RESULTS
The (132)-avoiding patterns of this special class of pattern avoiding permutations, represent an extension of the theory as reported earlier by the Author (Ibrahim, 2004; 2005; Ibrahim and Audu, 2005).
The following can be readily established from the foregoing discussions on these special patterns:
• | In contrast to the special (123)-avoiding patterns reported earlier, the special (132)-avoiding pattern can be constructed for every m≥3 irrespective of whether or not m is a prime. This explains that the precedence relation in this category of permutation patterns is uniform since only strictly consecutive terms are paired. |
• | The number m of distinct terms that are consecutively arranged and the number of possible subwords arising from a sequence of length n coincide. This result points to an important property of these patterns which is of statistical significance (Ibrahim, 2004). |
• | The (132)-avoiding category of these patterns can be used conveniently to generate the outermost nodes of a Cayley graphs that can in turn be used to construct interconnection networks (Drager and Fettweis (2002). Thus, using suitable permutations on these patterns we can generate the whole of the Cayley graph for a given number of vertices |
• | This class of pattern-avoiding system can be used to construct Latin squares for samples of size m>2. |
• | In contrast to the (123)-avoiding scheme reported earlier (Ibrahim, 2006b), the pattern of subwords in this scheme gives rise to multigraphs each containing an Eulerian circuit. |
• | This special enumeration scheme provides a combinatorial interpretation of the sequence A005408of the on line encyclopeadia of integer sequence. |
CONCLUSION
The (132)-avoiding category of these permutation patterns is not cyclic in nature, as was the case with the special restricted (123)-avoiding type reported earlier. This pattern therefore requires a further governing condition of consecutiveness if the cyclic method is applied so as not to end up producing the same element several times. This restriction has not been encountered in the group-theoretic treatment of the special (123)-avoiding type. However, due to the nature of arrangement of the terms of the subwords, the graph-theoretic method conveniently produces multigraphs.
RECOMMENDATIONS
It follows that restrictions on the pattern avoiding subsequences do give rise to a variety of systems that are of combinatorial significance. The interrelationship of this subject area with the other algebraic structures such as groups and graphs does provide interesting results. It is hoped that further researches be directed towards investigating more results arising from this interrelationship.
As an open problem, a detailed algorithm could be developed and corresponding multigraphs models determined for cases involving fixed number of nodes but varying combination of edges.
REFERENCES
- Ibrahim, A.A., 2004. Group theoretical interpretation of baraat al dhimmah models for prayers that are not strictly consecutive mathematical association of nigeria. Proceedings of the 10th Annual National conference of the National Association of Agricultural Economists, (NAAE'04), Niergia, pp: 35-46.