%0 Journal Article
%T Simple permutations of the classes Av(321, 3412) and Av(321, 4123) have polynomial growth
%A Lutful Karim
%A Nargis Khan
%J International Journal of Combinatorial Optimization Problems and Informatics
%D 2011
%I International Journal of Combinatorial Optimization Problems and Informatics
%X A permutation is called simple if its only blocks i.e. subsets of the permutation consist of singleton and the permutation itself. For example, 2134 is not a simple permutation since it consists ofa block 213 but 3142 is a simple permutation. The basis of a class of permutations is a set of patterns, which is minimal under involvement and do not belong to the permutation. In this paper we prove that the number of simple permutations an of the pattern class Av(321, 3412) follows the recurrence a(n) = a(n-1)+a(n-2) for n >= 4 and the pattern class Av(321, 4123) follows the recurrence a(n) = a(n-2)+a(n-3) for n >= 7. Thus, these pattern classes have polynomial growth.
%K Simple Permutation
%K Pattern Class
%K Basis
%K Polynomial Growth.
%U http://ijcopi.org/ojs/index.php?journal=ijcopi&page=article&op=view&path%5B%5D=51&path%5B%5D=75