BSc CSIT (TU) Science Discrete Structure (BSc CSIT, CSC160) Question Paper 2081 Nepal

Lattice

A lattice is a partially ordered set (poset) $(L, \preceq)$ in which every pair of elements $a, b$ has both a least upper bound (LUB / join, $a \vee b$) and a greatest lower bound (GLB / meet, $a \wedge b$).

Partially Ordered Set (Poset)

A relation $R$ on a set $S$ is a partial order if it is:

1. Reflexive — $a \preceq a$ for all $a \in S$.
2. Antisymmetric — if $a \preceq b$ and $b \preceq a$, then $a = b$.
3. Transitive — if $a \preceq b$ and $b \preceq c$, then $a \preceq c$.

The pair $(S, \preceq)$ is called a poset. The divisibility relation $a \mid b$ ("$a$ divides $b$") on positive integers is a partial order.

Hasse Diagram for Divisibility on {1, 2, 3, 6, 12, 24, 36}

Under the relation $a \mid b$, the covering (immediate-successor) relations are:

• $1 \to 2$, $1 \to 3$
• $2 \to 6$, $3 \to 6$
• $6 \to 12$
• $12 \to 24$, $12 \to 36$

Hasse diagram (drawn upward, omitting reflexive loops and transitive edges):

        24        36
          \      /
           \    /
            12
             |
             6
            / \
           2   3
            \ /
             1

Reading bottom to top: $1$ is at the bottom; $2$ and $3$ sit above it; both join into $6$; then $12$; and $12$ branches up to the two incomparable top elements $24$ and $36$.

Special Elements

• Minimal: $1$
• Maximal: $24, 36$
• Least: $1$
• Greatest: none (since $24 \nmid 36$ and $36 \nmid 24$).

Note: this poset is not a lattice, because $24$ and $36$ have no LUB within the set (their join $\text{lcm}(24,36)=72$ is absent).

Generating Function

The (ordinary) generating function of a sequence $a_0, a_1, a_2, \dots$ is the formal power series

