Engineering Mathematics

Chapter 10
Discrete Mathematics and Combinatorial Methods

Bachelors Program in Electronics and Communication
Engineering Mathematics   •   Post Graduate

Discrete Mathematics and Combinatorial Methods

Introduction

Discrete mathematics studies mathematical structures that are finite, countable, or separated into distinct elements. Unlike continuous mathematics, which models variation through limits and derivatives, discrete mathematics addresses sets, logic, relations, graphs, trees, algorithms, integers, and finite probability spaces. These ideas are fundamental to electronics and communication engineering because digital systems operate on discrete symbols, binary states, finite-state machines, communication networks, coding schemes, and algorithmic procedures.

Combinatorics, the systematic study of counting and arrangements, provides methods for determining the number of possible configurations without listing every configuration. It supports channel coding, cryptography, scheduling, network design, reliability analysis, digital circuit testing, and computational complexity. At postgraduate level, the subject is not merely a collection of counting formulas: it is a framework for modelling engineering systems, proving correctness, evaluating alternatives, and understanding computational limitations.

Learning Objectives

After studying this chapter, a learner should be able to:

  1. distinguish discrete structures such as sets, relations, functions, graphs, trees, and Boolean systems;
  2. formulate engineering statements using propositions, predicates, quantifiers, and logical equivalence;
  3. apply permutations, combinations, inclusion–exclusion, recurrence relations, and generating functions;
  4. analyse graphs, trees, connectivity, paths, circuits, and network representations;
  5. use Boolean algebra and switching functions in digital-system reasoning;
  6. formulate and solve finite probabilistic and reliability problems;
  7. evaluate algorithmic efficiency and recognise the significance of computational complexity;
  8. apply discrete and combinatorial methods to communication and electronic engineering problems.

1. Sets, Relations, and Functions

1.1 Sets and operations

A set is a well-defined collection of distinct objects. If an object x belongs to set A, we write x ∈ A. The cardinality of a finite set A is denoted by |A|. The universal set is the domain under consideration, and the complement of A is Ac.

For sets A and B, the principal operations are:

A ∪ B = {x : x ∈ A or x ∈ B}
A ∩ B = {x : x ∈ A and x ∈ B}
A − B = {x : x ∈ A and x ∉ B}

The Cartesian product is

A × B = {(a,b) : a ∈ A, b ∈ B}

If both sets are finite, |A × B| = |A||B|. De Morgan’s laws are

(A ∪ B)c = Ac ∩ Bc, (A ∩ B)c = Ac ∪ Bc

These laws are especially useful when a digital-system requirement is expressed through permitted and forbidden states.

1.2 Relations

A binary relation R from A to B is a subset of A × B. A relation on A may be reflexive, symmetric, antisymmetric, or transitive. An equivalence relation is reflexive, symmetric, and transitive; it partitions a set into disjoint equivalence classes. Congruence modulo n, defined by a ≡ b (mod n) when n divides (a−b), is an important engineering example used in coding and cyclic structures.

A partial order is reflexive, antisymmetric, and transitive. A set equipped with a partial order is called a partially ordered set or poset. Dependency scheduling, refinement hierarchies, and design constraints can be modelled using posets.

1.3 Functions

A function f:A→B assigns exactly one element of codomain B to every element of domain A. It is injective if distinct inputs have distinct outputs, surjective if every codomain element is attained, and bijective if it is both. A bijection establishes equal cardinality between finite sets and is the theoretical basis of many counting arguments.

A function may also represent a signal transformation, encoder, address mapping, or state transition. In engineering, it is important to identify the domain, codomain, assumptions, and whether information is lost. An injective encoder preserves distinguishability; a non-injective mapping may merge states and create ambiguity.

2. Mathematical Logic and Proof

A proposition is a declarative statement that is either true or false, but not both. If p and q are propositions, the conjunction, disjunction, implication, and biconditional are respectively p ∧ q, p ∨ q, p → q, and p ↔ q.

