Message Boards Message Boards

0
|
3740 Views
|
5 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Pattern Avoidance of Length 4 within Permutations

Mike Ingraffia
Posted 11 years ago
Hello everyone,

I need some help using Mathematica and the permutation function.  When I use the function in Mathematica "=Permutations[{1, 2, 3, 4, 5}]", it brings me all of the permutations for numbers 1 through 5 which is great. 

I need to restrict that list somehow to avoid three patterns: [1234],[1342], and [1324], seperately. For example if I want to avoid the pattern 1234, that is an increasing pattern  no results in the permutation "matrix" should contain an increasing pattern such as [12534], [12345],[23451],[21345], etc... as they are all increasing and contain that "1234" pattern.

I know I am supposed to obtain the results that there are 5! permutations of length 5 and 103 avoid the 1234 pattern,103 avoid the 1324 pattern, and103 avoid the 1342 pattern.

I also need to extend this to permutations of length 6,7,8 once I can do length 5.
I hope I am explaining this in a matter you can understand and any help would be greatly appreciated.

Thank you in advance!
POSTED BY: Mike Ingraffia
5 Replies
Sort By:
Mike Ingraffia
Mike Ingraffia
Posted 11 years ago
Reddit provided me with this:
(* Consider a list of n elements Sn (some permutation of 1..n) and a list of k elements pk (some permutation of 1..k) with k<=n. Generate all ordered subsets of Sn of length k. Apply pk^-1. Ask if any of those is OrderedQ. *)
SubsetsInversePerms[Sn_List, pk_List] :=
Module[{k = Length,
   n = Length}, #[[Ordering]] & /@
    Subsets[Sn, {k}] /; (k <= n)]
