Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References
Research Article
 

Some Transformation Schemes Involving the Special (132)-Avoiding Permutation Patterns and a Binary Coding: An Algorithmic Approach



Aminu Alhaji Ibrahim
 
ABSTRACT

Some transformations have been designed and used on the Special (132)-avoiding Patterns of Permutations reported earlier by the Author. In this report, an algorithm has also been used to derive some matrix representations of the special permutation Scheme using binary coding. By the current development, an important theorem has now been formulated expressing some useful relationships between this scheme and a system of cellular algebra.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Aminu Alhaji Ibrahim , 2008. Some Transformation Schemes Involving the Special (132)-Avoiding Permutation Patterns and a Binary Coding: An Algorithmic Approach. Asian Journal of Algebra, 1: 10-14.

DOI: 10.3923/aja.2008.10.14

URL: https://scialert.net/abstract/?doi=aja.2008.10.14

INTRODUCTION

The Special (132)-avoiding Permutation Pattern was earlier on Studied (Ibrahim and Audu, 2005; Ibrahim, 2007) in relation to some group theoretic Properties, Graph theoretic properties and enumeration procedure as permutation-avoiding subwords. Algorithmic method was also employed (Ibrahim, 2007) in the construction of some Eulerian circuits using the said scheme.

Algorithms are viewed, in Mathematics and computing as a set of procedure for accomplishing some task which posses a given initial state and a well defined end state. Algorithms have been used extensively in relation to graph-theoretic models (Ibrahim, 2006, 2007). Further, in relation to interconnection networks (Drager and Fettwies, 2002), algorithms have also proved to be very useful tools.

In this study, a relationship has been established between the special permutation pattern and cellular algebra. This procedure not only provide a good exposition of the subject matter of pattern avoidance but also introduces some new dimensions of theoretic interpretations of this class of permutation patterns in terms of other mathematical structures; such as coherent configurations.

In order for a good understanding of the paper, some basic notions are supplied below:

Cellular Algebra
A cellular algebra otherwise called a coherent configuration, can be defined as an algebra on square matrices of complex numbers having some finite basis

(1)

defined on a nonempty set

Ω = {1, 2,...,n}
(2)

and consisting of matrices whose entries are strictly 0 and 1 satisfying the following:

where, K = All 1-matrix.
There exists a subset of (1) whose sum is I; the identity matrix.
The set Γfinite of 10 is closed under transposition. That is, for each i, there exists i* such that (Bi)T = Bi*

(3)

Where, qi,jk in Eq. 3 are integers such that 1≤i, j, k≤m for some positive integer m. These integers are called intersection numbers.