The implication p → q is false only when p is true and q is false. Its contrapositive, ¬q → ¬p, is logically equivalent to it. The converse q → p is generally not equivalent to the original implication.

A proposition is a tautology if it is true for every valuation, a contradiction if it is always false, and contingent otherwise. Logical equivalence can be verified with truth tables or algebraic laws. In circuit design, a proposition corresponds to a switching function, while logical operators correspond to gates.

Quantifiers

The universal quantifier ∀ means “for every,” and the existential quantifier ∃ means “there exists.” Negation changes both the quantifier and the predicate:

¬(∀x P(x)) ≡ ∃x ¬P(x), ¬(∃x P(x)) ≡ ∀x ¬P(x)

The order of quantifiers matters. In general, ∀x∃y P(x,y) does not imply ∃y∀x P(x,y). This distinction is relevant to engineering specifications: “each transmitter has a suitable receiver” is not the same as “there is one receiver suitable for every transmitter.”

Proof methods

Direct proof assumes the hypotheses and derives the conclusion. Contraposition proves ¬q → ¬p instead of p → q. Contradiction assumes the negation of the desired statement and derives an impossibility. Mathematical induction proves a base case and then proves that validity at k implies validity at k+1. Strong induction permits dependence on all earlier cases. In engineering algorithms, induction is commonly used to establish loop invariants, recursive correctness, and properties of network structures.

3. Fundamental Counting Principles

The addition principle applies when alternatives are mutually exclusive. If one task can be completed in m ways and another mutually exclusive task in n ways, the total is m+n. The multiplication principle applies to sequential choices: if stages have n1,n2,…,nk possibilities, the total number is

n1 n2 ⋯ nk = ∏i=1k ni

These principles assume that the choices are correctly defined and that each complete outcome is counted once.

Permutations and combinations

The number of ordered arrangements of n distinct objects is

n! = n(n−1)(n−2)⋯1, 0! = 1

The number of ordered selections of r objects from n distinct objects is

P(n,r) = n!/(n−r)!, 0 ≤ r ≤ n

The number of unordered selections is

C(n,r) = n!/[r!(n−r)!], 0 ≤ r ≤ n

If repetitions are allowed in an ordered sequence of length r selected from n symbols, the number is nr. If r identical objects are distributed among n categories, the number of non-negative solutions to x1+⋯+xn=r is

C(n+r−1,r)

This stars-and-bars result assumes that objects of the same category are indistinguishable and that categories are distinguishable.

Binomial theorem

For a non-negative integer n,

(x+y)n = ∑r=0n C(n,r)xn−ryr

The coefficient C(n,r) counts the ways to select which r factors contribute y. The identity

∑r=0n C(n,r) = 2n

follows by setting x=y=1. It also counts the subsets of an n-element set.

Inclusion–exclusion

For two finite sets,

|A ∪ B| = |A| + |B| − |A ∩ B|

For three sets,

|A ∪ B ∪ C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|

The general principle alternates sums of intersections. It is useful when outcomes overlap, such as packets satisfying more than one fault condition.

Worked example: binary words with constraints

Suppose a communication frame contains 8 binary positions and must contain exactly three 1s. The number of valid frames is

C(8,3) = 8!/(3!5!) = (8×7×6)/(3×2×1) = 56

If the first position must be 1, two of the remaining seven positions must contain 1s, giving C(7,2)=21. The constraint has therefore reduced the valid set from 56 to 21 frames.

4. Recurrence Relations and Generating Functions

A recurrence relation defines a sequence using earlier terms. For example, the number of binary strings of length n containing no consecutive 1s satisfies

an = an−1 + an−2, n ≥ 2

with a0=1 and a1=2. A valid string either begins with 0, followed by a valid string of length n−1, or begins with 10, followed by a valid string of length n−2. Consequently, an is the Fibonacci sequence shifted in index, and a8=55.

A linear homogeneous recurrence with constant coefficients, such as

an = c1an−1+c2an−2

is solved through its characteristic equation r2−c1r−c2=0. Distinct roots produce a general form involving powers of those roots; repeated roots require an additional polynomial factor. Initial conditions determine the constants.

A generating function encodes a sequence a0,a1,… as

A(x) = ∑n=0∞ an xn

as a formal power series. Generating functions convert recurrence relations into algebraic equations and are useful for counting constrained configurations, analysing queueing models, and deriving coding distributions. Their use requires attention to convergence when numerical evaluation is intended; as formal series, convergence is not required for coefficient manipulation.

5. Graphs and Trees

A graph G=(V,E) consists of a vertex set V and an edge set E. In an undirected graph, an edge joins two unordered vertices; in a directed graph, each edge has an orientation. Weighted graphs assign a numerical weight to each edge, such as distance, cost, delay, or energy.

The degree of a vertex is the number of incident edges. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges. The handshaking lemma states

∑v∈V deg(v) = 2|E|

for every finite undirected graph, because each edge contributes two to the degree sum. A directed graph satisfies separate equalities for total indegree and total outdegree, each equal to |E|.

A walk is a sequence of adjacent vertices; a trail has no repeated edge; a path has no repeated vertex; and a circuit returns to its starting vertex. A graph is connected if every pair of vertices is joined by a path. A graph is bipartite if its vertices can be divided into two sets so that every edge joins different sets. A graph is bipartite exactly when it contains no odd cycle.

Matrices for graphs

The adjacency matrix A of a graph has Aij=1 when vertices i and j are adjacent, and 0 otherwise, for a simple unweighted graph. The entry (Ak)ij gives the number of walks of length k from i to j. Weighted adjacency matrices replace 1 by edge weights, but matrix powers then require careful interpretation because multiplication combines weights.

Euler and Hamilton concepts

An Euler trail uses every edge exactly once, whereas a Hamiltonian path visits every vertex exactly once. A connected undirected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler trail but not an Euler circuit if and only if exactly two vertices have odd degree. Hamiltonian problems generally lack an equally simple degree criterion and are computationally difficult in the general case.

Trees and spanning trees

A tree is a connected undirected graph with no cycles. For a tree with n vertices, the following are equivalent: it has n−1 edges; exactly one path joins every pair of vertices; and removing any edge disconnects it. A spanning tree contains every vertex of a connected graph and is itself a tree.

Minimum spanning trees minimise the sum of edge weights. Kruskal’s algorithm repeatedly selects the least-weight edge that does not create a cycle; Prim’s algorithm grows one tree by adding the least-weight edge connecting the current tree to an unvisited vertex. Both require non-negative or arbitrary edge weights only insofar as “minimum” is well-defined; unlike shortest-path algorithms, negative weights do not invalidate the spanning-tree objective.

6. Boolean Algebra and Switching Functions

Boolean algebra operates on values 0 and 1. The basic operations are complement x′, conjunction xy, and disjunction x+y. Important identities include

x + 0 = x, x·1 = x, x + x′ = 1, x·x′ = 0
x + xy = x, x(x+y) = x

and De Morgan’s laws

(x+y)′ = x′y′, (xy)′ = x′+y′

A switching function of n binary variables maps {0,1}n to {0,1}. It can be represented by a truth table, Boolean expression, logic circuit, or canonical sum of products. A minterm is a product containing every variable once, either complemented or uncomplemented. A function may be simplified algebraically or by Karnaugh maps for a small number of variables. For larger systems, Quine–McCluskey procedures and computer-aided logic minimisation are preferable.

The practical objective is not always the shortest Boolean expression. Delay, fan-in, power dissipation, hazard behaviour, testability, and technology-specific constraints may be more important. Static hazards can arise when unequal propagation delays cause an output to change briefly during an input transition; redundancy may be deliberately retained to suppress such hazards.