(* We don't actually need the above (but I save it in case you want to peek inside). What we want is to check if any term is OrderedQ. *)
SubsetsInversePermsAnyOrderedQ[Sn_List, pk_List] :=
Module[{k = Length, n = Length},
  Or @@ (OrderedQ[#[[Ordering]]] & /@ Subsets[Sn, {k}]) /; (k <= n)]

(* Example *)
SubsetsInversePermsAnyOrderedQ[{1, 2, 3, 4, 5}, {1, 3, 2}]
(* False *)

(* The values of False are the ones which avoid the permutation. Count the number of permutations in the group Subscript[S, n] which avoid some sequence pk. *)
NumSnAvoidingpk[n_Integer, pk_List] /; n >= Length :=
Count[SubsetsInversePermsAnyOrderedQ[#, pk] & /@ Permutations@Range@n,
   False]

(* Here we go: *)
NumAvoidingPk4[pk4_List] /; (Length[pk4] === 4) :=
TableForm[
  Transpose@Table[{n, NumSnAvoidingpk[n, pk4]}, {n, {4, 5, 6, 7, 8}}]]

NumAvoidingPk4[{1, 3, 4, 2}]
4   5    6    7     8
23  103  512  2740  15485
NumAvoidingPk4[{1, 2, 3, 4}]
4   5    6    7     8
23  103  513  2761  15767
NumAvoidingPk4[{1, 3, 2, 4}]
4   5    6    7     8
23  103  513  2762  15793
Thank you for your help, and this is what I was trying to accomplish.  Again thank you for the help you provided me with!
POSTED BY: Mike Ingraffia
Bill Simpson
Bill Simpson
Posted 11 years ago
I now see that the criteria for eliminating candidates from the set of permutations is more complicated than just removing those which have subsets in given order. That explains why my counts differ from those in your text. I don't have that text.

If you scroll down through this

http://oeis.org/search?q=1%2C2%2C6%2C23%2C103&sort=&language=english&go=Search 

then you can find some background information and references about your sequences.
If you enter longer sequences then it may narrow the result down to the particular sequence.
That doesn't directly show you how to select the desired permutations, but it might help you.

If you can describe more clearly the criteria for eliminating elements from the set of all permutations then we might be able to find a method of solving this.

Perhaps try ignoring the Mathematica syntax for the moment and just simply describe all the classes of permutations that would be eliminated if you were going to do this by hand. With that it might then be possible to think about translating it into code.
POSTED BY: Bill Simpson
Mike Ingraffia
Mike Ingraffia
Posted 11 years ago
Thank you for your response Bill! 
This is actually a lot more progress then I expected and I'm glad you were able to understand somewhat what I was looking for since I think  my directions were unclear.
This might help you more, http://imgur.com/a/oTU2B. 
The first image is a definition of pattern avoidance which I did not explain clearly.  The last 3 images focus on patterns of length four.  In the last image is the information I am trying to reproduce.  "for Sn(1324)..etc" for Sn(1234)...etc" and "for Sn(1324)...etc"
POSTED BY: Mike Ingraffia
Bill Simpson
Bill Simpson
Posted 11 years ago
 In[1]:= Length[Permutations[{1, 2, 3, 4, 5}]]
 
 Out[1]= 120
 
 In[2]:= DeleteCases[Permutations[{1, 2, 3, 4, 5}], {___, 1, ___, 2, ___, 3, ___, 4, ___}]
 
 Out[2]= {
 {1, 2, 4, 3, 5}, {1, 2, 4, 5, 3}, {1, 2, 5, 4, 3}, {1, 3, 2, 4, 5}, {1, 3, 2, 5, 4}, {1, 3, 4, 2, 5},
 {1, 3, 4, 5, 2}, {1, 3, 5, 2, 4}, {1, 3, 5, 4, 2}, {1, 4, 2, 3, 5}, {1, 4, 2, 5, 3}, {1, 4, 3, 2, 5},
{1, 4, 3, 5, 2}, {1, 4, 5, 2, 3}, {1, 4, 5, 3, 2}, {1, 5, 2, 4, 3}, {1, 5, 3, 2, 4}, {1, 5, 3, 4, 2},
{1, 5, 4, 2, 3}, {1, 5, 4, 3, 2}, {2, 1, 3, 4, 5}, {2, 1, 3, 5, 4}, {2, 1, 4, 3, 5}, {2, 1, 4, 5, 3},
{2, 1, 5, 3, 4}, {2, 1, 5, 4, 3}, {2, 3, 1, 4, 5}, {2, 3, 1, 5, 4}, {2, 3, 4, 1, 5}, {2, 3, 4, 5, 1},
{2, 3, 5, 1, 4}, {2, 3, 5, 4, 1}, {2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, {2, 4, 3, 1, 5}, {2, 4, 3, 5, 1},
{2, 4, 5, 1, 3}, {2, 4, 5, 3, 1}, {2, 5, 1, 3, 4}, {2, 5, 1, 4, 3}, {2, 5, 3, 1, 4}, {2, 5, 3, 4, 1},
{2, 5, 4, 1, 3}, {2, 5, 4, 3, 1}, {3, 1, 2, 4, 5}, {3, 1, 2, 5, 4}, {3, 1, 4, 2, 5}, {3, 1, 4, 5, 2},
{3, 1, 5, 2, 4}, {3, 1, 5, 4, 2}, {3, 2, 1, 4, 5}, {3, 2, 1, 5, 4}, {3, 2, 4, 1, 5}, {3, 2, 4, 5, 1},
{3, 2, 5, 1, 4}, {3, 2, 5, 4, 1}, {3, 4, 1, 2, 5}, {3, 4, 1, 5, 2}, {3, 4, 2, 1, 5}, {3, 4, 2, 5, 1},
{3, 4, 5, 1, 2}, {3, 4, 5, 2, 1}, {3, 5, 1, 2, 4}, {3, 5, 1, 4, 2}, {3, 5, 2, 1, 4}, {3, 5, 2, 4, 1},
{3, 5, 4, 1, 2}, {3, 5, 4, 2, 1}, {4, 1, 2, 3, 5}, {4, 1, 2, 5, 3}, {4, 1, 3, 2, 5}, {4, 1, 3, 5, 2},
{4, 1, 5, 2, 3}, {4, 1, 5, 3, 2}, {4, 2, 1, 3, 5}, {4, 2, 1, 5, 3}, {4, 2, 3, 1, 5}, {4, 2, 3, 5, 1},
{4, 2, 5, 1, 3}, {4, 2, 5, 3, 1}, {4, 3, 1, 2, 5}, {4, 3, 1, 5, 2}, {4, 3, 2, 1, 5}, {4, 3, 2, 5, 1},
{4, 3, 5, 1, 2}, {4, 3, 5, 2, 1}, {4, 5, 1, 2, 3}, {4, 5, 1, 3, 2}, {4, 5, 2, 1, 3}, {4, 5, 2, 3, 1},
{4, 5, 3, 1, 2}, {4, 5, 3, 2, 1}, {5, 1, 2, 4, 3}, {5, 1, 3, 2, 4}, {5, 1, 3, 4, 2}, {5, 1, 4, 2, 3},
{5, 1, 4, 3, 2}, {5, 2, 1, 3, 4}, {5, 2, 1, 4, 3}, {5, 2, 3, 1, 4}, {5, 2, 3, 4, 1}, {5, 2, 4, 1, 3},
{5, 2, 4, 3, 1}, {5, 3, 1, 2, 4}, {5, 3, 1, 4, 2}, {5, 3, 2, 1, 4}, {5, 3, 2, 4, 1}, {5, 3, 4, 1, 2},
{5, 3, 4, 2, 1}, {5, 4, 1, 2, 3}, {5, 4, 1, 3, 2}, {5, 4, 2, 1, 3}, {5, 4, 2, 3, 1}, {5, 4, 3, 1, 2},
{5, 4, 3, 2, 1}}

In[3]:= Length[DeleteCases[Permutations[{1, 2, 3, 4, 5}], {___, 1, ___, 2, ___, 3, ___, 4, ___}]]

Out[3]= 115

In[4]:= Length[DeleteCases[Permutations[{1, 2, 3, 4, 5}], {___, 1, ___, 2, ___, 3, ___, 4, ___} |
    {___, 1, ___, 3, ___, 4, ___, 2, ___} | {___, 1, ___, 3, ___, 2, ___, 4, ___}]]

Out[4]= 105

In[5]:= Length[DeleteCases[Permutations[{1, 2, 3, 4, 5, 6}], {___, 1, ___, 2, ___, 3, ___, 4, ___} |
   {___, 1, ___, 3, ___, 4, ___, 2, ___} | {___, 1, ___, 3, ___, 2, ___, 4, ___}]]

Out[5]= 630

I must be making some mistake because my counts don't seem to match yours. If you can track down one or more of the
permutations that are incorrectly being counted in this code then I will find a way to correct the code and automate your count.
POSTED BY: Bill Simpson
Mike Ingraffia
Mike Ingraffia
Posted 11 years ago
I am sorry for leaving out some important information.
For example of what I am trying to do on a smaller scale using permutations of length n=4 they are:
(1234)(1243)(1324)(1342)(1423)(1432)(2134)(2143)(2314)(2341)(2413)(2431)(3124)(3142)(3214)(3241)(3412)(3421)(4123)(4132)(4213)(4231)(4312)(4321).
There are 24.
Now lets say I want all the permutations that avoid the pattern (123). The new list I would want that avoid that pattern (123) are: (1432)(3241)(4213)(2431)(4132)(4231)(3214)(2413)(2143)(3421)(3142)(3412)(4312)(4321). There are 14 of them that do not have that "increasing 123 pattern".

And that is what I would like to obtain, but extending it for a permutation of length 5 avoiding the 3 patterns above.
And When we extend it to patterns of length 6,7, and 8 I would want the avoid the same 3 patterns (1234), (1342), (1324).

The reason I want those distinct 3 patterns is they are the equivalence classes for the rest of the patterns. The actual data I need to obtain is: For permutations of length 5, there are 103 that avoid the patterns (1234), (1342), and (1324). But when we get to length 6 there are 513 that avoid the patterns (1234), and (1324), but 512 that avoid the pattern (1342). And length 7 there are 2740 that avoid the pattern (1342), 2761 that avoid the pattern (1234), and 2762 that avoid the pattern (1324).

So I know that some patterns are easier to avoid then others, I just need to prove that just because they are length 4 does not imply that each pattern is equally easy to avoid.

Hopefully this clears some information up
POSTED BY: Mike Ingraffia
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract