Compute Environment: Ubuntu 20.04 (Default)

## Permutation Patterns

### 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 $n$ is a reordering of the list $[1,2,\dots,n]$. We will usually write a permutation as $\pi = \pi_1\pi_2\dots\pi_n$

In [43]:
perms = Permutations(4)
print(perms)

Standard permutations of 4
In [42]:
for p in perms:
print(p)

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Permutations give the number of ways to arrange n numbers and are counted by the factorial $n! = n\cdot(n-1)\dots 3\cdot 2\cdot 1.$

In [7]:
print(P.cardinality())
print(factorial(4))

24 24

#### Permutations:

To find number of ways to choose r slots out of n total items.
$\operatorname{number-of-permutations}(\mathit{items}, \mathit{slots}) = \frac {\mathit{items}!} {(\mathit{items} - \mathit{slots})!}$

In [1]:
Arrangements( ["c","a","t"], 2 ).list()

[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
In [2]:
Arrangements(["c","a","t"],2).cardinality()

6

## 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 $x = (1432)$ and $y =(12)$. Notice $x$ contains a pattern in $y$ because as we can see the order of $x$ is ascending on the first two digits of the permutation and the same is for $y$. So we can choose any subsequence in $x$ such as $(14)$ and it contains the permutation $(12)$.

Permutation Patterns can be tricky to notice. Lets use sage to help.

In [9]:
 Permutation([1,4,3,2]).has_pattern([1,2])

True
In [6]:
Permutation([1,4,3,2]).pattern_positions([1,2])

[[0, 1], [0, 2], [0, 3]]

Notice that there is more than one subsequence $x$ that contains $y$ 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.

In [16]:
 Permutation([4,3,2,1]).avoids([1,2])

True

This will give us an error because no pattern exists

In [15]:
 Permutation([4,3,2,1]).pattern_postions([1,2])

--------------------------------------------------------------------------- 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 $(231)$. Answer below

In [ ]:



Does the permutation $(4, 2, 3, 1)$ contains or avoid the permutation (2,1)? If contains. how many patterns? Answer below

In [ ]:



## 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

In [7]:
Permutation([1, 3, 4, 2]).avoids([2,3,1])

False
In [8]:
Permutation([4, 3, 2, 1]).avoids([2,3,1])

True

## 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 $C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0.$

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: $C_0 = 1 \; \; and \; \; C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$

a.) Find the nth catalan number

In [ ]:
def catalan(n):



b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers

In [ ]:



c.) What are the valid permutations for catalan(3)?

In [ ]:



## 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 $C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0.$

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: $C_0 = 1 \; \; and \; \; C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$

a.) Find the nth catalan number

In [38]:
def catalan(n):

# Base Case
if ((n == 0) or  (n == 1))
:
return 1

#recursion
catNumber = 0
for i in range(n):
catNumber += catalan(i) * catalan(n-i-1)

return catNumber


b.) Print the first 5 catalan numbers. look up the catalan numbers to check answers

In [39]:
for i in range(5):
print(catalan(i))

1 1 2 5 14

c.) What are the valid permutations for catalan(3)?

In [47]:

perms = Permutations(3)

for i in perms:
if(Permutation(i).avoids([1,2,3])):
print(i)


[1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

## 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
In [ ]:
a.) create the stack sort algorithm

In [ ]:
from collections import deque

In [ ]:
def sort(n):
stack = deque()


In [ ]:



b.) Find a valid permutation to sort using permutation patterns

In [ ]:



## 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

In [49]:
from collections import deque

In [50]:
def sort(n):
stack = deque()

#while the n is not empty
while(len(n) != 0):

#get the last element in n and remove it
last = n[-1]
n.pop()

#while our stack is not empty and the last element in our stack is greater than last element in n
while((len(stack) != 0) and (stack[-1] > last)):

#add our last element into n and pop the element
n.append(stack[-1])
stack.pop()
#add the last element of n to our stack
stack.append(last)

#when we go through all of n return our stack
return stack



b.) Find a valid permutation to sort using permutation patterns

In [32]:
perm = [2, 1, 3]

Permutation(perm).avoids([2,3,1])

print(sort(perm))

deque([1, 2, 3])
In [25]:
print(sort(perm) == perm.sort())

False