Advanced Topics in Discrete Mathematics: RR, CA, and Graph Analysis

This document presents comprehensive solutions to a discrete mathematics assignment. The assignment encompasses various topics including recurrence relations (finding a recurrence relation for climbing stairs, solving it, and calculating the number of ways for 50 stairs), analysis of the tent map (finding fixed points, plotting derivatives, and identifying stability), and cellular automata (determining rule numbers, performing iterations, and exploring specific rules like B25/S4 and Game of Life). Furthermore, it delves into combinatorics using the inclusion-exclusion method to calculate coprime integers and graph theory, including girth analysis, planar graphs, and chromatic numbers. The assignment also covers equivalence relations, generating functions, and counting problems related to passwords, bagles, and digit sequences. Finally, the assignment explores odd graphs, proper colorings, Hasse diagrams, and spanning trees, providing a broad overview of discrete mathematics concepts and their applications.

Recurrence, Relations (RR) and Cellular Automata
(CA)
1. Find a RR for the number of ways to climb n stairs if the allowed steps are 1 or 2 staircases.
What are the initial conditions for this RR? Solve the problem. In how many ways can one
climb 50 stairs?
2. Find the fix points for the tent map. Then g(x) = aMin(x, 1-x), 0 ≤ x ≤ 1, 0 ≤ a ≤ 2. Plot the
location of the right fix point as function of a and the derivative there. When is this fix point
stable? Can you find a 2-cycle in the tent map?
3. Consider the following 1D CA: A cell is black in next generation if and only if either of it
neighbours, but not both, was black on the step before. What is the rule number? Do 5
iterations using one black cell as seed.
4. Consider the rule B25/S4. B denotes birth and S survival. Game of Life is B3/S23. What is the
rule number for B25/S4? Do 3 iterations for the first one. Note that we have up-down
symmetry. It is called a replicator. Do one iteration for the second one. It is called a photon.
5. Use the inclusion-exclusion (IE) method to calculate the number of integers between 1 and
60 that are coprime with 60. The primes 2, 3 and 5 are the prime factors in 60 since 60 = 22 ·
3 · 5. The integers, i, that are coprime with 60 are not divisible with 2, 3 and 5 so GCD(i, 60) =
1 for them. GCD stands for greatest common divisor. You can count them directly but here
you have to use the IE-method.
6. The girth of a graph G is the number of edges of the shortest cycle it is possible to find in G
and it is denoted g (G). Let, from now on, the graphs G have e = v + 1 For such graphs with v
≥ 4 it is possible to show that
The floor function [x] gives the largest integer ≤ x.
a) Explain why in this type of graphs there must be at least two cycles. Draw a case where the cycles
are edge disjoint for v = 7 and e = 8.
b) If the two cycles are edge disjoint what is the maximum girth in a graph with e = v+ 1?
c) Draw a graph with maximal girth for v = 7 and e = 8

7. What is the maximal number of edges in a planar graph when the regions have degree 3 or
more? Use for example 2e = Σdeg(Ri) and Euler’s formula.
b) Let G be a graph with 11 vertices and let G¯ be its complement graph. G¯ has the same 11
vertices but the edges from K11 that are not edges in G. Use the result in (a) above to show
that not both G and G¯ can be planar.
8. Consider passwords with three symbols. Allowed symbols are the 26 letters in the English
alphabet and the ten digits 0 to 9. We put the following restrictions on the passwords:
i) There must be both letters and digits.
ii) There must be both upper- and lower-case letters.
So K8k and 4zL are examples of allowed passwords. How many such passwords can be
constructed?
9. Let X = {1, 2, 3, 4} and A = X × X. Define a relation R on A by (a, b)R(c, d) if and only if ab = cd.
This relation, R, is an equivalence relation. Determine the equivalence classes.
10. You have to buy 27 bagels. They are of four types: plain, onion, tomato and blueberry. The
restrictions are: At least three of each sort. Not more than five with onions. In how many
ways can you do this?
(a) Solve the problem with inclusion-exclusion method.
(b) Give the generating function for the problem.
11. Consider all the 4-digit numbers from 1000 to 9999.
(a) How many of them have a strictly increasing or decreasing sequence? Two examples are
3589 (strictly increasing) and 9760 (strictly decreasing). Strictly increasing means next digit
to the right is greater than the previous one. Strictly decreasing means next digit to the right
is smaller than the previous one.
(b) How many of them have an increasing or decreasing sequence? Two examples are 3556
(increasing) and 6661 (decreasing). Increasing means next digit to the right is ≥ the previous
one. Decreasing means next digit to the right is ≤ the previous one.
12. The odd graph Ok, k is an integer ≥ 2, is defined in the following way:
The vertices represent the subsets with k − 1 elements that can be obtained from a set with
2k −1 elements. Two vertices are joined with an edge if and only if the corresponding
subsets are disjoint. O2 is a triangle so it is isomorphic to C3.
(a) Draw O3

(b) Show that Ok is k-regular for all k ≥ 2, that is, show that all vertices in Ok has degree k.
13. The complete bipartite graph K2,4 is shown below.
How many proper colorings of K2,4 are possible if 4 colors are available? Hint: Here you can use the
sum rule. Sum over 2 colors and 1 color on the upper two vertices.
14. A Hasse diagram is shown below. Unfortunately the labels at the vertices are missing. Give
suggestions of what they can be. The relation R is the divides relation on a subset, S, of the
set of positive integers. That is, aRb if and only if a|b, where a ∈ S and b ∈ S.
Define the relation R on the set A of all bit strings of length five such that sRt, for s, t ∈ A, if and only
if s and t contain the same number of 1s. Give the equivalence class [10100].
15. Consider the following graph, G.
(a) Determine the chromatic number χ(G).
(b) Find an Euler circuit and a Hamilton cycle in G if they exist
16. Define the relation R on the integer points in the plane, Z × Z, in the following way:

(x1, y1)R(x2, y2) ⇔ y1 −x1 = y2 −x2. This is an equivalence relation. Illustrate in a figure two
equivalence classes and give three elements in each of them
17. Five different balls, numbered 1 to 5, shall be placed in three containers labeled a, b and c. In
how many ways can this be done if no container is allowed to be empty? So we are asking
for the number of onto functions from a set with five elements to a set with three elements.
Use for example the inclusion-exclusion method.
18. Consider the following statement about simple connected graphs G:
True or false? Motivate your answer. χ(G) is the chromatic number for G
19. An interesting type of graphs is the fullerene graphs. They are planar and every vertex has
degree 3. The regions are pentagons and hexagons. With pentagons and hexagons we mean
C5 and C6 cycles, respectively.
(a) If a fullerene, G, has 60 vertices, how many edges and regions are there in G? How many of the
regions are pentagons and how many are hexagons?
(b) Let p denote the number of pentagons and h the number of hexagons. Which values of p and h
are possible in a fullerene graph?
(c) Draw the fullerene graph with 24 vertices. The drawing must be done without edge crossings
since the graph is planar.
20. A spanning tree T to a connected graph G is a subgraph of G which is a tree and contains all
the vertices of G. Let, from now on, G = K3,3 see figure below.
a) Draw three non-isomorphic spanning trees in K3,3
b) Let us now also include isomorphic trees. How many spanning trees are there then in total in K3,3?