7. Probability and Reliability in Discrete Systems

A finite probability model consists of a sample space Ω and a probability function P satisfying P(Ω)=1 and non-negativity. For events A and B,

P(A∪B) = P(A)+P(B)−P(A∩B)

Conditional probability is

P(A|B) = P(A∩B)/P(B), P(B)>0

Independence means P(A∩B)=P(A)P(B), not merely that the events appear unrelated. Bayes’ theorem is

P(A|B) = P(B|A)P(A)/P(B), P(B)>0

If X is a discrete random variable, its expectation and variance are

E[X] = ∑x xP(X=x)
Var(X) = E[(X−E[X])2] = E[X2]−(E[X])2

For a binomial random variable counting successes in n independent trials with success probability p,

P(X=k) = C(n,k)pk(1−p)n−k

where k=0,1,…,n.

In a series system, all components must operate, so independent component reliabilities R1,…,Rn give

Rseries = ∏i=1n Ri

For an independent parallel system requiring at least one functioning component,

Rparallel = 1 − ∏i=1n(1−Ri)

These formulas assume statistically independent component failures and clearly defined operating conditions. Common-cause failures violate this assumption and can substantially reduce actual system reliability.

8. Algorithms and Computational Complexity

An algorithm is a finite, unambiguous procedure that transforms input into output. Correctness has two components: partial correctness, meaning that a terminating algorithm produces a correct result, and termination, meaning that it eventually stops for every permitted input.

The asymptotic notation O(g(n)) describes an upper growth bound up to a constant factor for sufficiently large n. Θ(g(n)) describes a tight asymptotic bound, while Ω(g(n)) describes a lower bound. For example, binary search on a sorted array has time complexity O(log n) because the remaining search interval is approximately halved at each step. Linear search has O(n) worst-case complexity.

Polynomial-time problems are commonly regarded as tractable at scale, although the degree and constants matter in practice. Many combinatorial optimisation problems, including general travelling-salesperson and Hamiltonian-cycle decision problems, are NP-hard or NP-complete in suitable formulations. This classification does not say that every instance is difficult, but it warns that no efficient algorithm is currently known for all instances under standard complexity assumptions.

Engineering responses include approximation algorithms, dynamic programming, branch and bound, randomised algorithms, heuristics, parameterised algorithms, and exploiting special graph structure. A solution should report not only whether an algorithm works, but also its memory use, worst-case behaviour, numerical robustness, and suitability for real-time constraints.

9. Applied Case: Reliable Routing in a Sensor Network

Background

Consider an illustrative wireless sensor network with five nodes: a gateway G and sensors A,B,C,D. Links have measured transmission costs and estimated independent reliabilities. The design objective is to provide a low-cost route from each sensor to the gateway while retaining a backup path for critical data.

Problem

A single shortest route may be inexpensive but vulnerable to one link failure. Conversely, installing every possible link increases energy consumption and maintenance cost. The engineer must balance connectivity, reliability, and resource constraints.

Analysis

The network is represented by a weighted graph. Vertices represent devices; edges represent communication links; weights represent energy or delay. A minimum spanning tree can connect all nodes with minimum total link cost, but it supplies only one route between any pair. Therefore, a tree alone does not provide redundancy.

Suppose two independent paths from a sensor to the gateway have reliabilities 0.90 and 0.80. If the system can use either path, the route-level reliability is

R = 1 − (1−0.90)(1−0.80) = 1 − (0.10)(0.20) = 0.98

This calculation assumes path failures are independent. If both paths share a power source or radio environment, the result is optimistic because the failures are correlated.

Approach and solution

The engineer first constructs a graph and removes links violating range or energy limits. Dijkstra’s algorithm identifies least-cost paths when all link costs are non-negative. A second path is selected subject to a node-disjoint or edge-disjoint constraint, depending on the failure model. Reliability is then evaluated using the appropriate series and parallel model. If exact network reliability is required, the problem may involve enumerating connected subgraphs and can become computationally expensive; decomposition, binary decision diagrams, simulation, or approximate methods may be used.