A detailed treatment of cellular algebra can be found in notes due to Cameron (n.d) especially in relation to association scheme and permutation groups (http://kissme.shinshu-u.ac.jp/as/). Further, Delsarte (1973) did one of the good investigations on relationships between association schemes and cellular algebra.

However, the approach in this research is on the use of succession schemes to propose a study of and a relationship there from with a system of cellular algebra.

Permutation Pattern
The listing 1,2,...,n of objects in a definite order is called a sequence. And where a particular order of arrangement is desired, such an arrangement becomes an ordered arrangement governed by a pattern and According to Ibrahim (2007) each such permutation pattern σ ∈ Sn {n} naturally results into a certain arrangement of 1,2,...,n given by:

σ(1)σ(2)...σ(n)
(4)

and is referred to as the arrangement associated with a permutation pattern of points of a nonempty set Ω.

On the other hand, permutation avoiding a particular pattern of arrangement can be understood in the light of two sequences: a sequence π consisting of n elements arranged in a given pattern and another sequence σ having m elements such that m<n. In such situations σ is said to be contained as a pattern in π provided π has a subsequence which is order isomorphic to σ. If π does not contain σ it is said to avoid it. The set of all the σ-avoiding permutations is denoted Sn(σ).

ALGEBRAIC INTERPRETATIONS

The fact that this special succession scheme forms a cyclic Structure has been reported earlier (Ibrahim, 2007). It was also reported that the scheme could be used to construct some interesting eulerian circuits (Ibrahim, 2007).

The main point of emphasis in this communication is therefore focused on finding out some further algebraic properties of this scheme as applied to a five element sample and, by extension, to samples of size n where n>5. This is achieved in this research by discovering some general rules satisfied by the scheme for all n∈|An,subwords|, n = 3,4,... (Ibrahim, 2007). In particular, the research identifies some useful transformation schemes using the established theoretic properties of the special permutation pattern in conjunction with the algorithmic procedure to discover some interesting interrelationships between the different structures of cyclic elements, the special permutation-avoiding patterns and the matrices of binary coding scheme.

Finally, the study proposes an open problem in the recommendation section.

Formulation of Cyclic Structures
Consider the special (132) avoiding subwords as reported (Ibrahim, 2007). For sake of clarity, the format of the succession is treated in the following proposition which also establishes a group-theoretic formalism of the pattern as mentioned before.

Proposition One
Consider a mapping βn(x) on points x of a non empty set Δ whose cardinality is |Δ| = n which acts on x in such a way as to generate a cycle of consecutive positive integers with x as the first element of a permutation pattern whose highest integer is the cardinality |Δ| = n of a non-empty set. Then, βn generates cycles which posses some interesting group-theoretic property and which define a special pattern avoidance when viewed as subwords.

Proof
Based on the given conditions βn: Δ → (12...n) so that βn(x) = (x(x+1)...n) and inductively over all the points of Δ.

Without loss of generality, the following cycles are generated subsequently

((x + 1) (x + 2) ...x), ((x + 2) (x + 3) ... (x + 1)),...(n x ... (n–1))

The results follow since each of the identical cycles forms a two group when paired with identity permutation (1). Further, when viewed as permutation subwords each of the elements generated represents a different subword which is also (132)-avoiding.

Example
For sample if we consider a set Δ of size |Δ| = 5 we have thus:

β5 (1) = (1 2 3 4 5), β5 (2) = (2 3 4 5 1), ..., β5 (5) = (5 1 2 3 4),

Formulation of Algorithm
The following algorithm transforms the permutation patterns constructed in the foregoing into matrix representation using a special coding scheme.

Step One
In the first row of the nxn matrix assign a 1 to the position ai,j corresponding to the value i of the ith matrix element. The rest are assigned a 0.

Step Two
Shift the entry 1 in the subsequent rows so that the non-zero entries shift consecutively towards subsequent positions in the right of the diagonal.

Step Three
Continue the procedure in step two until a square matrix is formed.

Step Four
End if a square matrix is formed. Otherwise go to step two.

Example
The following example uses the above algorithm to construct matrices An for sample of size n = 5.

It follows that for an mxm matrix, the algorithm is iterated m times so that at any stage t, the position of the non-zero entry on the first row is shifted rightwards as ai,j thereby generating m matrix elements.

As a further illustration, consider the following proposition and the accompanying example.

Proposition Two
Perform a transformation μ from elements of the special (132)-avoiding subword βn(x) to elementsof corresponding nxn matrix representations An defined by μ: βn(x) → An. Then, the points x,x+1,... of the nonempty set Δ correspond to the positions Ax,Ax+1,... of the corresponding nxn matrix representations An which also specify the positions ax,j,ax+1,j of the non-zero entries in such matrix representation.

Proof
The general form of βn(x) is βn(x) = (x(x + 1). . . n). Thus, for x = 1 we have the cycle (1,2,...n). It then follows that the points 1,2,…n represent the positions of the non-zero entries of the first matrix representation A1.

Using similar technique we can generate the rest of the transformations. That is, we can transform βn(2) to A2, βn(3) to A3 and subsequently.

The result follows.

APPLICATION

We state below a very interesting result linking up the enumeration scheme of the reported permutation pattern with cellular algebra.

Theorem
Denote by An = {β5(1), β5(2),...,βn(n)} the set of cycles βn(x) of length 5 and assume a transformation as in proposition two. Then A5 forms a cellular algebra.

Proof
Use A1 to A5 as in the example provided above. Then, define a linear space over with Ai, i = 1,2,...n as the basis where Ai s are as given above.
Then;

(3)

Similarly, for each i ∈ {1,...,n} there exist i such that AiT = Ai. This follows readily since each Ai a is square matrix coupled with the fact that the sum total of all the five matrices gives rise to Eq. 3 above.

As a counter example, suppose for some i ∈ {1, ..., n}, AiT produces a matrix containing a 2 as an entry so that as,j = 2 say, for some s ∈ Ω. This will imply that for some matrix As s ∈ Ω one of the entriesis a 2 contradicting the definition of Ai hence, the result.

CONCLUSION

The special (132)-avoiding pattern of permutation under study has proved to have some useful algebraic-theoretic properties. In this study, more properties of this pattern have been investigated through some transformations using binary coding scheme and based on a designed algorithm.

RECOMMENDATION AND OPEN PROBLEM

More transformations should be investigated using this special succession scheme so as to further reveal more of the useful properties and applications. In addition, researches should focus on revealing more interrelationships of this permutation pattern and other algebraic structures. For instance, more relationship can be investigated in relation to semi groups and loops.

REFERENCES
Cameron, P.J., 1999. Coherent Configurations, Association Schemes and Permutation Groups. Lecture Notes, Combinatorial Study Group.

Delsarte, P.H., 1973. An algebraic approach to the association scheme of coding theory. Philiphs Res. Suppl., 10.

Drager, T. and G.P. Fettweis, 2002. Energy savings with appropriate interconnection networks in Parallel DSP. Colloquim des Schwerpunklprogramms der Dculschen Forscungsgescllschaft VIVA: 35-42, Chemnitz, Germany.

Ibrahim, A.A. and M.S. Audu, 2005. Group theoretical properties of some class of (123) and (132)-avoiding patterns: An enumeration scheme. Afr. J. Natl. Sci., 8: 79-84.

Ibrahim, A.A., 2006. A counting scheme and some algebraic properties of a class of special permutation patterns. (In Press).

Ibrahim, A.A., 2007. An enumeration scheme and some algebraic properties of a special (132)-avoiding class of permutation patterns. Trends Applied Sci. Res., 2: 334-340.
CrossRef  |  Direct Link  |  

©  2019 Science Alert. All Rights Reserved
Fulltext PDF References Abstract