IT221 Discrete Math

Unit 5: Counting, Combinations and Permutations

RBatzinger

2025-10-21

Final Topics

1: Automata
2: Sequences
3: Counting Combinations and Permutations
4: Graphs and Trees
5: Regular Expressions and State Machines

1: Automata

Starting image

Automata Outline

  +         +
 +#+  -->  + +
  +         +

 +++       +++
 +#+  -->  + +
 +++       +++

Outline version

 5 dot pattern                                    9-dot pattern

Conway’s Game of Life ( Cellular Automata)

Each cell with one or no neighbors dies, as if by solitude.
```
 ++            ++
#     -->     .
```
Each cell with four or more neighbors dies, as if by overpopulation.
```
++         ++
#+    -->  .+
 +         ++ 
```
Each cell with two or three neighbors survives.
```
 +          +
#+    -->  #+ 
```
For a space that is empty or unpopulated: Each cell with three neighbors becomes populated.
```
 +           +
 +    -->   #+
 +           +
```

https://playgameoflife.com

2: Sequences

Arithmetic

\[a_n = a_{n-1} + d\]

\[a_n = a_1 + d(n-1)\]

\[\small s_n = \sum \left(a_1 + a_1 + \cdots + a_n\right)= \frac{n (a_1 + a_n)}{2}\]

Geometric

\[x_n = a(r^{n-1})= r x_{n-1}\]

Sum of units $x_1 \cdots x_n$

\[s_n = \sum \left(x_1 + x_2+ \cdots x_n\right)= \frac{a(1-r^n) }{(1-r)}\]

Sum of units $x_1 x_r< 1 $

\[s_n = \sum \left(x_1 + x_2+ \cdots + x_n\right)= \frac{a}{(1-r)}\]

Note: $r \ne 1$ and $r \gt 1$ will never converge.

Polynomial of power $n$

General Polynomial

\[x = a_0 + a_1 x+ a_2 x^2+ ... + a_{n}x^n\]

Let’s use a random polynomial to general

\[y=2x^3-4x\] * Calculate the first 7 entries of the sequence.

-2  8  42  112  230  408  658

Calculate derivative differentials to determine power of the polynomial

 x   y    Diff  Diff2 Diff3
 1   -2   
      >  10 
 2    8        >  24
      >  34           > 12
 3   42        >  36
      >  70           > 12
 4  112        >  48
      >  118          > 12
 5  230        >  60
      >  178          > 12
 6  408        >  72
      >  250
 7  658

Set up to determine the coefficients

\[\eqalign{ x:& &ax^3 + bx^2 + cx + d &=& y\\ 1:& &a + b + c + d &=& -2\\ 2:& & 8a + 4b + 2c +d &=&8\\ 3:& & 27a + 9b + 3c + d&=&42\\ 4:& & 64a + 16b + 4c + d&=&112\\ }\]

Convert to a solution matrix

\[\left[\matrix{1&1&1&1&|& -2\\ 8 & 4 & 2 & 1 &|&8\\ 27 & 9 & 3& 1&|&42\\ 64 & 16 & 4 & 1&|&112\\ }\right]\]

Use Gaussian elimination to reduce the lower echelon

\[\left[\matrix{1&1&1&1&|& -2\\ 0 & 1 & \frac{3}{2} & \frac{7}{4}&|&-6\\ 0 & 0 & 1& \frac{11}{6}&|&-4\\ 0 & 0 & 0 & 1&|&0\\ }\right]\]

Use back substitution to solve the unknowns

\[\left[\matrix{1&0&0&0&|& 2\\ 0 & 1 & 0 & 0&|&0\\ 0 & 0 & 1& 0&|&-4\\ 0 & 0 & 0 & 1&|&0\\ }\right]\]

Convert to the polynomial

\[y=2x^3-4x\]

Use Integration to determine the sum

\[\int_1^7 2x^3 - 4x dx= 1102\]

Confirmation by Trapezoida Rule

3: Counting Combinations and Permutations

Permutations

an arrangement of objects in a specific order.
Order matters: each permutation represents a different permutation.
Permutations of $n$ Objects Taken $n$ at a Time

\[P(n,n) = n!\]

Permutations of $n$ Objects Taken $k$ at a Time

\[P(n,k)= \frac{n!}{(n-k)!}\]

Permutations with Repetition (Non-Distinct Objects)

The number of ways to arrange $n$ objects where there are $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, and so on.

\[\frac{n!}{n_1! n_2! \dots n_r!}\]

Combinations (Order Doesn’t Matter)

A combination is a selection of objects where the order of selection is irrelevant.

Example: Choosing runs like ${1, 2, 3}$, ${2,1,3}$ and ${3,1,2}$ out of a set of 100 numbers

Combinations of $n$ Objects taken $k$ at a Time

\[C(n, k) = \binom{n}{k} = \frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!}\]

Permutations vs Combinations

\[\small\matrix{ Feature & Permutations & Combinations\\ \hline \hbox{Order}&\hbox{Matters (Arrangement)}&\hbox{Doesn't Matter (Selection)}\\ \hbox{Question}&\hbox{How many arrangements?}&\hbox{How many groups/subsets?}\\ \hbox{Formula} & P(n, k) = \frac{n!}{(n-k)!} & C(n, k) = \frac{n!}{k!(n-k)!}\\ \hbox{Result}&\hbox{Generally larger number}&\hbox{Generally smaller number}\\ \hbox{Mnemonic}&\hbox{Position (or Placement)}&\hbox{Committee (or Choose)}\\ }\]

Bars and Stars:

Distribution of $n$ items among $k$ bins

We need n stars (the objects)
We need k-1 bars (to create k bins)
Total positions: n + k - 1
The number of ways =

\[\binom{n+k-1}{k-1} = \binom{n+k-1}{n}\]

Example: 3 cookies distribute among 2 children
```
 ***|
 **|*
 *|**
 |***
```

\[\binom{3+2-1}{2-1}= \binom{4}{1}= \frac{4!}{3!1!}=4\]

4: Graphs

Structures

linked nodes: A list of neighbors

  a = Node.new(0)
  b = Node.new(72)
  c = Node.new(144)
  d = Node.new(216)
  e = Node.new(288)
  f = Node.new(nil)

  a.neighbors([b,c,d,e,f])
  b.neighbors([a,c,d,e])
  c.neighbors([a,b,d,e])
  d.neighbors([a,b,c,e])
  e.neighbors([a,b,c,d])
  f.neighbors([a])

Connectivity Matrix:

a matrix to map connections to the next

\[\matrix{&\tiny a &\tiny b&\tiny c &\tiny d&\tiny e &\tiny f\\ \tiny a &0&1&1&1&1&1\\ \tiny b &1&0&1&1&1&0\\ \tiny c &1&1&0&1&1&0\\ \tiny d &1&1&1&0&1&0\\ \tiny e &1&1&1&1&0&0\\ \tiny f &1&0&0&0&0&0\\ }\] ## Unweighted Undirected Graph

Weighted Undirected Graph

Directed Graph

Weighted Directed Graph

5: Nodes and links

Node

A container object that includes
Data structure can be either
- scalar value:
- attributes of a record
- links to data container
Dynamic links to other nodes
- Forward links (going deeper into the structure)
- Back links (backing out of a structure)

Ruby code

class Node
   attr_accessors :value, :leftnode; :rightnode

   def initialize(value,left,right)
      @value = value
      @leftnode = left
      @rightnode = right
   end
   
   def to_s
      @value.to_s
   end
end

6: Trees

7: Regular Expressions and State Machines