$$G(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \cdots$$

It encodes the entire sequence as the coefficients of a single function, turning recurrence relations into algebraic equations that can be solved and then expanded back into a closed form for $a_n$.

Solving $a_n = 3a_{n-1} + 2$, $a_0 = 1$

Step 1 — Set up the generating function. Let $G(x)=\sum_{n\ge 0} a_n x^n$.

The recurrence holds for $n \ge 1$. Multiply both sides by $x^n$ and sum:

$$\sum_{n\ge 1} a_n x^n = 3\sum_{n\ge 1} a_{n-1} x^n + 2\sum_{n\ge 1} x^n$$

Step 2 — Express each sum via $G(x)$.

• $\sum_{n\ge 1} a_n x^n = G(x) - a_0 = G(x) - 1$.
• $\sum_{n\ge 1} a_{n-1} x^n = x\sum_{n\ge 1} a_{n-1}x^{n-1} = x\,G(x)$.
• $\sum_{n\ge 1} x^n = \dfrac{x}{1-x}$.

So:

$$G(x) - 1 = 3x\,G(x) + \frac{2x}{1-x}$$

Step 3 — Solve for $G(x)$.

$$G(x)(1 - 3x) = 1 + \frac{2x}{1-x} = \frac{(1-x) + 2x}{1-x} = \frac{1+x}{1-x}$$ $$G(x) = \frac{1+x}{(1-x)(1-3x)}$$

Step 4 — Partial fractions. Write

$$\frac{1+x}{(1-x)(1-3x)} = \frac{A}{1-x} + \frac{B}{1-3x}$$

Then $1 + x = A(1-3x) + B(1-x)$.

• Set $x = 1$: $\;2 = A(1-3) = -2A \Rightarrow A = -1$.
• Set $x = \tfrac{1}{3}$: $\;\tfrac{4}{3} = B(1 - \tfrac{1}{3}) = \tfrac{2}{3}B \Rightarrow B = 2$.

Thus

$$G(x) = \frac{-1}{1-x} + \frac{2}{1-3x}$$

Step 5 — Read off the coefficients. Using $\dfrac{1}{1-rx} = \sum_{n\ge 0} r^n x^n$:

$$a_n = -1\cdot(1)^n + 2\cdot(3)^n = 2\cdot 3^n - 1$$

Final answer:

$$\boxed{a_n = 2\cdot 3^n - 1}$$

Check: $a_0 = 2-1 = 1$ ✓, $a_1 = 6-1 = 5 = 3(1)+2$ ✓, $a_2 = 18-1 = 17 = 3(5)+2$ ✓.

Euler and Hamiltonian Paths and Circuits

Euler Path and Euler Circuit

• An Euler path is a path that traverses every edge of the graph exactly once (vertices may repeat).
• An Euler circuit is an Euler path that starts and ends at the same vertex, i.e. a closed Euler path.

Example. In the graph with vertices $\{A,B,C,D\}$ and edges $AB, BC, CD, DA, AC$:

• $D{-}A{-}B{-}C{-}A{-}C$? — instead, $A{-}B{-}C{-}D{-}A{-}C$ is an Euler path (uses each of the 5 edges once) but not a circuit, because it starts at $A$ and ends at $C$. (Here $A$ and $C$ have odd degree.)

Hamiltonian Path and Hamiltonian Circuit

• A Hamiltonian path visits every vertex exactly once (edges may be skipped).
• A Hamiltonian circuit (cycle) is a Hamiltonian path that returns to the starting vertex, visiting every vertex exactly once and closing the loop.

Example. In the cycle graph $C_4$ with vertices $A,B,C,D$ and edges $AB, BC, CD, DA$, the sequence $A{-}B{-}C{-}D{-}A$ is a Hamiltonian circuit (every vertex once, returns to $A$).

Key Difference

Necessary and Sufficient Conditions for an Euler Circuit

Theorem (Euler). A connected graph $G$ has an Euler circuit if and only if every vertex has even degree.

Related condition for an Euler path (open): a connected graph has an Euler path that is not a circuit if and only if it has exactly two vertices of odd degree (the path begins at one and ends at the other).

Reasoning: each time the trail enters a vertex it must also leave it, pairing up edges at that vertex; for a closed circuit this forces every degree to be even.

Both are indirect proof techniques for an implication $p \Rightarrow q$, but they differ in what is assumed and contradicted.

Proof by contraposition uses the tautology $(p \Rightarrow q) \equiv (\lnot q \Rightarrow \lnot p)$ and works only for implications.

Proof by contradiction is more general: it assumes the statement is false and shows this leads to a logical impossibility. (Example: $\sqrt{2}$ is irrational is proved by contradiction.)

In short: contraposition flips and negates an implication; contradiction assumes the whole claim is false and derives an inconsistency.

Identity Function

The identity function on a set $A$ is the function $I_A : A \to A$ defined by

$$I_A(x) = x \quad \text{for all } x \in A.$$

It maps every element to itself. It is always a bijection, and for any function $f:A\to B$, $f \circ I_A = f$ and $I_B \circ f = f$.

Inverse Function

Let $f : A \to B$ be a bijective (one-to-one and onto) function. Its inverse function $f^{-1} : B \to A$ is defined by

$$f^{-1}(y) = x \iff f(x) = y.$$

The inverse satisfies

$$f^{-1} \circ f = I_A \quad\text{and}\quad f \circ f^{-1} = I_B.$$

Existence condition: $f^{-1}$ exists only if $f$ is a bijection.

Example. If $f:\mathbb{R}\to\mathbb{R}$, $f(x) = 2x + 3$, then $f^{-1}(y) = \dfrac{y-3}{2}$.

Symmetric Difference

The symmetric difference of two sets $A$ and $B$, written $A \triangle B$ (or $A \oplus B$), is the set of elements that belong to exactly one of $A$ or $B$ — that is, in either set but not in both:

$$A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B).$$

It is commutative and associative, and corresponds to the logical XOR of membership.

Example

Let $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$.

• $A \setminus B = \{1, 2\}$
• $B \setminus A = \{5, 6\}$

$$A \triangle B = \{1, 2\} \cup \{5, 6\} = \{1, 2, 5, 6\}.$$

The common elements $3$ and $4$ are excluded.

Poset (Partially Ordered Set)

A poset is a set $S$ together with a relation $\preceq$ that is reflexive, antisymmetric, and transitive:

1. $a \preceq a$ (reflexive),
2. $a \preceq b \wedge b \preceq a \Rightarrow a = b$ (antisymmetric),
3. $a \preceq b \wedge b \preceq c \Rightarrow a \preceq c$ (transitive).

It is denoted $(S, \preceq)$. "Partial" means some pairs may be incomparable. Example: $(\mathcal{P}(S), \subseteq)$ and the divisibility relation $(\mathbb{Z}^+, \mid)$.

Hasse Diagram

A Hasse diagram is a simplified graphical representation of a finite poset that shows only the essential covering relations. It is drawn using these conventions:

