Math 157: Intro to Mathematical Software
UC San Diego, Winter 2020
Permutation Patterns
By Hanad Ahmed
Quick Permutation Review:
What is a Permutation?
A permutation is a mathematical technique that determines the number of possible arrangements in a set when the order of the arrangements matters.
Permutations are used in so many things such as:
Gambling
Cryptography
Architecture
etc
A permutation of length is a reordering of the list . We will usually write a permutation as
Permutations give the number of ways to arrange n numbers and are counted by the factorial
Permutations:
To find number of ways to choose r slots out of n total items.
Permutation Patterns: (Its about to get real!)
What is Permutation Pattern?
A permutation pattern is a sub permutation of a seperate pattern. Pattern permutations are based on two main concepts: containment and avoidance
Pattern Containment:
If π and σ are two permutations, then π is said to CONTAIN σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ. Permutation Patterns focus on the relationship of two permutations rather than the actual numbers of the two.
For example:
let and . Notice contains a pattern in because as we can see the order of is ascending on the first two digits of the permutation and the same is for . So we can choose any subsequence in such as and it contains the permutation .
Permutation Patterns can be tricky to notice. Lets use sage to help.
Notice that there is more than one subsequence that contains as a pattern
Pattern Avoidance
Pattern avoidance is the angalous of pattern containment. If a permutation π does not contain a pattern σ, then π is said to avoid σ.
For example:
The permutation π = (4321) avoids the permutation σ = (12) because π has no ascending subsequence.
This will give us an error because no pattern exists
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-15-62217f902c2a> in <module>
----> 1 Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).pattern_postions([Integer(1),Integer(2)])
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4703)()
491 AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'
492 """
--> 493 return self.getattr_from_category(name)
494
495 cdef getattr_from_category(self, name):
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/structure/element.pyx in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4815)()
504 else:
505 cls = P._abstract_element_class
--> 506 return getattr_from_other_class(self, cls, name)
507
508 def __dir__(self):
/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/cpython/getattr.pyx in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2553)()
365 dummy_error_message.cls = type(self)
366 dummy_error_message.name = name
--> 367 raise AttributeError(dummy_error_message)
368 cdef PyObject* attr = instance_getattr(cls, name)
369 if attr is NULL:
AttributeError: 'StandardPermutations_all_with_category.element_class' object has no attribute 'pattern_postions'
Take two minutes and try to answer these questions
***** Participation Check ***************************
Find a permutation that contains the pattern . Answer below
Does the permutation contains or avoid the permutation (2,1)? If contains. how many patterns? Answer below
*********************************************************
Stack sortability of permutations:
A stack is one of the most important data structures in computer science. The order of the stack is similar to a stack of dishes, where the last thing put in is the first thing taken out.
The algorithm to sort a stack is:
Initialize an empty stack
For each input value x:
While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output
Push x onto the stack
While the stack is nonempty, pop it to the output
Stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. This is significant because stack storing doesnt depend on the value the input but the relative order to other inputs. This is where permutation patterns come in play. The algorithm to correctly sort a stack is the permutation that avoids the permutation 231.
Computer scientist Donald Knuth concluded that if the algorithm fails to sort an input using (231), then that input cannot be sorted with a single stack.
For example:
Input permutation (123) into the sorting algorithm. all three numbers are pushed into the stack, then popped in the order (321).
But if you try to input the permutation (231) into the algorithm it fails. The algorithm first pushes 2, and pops it when it sees the larger input value 3, causing 2 to be output before 1 rather than after it.
Lets show this on sage
Exercise 1: Catalan Numbers
Catalan number is a sequence of numbers that commonly occurs in enumeration/counting problems.
The ''n''th Catalan number is given directly in terms of binomial coefficients by
Cn is the number of permutations of {1, ..., n} that avoid the permutation pattern 123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence.
Similar to fibonacci sequence. The Catalan numbers satisfy the recurrence relations:
a.) Find the nth catalan number
b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers
c.) What are the valid permutations for catalan(3)?
Exercise 1: Catalan Numbers (SOLUTION)
Catalan number is a sequence of numbers that commonly occurs in enumeration/counting problems.
The ''n''th Catalan number is given directly in terms of binomial coefficients by
Cn is the number of permutations of {1, ..., n} that avoid the permutation pattern 123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence.
Similar to fibonicii sequence. The Catalan numbers satisfy the recurrence relations:
a.) Find the nth catalan number
b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers
c.) What are the valid permutations for catalan(3)?
Exercise 2: Stack Sortability
Being able to sort a stack of inputs is important in computer science. Lets implement the algorithm to allow us to sort a stack using the algorithm.
def(sort):
Initialize an empty stack
For each input value x:
While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output
Push x onto the stack
While the stack is nonempty, pop it to the output
b.) Find a valid permutation to sort using permutation patterns
Exercise 2: Stack Sortability (SOLUTION)
Being able to sort a stack of inputs is important in computer science. Lets implement the algorithm to allow us to sort a stack using the algorithm.
def(sort):
Initialize an empty stack
For each input value x:
While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output
Push x onto the stack
While the stack is nonempty, pop it to the output
a.) create the stack sort algorithm
b.) Find a valid permutation to sort using permutation patterns