Outcome

The resulting design may cost more than a minimum spanning tree but substantially improve service continuity. A documented design should state link assumptions, failure definitions, time interval, traffic requirements, and whether reliability estimates are empirical or model-based.

Learning points

  1. A minimum-cost structure is not automatically the most reliable structure.
  2. Graph topology and probability models must be analysed together.
  3. Independence assumptions require physical justification.
  4. The correct optimisation objective depends on application priorities.
  5. Safety-critical deployments require validation with measured failure data.

10. Contemporary Developments and Professional Practice

Discrete mathematics now supports error-correcting codes, network coding, blockchain protocols, hardware verification, quantum information, distributed consensus, and machine-learning data structures. In communication systems, finite fields underpin Reed–Solomon, BCH, and many modern coding methods. In formal hardware verification, satisfiability solvers determine whether Boolean specifications are consistent and whether unwanted states are reachable.

AI systems also depend on discrete structures: search spaces, graphs, symbolic constraints, combinatorial optimisation, and discrete latent variables. However, an AI-generated proof, circuit simplification, or network design must be independently verified. Plausible output is not evidence of mathematical correctness. Reproducibility requires stating data, assumptions, algorithms, random seeds where relevant, and validation procedures.

Professional practice requires careful treatment of privacy and security. Counting attack configurations can assist defensive risk analysis but may also expose vulnerabilities. Cryptographic designs must use established, peer-reviewed constructions rather than relying on an apparently complex combinatorial scheme. Safety-related logic should be formally specified, tested against boundary cases, and reviewed independently.

Challenges and Limitations

Discrete models simplify reality. Graph edges may omit interference, component ageing, physical obstructions, or common-cause failures. Counting formulas may become invalid when objects are not distinct, choices are dependent, or constraints overlap. Complexity results describe asymptotic growth rather than actual performance on a particular processor. Boolean minimisation may reduce gate count while increasing delay or hazards. Probability estimates are only as credible as the data and assumptions behind them.

Best practice is therefore to define the system boundary, identify all variables, state assumptions, test small cases, use more than one verification method, and perform sensitivity analysis. When a result depends strongly on independence, uniformity, or complete observation, that dependence should be reported explicitly.

Chapter Summary

Discrete mathematics provides the formal language for finite engineering systems. Set theory describes collections and constraints; relations and functions model association and transformation; logic supports specification and proof; combinatorics counts configurations; recurrence relations describe recursive structures; graphs represent networks; trees provide efficient hierarchical and connecting structures; Boolean algebra models digital switching; probability evaluates uncertainty and reliability; and complexity theory assesses scalability.

The addition and multiplication principles, permutations, combinations, inclusion–exclusion, recurrence relations, and generating functions form the main combinatorial toolkit. Graph algorithms such as shortest-path and minimum-spanning-tree methods support network engineering, while Boolean identities support digital design. Reliable application requires explicit assumptions, especially regarding independence, distinctness, weights, and failure mechanisms. At postgraduate level, mathematical elegance must be combined with modelling judgement, algorithmic awareness, validation, and ethical professional practice.

Key Terms

Set: A well-defined collection of distinct objects.

Cardinality: The number of elements in a finite set.

Relation: A subset of a Cartesian product.

Function: A mapping assigning exactly one output to each input.

Bijection: A function that is both injective and surjective.

Proposition: A declarative statement with a definite truth value.

Tautology: A proposition true under every valuation.

Induction: A proof method using a base case and an inductive implication.

Permutation: An ordered arrangement or selection.

Combination: An unordered selection.

Inclusion–exclusion: A method correcting overlaps among sets.

Recurrence relation: A rule defining terms from earlier terms.

Generating function: A formal power series encoding a sequence.

Graph: A structure of vertices and edges.

Tree: A connected acyclic undirected graph.