• Each element is a vertex.
• If $a \prec b$ and there is no $c$ with $a \prec c \prec b$ (i.e. $b$ covers $a$), draw an edge with $b$ placed above $a$.
• Reflexive loops (each $a \preceq a$) are omitted.
• Transitive edges that can be inferred are omitted.
• Direction is implied by vertical position (upward = greater), so arrowheads are not needed.

Example. For $\{1,2,4\}$ under divisibility: $1$ at bottom, edge to $2$, edge up to $4$ (a vertical chain).

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It is a greedy algorithm that grows a set of vertices whose final shortest distance from the source is known.

Steps

Dijkstra(G, w, source):
  1. For every vertex v: dist[v] = ∞, prev[v] = NIL
  2. dist[source] = 0
  3. Let Q = set of all vertices (a min-priority queue keyed by dist)
  4. While Q is not empty:
       a. u = vertex in Q with the SMALLEST dist[u]   // greedy pick
       b. Remove u from Q (its distance is now final)
       c. For each neighbor v of u still in Q:
            if dist[u] + w(u, v) < dist[v]:
               dist[v] = dist[u] + w(u, v)   // relaxation
               prev[v] = u
  5. Return dist[], prev[]

Key points

• Greedy + relaxation: repeatedly select the unvisited vertex with the minimum tentative distance, then relax its outgoing edges.
• Requirement: edge weights must be non-negative.
• Complexity: $O(V^2)$ with an array, or $O((V+E)\log V)$ with a binary-heap priority queue.
• prev[] lets you reconstruct the actual shortest paths.

Rooted Tree

A rooted tree is a tree in which one vertex has been designated as the root, and every edge is implicitly directed away from the root. This gives a parent–child hierarchy: for any non-root vertex there is a unique path from the root to it, and the vertex just before it on that path is its parent.

Key terms:

• Root — the distinguished topmost vertex (no parent).
• Parent / child — adjacent vertices on a root-to-vertex path.
• Leaf — a vertex with no children.
• Internal vertex — a vertex with at least one child.

Height of a Tree

The level (depth) of a vertex is the length (number of edges) of the path from the root to that vertex; the root has level $0$.

The height of a rooted tree is the maximum level among all its vertices — equivalently, the length of the longest path from the root to a leaf.

Example. In a tree where the root has children at level 1 and grandchildren (leaves) at level 2, the height is $2$. A single-vertex tree has height $0$.

Cyclic Group

A group $(G, *)$ is called cyclic if there exists an element $g \in G$, called a generator, such that every element of $G$ can be written as a power (or integer multiple) of $g$:

$$G = \langle g \rangle = \{ g^n : n \in \mathbb{Z} \}.$$

(For additive notation, $G = \{ ng : n \in \mathbb{Z}\}$.) Every cyclic group is abelian (commutative).

Examples

1. Finite cyclic group $(\mathbb{Z}_4, +_4)$ — integers modulo $4$ under addition.

Taking $g = 1$:

$$1,\; 1+1=2,\; 1+1+1=3,\; 1+1+1+1 = 0.$$

So $\langle 1 \rangle = \{0,1,2,3\} = \mathbb{Z}_4$. Hence $\mathbb{Z}_4$ is cyclic with generator $1$ (also $3$).

2. Infinite cyclic group $(\mathbb{Z}, +)$ — the integers under addition are cyclic, generated by $1$ (every integer is a multiple of $1$).

Euclidean Algorithm for gcd(414, 662)

Repeatedly apply $\gcd(a,b) = \gcd(b, a \bmod b)$ until the remainder is $0$:

$$662 = 1 \cdot 414 + 248$$ $$414 = 1 \cdot 248 + 166$$ $$248 = 1 \cdot 166 + 82$$ $$166 = 2 \cdot 82 + 2$$ $$82 = 41 \cdot 2 + 0$$

The last non-zero remainder is $2$.

$$\boxed{\gcd(414, 662) = 2}$$

Check: $414 = 2 \cdot 207$ and $662 = 2 \cdot 331$; $207$ and $331$ share no common factor, confirming the gcd is $2$.

Coefficient of $x^5$ in $(1+x)^{10}$

By the Binomial Theorem,

$$(1+x)^{10} = \sum_{k=0}^{10} \binom{10}{k} x^k.$$

The coefficient of $x^5$ is therefore $\dbinom{10}{5}$:

$$\binom{10}{5} = \frac{10!}{5!\,5!} = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{30240}{120} = 252.$$

Final answer:

$$\boxed{\text{coefficient of } x^5 = \binom{10}{5} = 252}$$