1

2

3

- https://en.wikipedia.org/wiki/Permutation_pattern
- https://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes
- https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/permutation.html
- https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/permutation.html#sage.combinat.permutation.Permutation.avoids
- https://www.mathsisfun.com/definitions/permutation.html
- https://stevelosh.com/blog/2015/12/permutation-patterns/
- https://www.geeksforgeeks.org/program-nth-catalan-number/
- https://www.geeksforgeeks.org/sort-stack-using-temporary-stack/?ref=rp

4

5

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$

6

In [43]:

perms = Permutations(4) print(perms)

7

Standard permutations of 4

In [42]:

for p in perms: print(p)

8

[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.$

9

In [7]:

print(P.cardinality()) print(factorial(4))

10

24
24

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})!}$

11

In [1]:

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

12

[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]

In [2]:

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

13

6

14

A permutation pattern is a sub permutation of a seperate pattern. Pattern permutations are based on two main concepts: containment and avoidance

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)$.

15

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

16

In [9]:

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

17

True

In [6]:

Permutation([1,4,3,2]).pattern_positions([1,2])

18

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

Notice that there is more than one subsequence $x$ that contains $y$ as a pattern

19

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.

20

In [16]:

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

21

True

This will give us an error because no pattern exists

22

In [15]:

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

23

```
---------------------------------------------------------------------------
```

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

Find a permutation that contains the pattern $(231)$. Answer below

24

In [ ]:

25

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

26

In [ ]:

27

28

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

29

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.

30

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.

31

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.

32

Lets show this on sage

33

In [7]:

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

34

False

In [8]:

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

35

True

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.$

36

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$

37

a.) Find the nth catalan number

38

In [ ]:

def catalan(n):

39

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

40

In [ ]:

41

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

42

In [ ]:

43

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.$

44

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$

45

a.) Find the nth catalan number

46

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

47

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

48

In [39]:

for i in range(5): print(catalan(i))

49

1
1
2
5
14

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

50

In [47]:

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

51

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

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

52

In [ ]:

a.) create the stack sort algorithm

53

In [ ]:

from collections import deque

54

In [ ]:

def sort(n): stack = deque()

55

In [ ]:

56

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

57

In [ ]:

58

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

59

a.) create the stack sort algorithm

60

In [49]:

from collections import deque

61

In [50]:

def sort(n): #start with an empty stack 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

62

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

63

In [32]:

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

64

deque([1, 2, 3])

In [25]:

print(sort(perm) == perm.sort())

65

False