Spanning tree: A tree containing every vertex of a connected graph.

Boolean algebra: Algebra of binary variables and logical operations.

Reliability: The probability that a system performs its required function.

Algorithm: A finite, unambiguous computational procedure.

Computational complexity: The resource growth of an algorithm with input size.

Review Questions

Short Answer Questions

  1. Distinguish an injective function from a surjective function.
  2. State the multiplication principle of counting.
  3. What conditions make an undirected graph Eulerian?
  4. Define a spanning tree.
  5. State the difference between O(n) and Θ(n).

Long Answer Questions

  1. Explain logical implication, converse, contrapositive, and biconditional with suitable truth-table reasoning.
  2. Derive the recurrence for binary strings with no consecutive 1s and compute the first several terms.
  3. Explain permutations, combinations, and stars-and-bars, including their assumptions and engineering uses.
  4. Describe adjacency matrices, paths, connectivity, Euler circuits, Hamiltonian paths, and spanning trees.
  5. Discuss Boolean minimisation in digital design, including the trade-off between expression size, delay, power, and hazards.

Analytical / Application Questions

  1. A communication frame has 10 binary positions and exactly four error-control bits set to 1. Determine the number of possible patterns. How does the answer change if the first bit must be 1?
  2. A system has three independent parallel components with reliabilities 0.85, 0.90, and 0.95. Calculate system reliability and explain one physical reason why the calculated value may overestimate field reliability.
  3. Design a graph-based routing strategy for a sensor network requiring a primary and a node-disjoint backup route. Explain the algorithmic, reliability, energy, and verification considerations.

Multiple Choice Questions with Answers

Question 1

How many unordered selections of 3 objects can be made from 8 distinct objects?

A. 24

B. 56

C. 336

D. 512

Correct Answer: B. 56

Question 2

Which condition is necessary and sufficient for a connected undirected graph to have an Euler circuit?

A. Exactly two vertices have odd degree

B. Every vertex has degree one

C. Every vertex has even degree

D. The graph has no cycles

Correct Answer: C. Every vertex has even degree

Question 3

What is the reliability of two independent parallel components with reliabilities 0.9 and 0.8?

A. 0.72

B. 0.82

C. 0.90

D. 0.98

Correct Answer: D. 0.98

Question 4

Which expression is logically equivalent to p → q?

A. q → p

B. ¬q → ¬p

C. p ∧ q

D. ¬p → q

Correct Answer: B. ¬q → ¬p

Question 5

A tree with 12 vertices has how many edges?

A. 10

B. 11

C. 12

D. 24

Correct Answer: B. 11

Question 6

The number of binary strings of length 5 with no consecutive 1s is:

A. 8

B. 13

C. 16

D. 32

Correct Answer: B. 13

Question 7

Which algorithm is appropriate for shortest paths when all edge weights are non-negative?

A. Dijkstra’s algorithm

B. Kruskal’s algorithm

C. Boolean minimisation

D. Depth-independent hashing

Correct Answer: A. Dijkstra’s algorithm

Question 8

For finite sets A and B, which identity is correct?

A. |A∪B|=|A|+|B| always

B. |A∪B|=|A|−|B|

C. |A∪B|=|A|+|B|−|A∩B|

D. |A∪B|=|A∩B|

Correct Answer: C. |A∪B|=|A|+|B|−|A∩B|

Question 9

What does (Ak)ij represent for an unweighted graph adjacency matrix?

A. The shortest path cost from i to j

B. The number of walks of length k from i to j

C. The degree of vertex i

D. The number of vertices in the graph

Correct Answer: B. The number of walks of length k from i to j

Question 10

Which statement about a binomial random variable is correct?

A. Trials must have changing success probabilities

B. Trials must be independent with a constant success probability

C. It can count only failures

D. Its outcomes must be continuous

Correct Answer: B. Trials must be independent with a constant success probability
Engineering Mathematics
Chapter 10 of 10