Counting, Combinatorics and Discrete Structures

Introduction

Computer applications routinely require answers to questions such as: How many passwords can be generated? How many ways can tasks be assigned to processors? How large is a search space? How many records may satisfy at least one of several conditions? Counting theory provides systematic methods for answering such questions without listing every possibility.

Combinatorics is the study of discrete arrangements, selections, and structures. It supports algorithm analysis, database design, cryptography, probability, coding theory, artificial intelligence, network configuration, and software testing. A central principle is that the method of counting must match the structure of the problem: alternatives are added, independent stages are multiplied, order may or may not matter, and restrictions must be handled explicitly.

Learning Objectives

After completing this chapter, you should be able to:

• distinguish finite discrete structures and count their elements;
• apply the sum rule and product rule;
• use factorials, permutations, combinations, and binomial coefficients;
• solve problems involving repetition, restrictions, and circular arrangements;
• apply inclusion–exclusion and the pigeonhole principle;
• establish and use basic combinatorial identities;
• estimate search spaces and relate counting to algorithmic complexity;
• select an appropriate counting model for a practical computing problem.

1. Discrete Structures and Counting Models

A set is a collection of distinct objects. Its cardinality, written |S|, is the number of elements in S. A sequence is an ordered list, whereas a set does not normally record order. A multiset permits repeated elements. These distinctions are fundamental.

For example, the set {a, b, c} and the sequence (a, b, c) contain the same symbols but represent different mathematical objects. The sequences (a, b, c) and (b, a, c) are different because their order differs.

Before counting, identify four questions:

1. What objects are being counted?
2. Are the choices ordered?
3. Is repetition allowed?
4. Are there restrictions or overlapping categories?

A counting model is valid only when it represents all and only the intended outcomes.

2. The Sum Rule and Product Rule

2.1 Sum rule

If a task can be completed in one of several mutually exclusive ways, and method i has nᵢ outcomes, then the total number of outcomes is the sum of the alternatives.

The alternatives must be disjoint: no outcome should be counted in two categories. More generally, if sets A₁, A₂, …, Aₖ are pairwise disjoint, then |A₁ ∪ A₂ ∪ … ∪ Aₖ| = |A₁| + |A₂| + … + |Aₖ|.

Example. A software menu offers 4 text export formats and 3 image export formats. Since an export is either text or image, the number of format choices is 4 + 3 = 7.

2.2 Product rule

If a process has k successive stages, with n₁ choices at stage 1, n₂ choices at stage 2 for every first choice, and so on, then the total number of outcomes is

The number of choices at a later stage may depend on earlier choices. In that case, count each complete branch or use a sum of products.

Example. A user ID consists of 2 uppercase letters followed by 3 digits. Repetition is permitted. There are 26 choices for each letter and 10 for each digit, so

If repeated symbols were forbidden, the count would instead be 26 × 25 × 10 × 9 × 8.

A useful representation is a decision tree: each level represents a stage, and each root-to-leaf path represents one complete outcome. The product rule counts paths when the branching structure is uniform; summing leaves handles nonuniform branching.

3. Factorials and Permutations

For a nonnegative integer n, the factorial is defined by

with 0! = 1. The convention 0! = 1 is necessary because it makes recursive identities and empty arrangements consistent.

3.1 Permutations of distinct objects

The number of ways to arrange n distinct objects in a line is

The first position has n choices, the second n − 1, and so forth.

The number of ordered arrangements of r objects selected from n distinct objects is

where 0 ≤ r ≤ n.

Worked example. From 8 applicants, a company selects a chairperson, secretary, and treasurer. The positions are distinct, so order or role assignment matters:

3.2 Permutations with repeated objects

If n objects contain repetitions, with n₁ identical objects of one type, n₂ of another, and so on, the number of distinct linear arrangements is

where n₁ + n₂ + ⋯ + nₖ = n.

Example. The letters in LEVEL contain L twice and E twice. The number of distinct arrangements is 5!/(2!2!) = 30.

3.3 Circular permutations

For n distinct objects arranged around a circle, rotations are treated as identical. Fixing one object removes rotational duplication, giving

This formula assumes that reflections are different. If arrangements that are mirror images are also considered identical, further treatment is required; for distinct objects under rotation and reflection, the count is generally (n − 1)!/2 for n > 2.

4. Combinations and Binomial Coefficients

A combination selects objects without regard to order. The number of ways to choose r objects from n distinct objects is

where 0 ≤ r ≤ n.

The relationship between permutations and combinations is

First choose the r objects, then arrange them in r! orders.

Worked example. A committee of 4 is selected from 10 students. Since committee membership has no positions,

4.1 Combinations with repetition

The number of ways to select r objects from n types when repetition is allowed and order is irrelevant is

This applies when each type may be selected any nonnegative number of times. It is commonly derived using the stars-and-bars model: r identical stars are separated into n groups by n − 1 bars.

Example. The number of ways to choose 5 pieces of fruit from 3 types, with unlimited supply, is

If each fruit must be different, or if supplies are limited, this formula is not directly applicable.

4.2 Binary strings and subsets

Every subset of an n-element set corresponds to an n-bit string: bit 1 indicates inclusion and bit 0 indicates exclusion. Therefore, the number of subsets is 2ⁿ. The number of subsets containing exactly r elements is C(n,r).

This interpretation is important in feature selection, access-control configurations, and exhaustive search algorithms.

5. The Binomial Theorem and Identities

The binomial theorem expands a nonnegative integer power of a sum:

Here n is a nonnegative integer, r ranges from 0 to n, and x and y may be numbers or algebraic quantities for which the operations are defined.

Setting x = y = 1 gives

Setting x = 1 and y = −1 gives

Important identities include:

• Symmetry: C(n,r) = C(n,n−r).
• Pascal identity: C(n,r) = C(n−1,r−1) + C(n−1,r).
• Hockey-stick identity: ∑ᵢ₌ᵣⁿ C(i,r) = C(n+1,r+1).

The symmetry identity follows because choosing r objects to include is equivalent to choosing n − r objects to exclude. Pascal’s identity partitions an r-subset according to whether it contains a designated element.

Pascal’s identity produces Pascal’s triangle, whose nth row contains the coefficients of (x + y)ⁿ. It also supports dynamic programming: a table of binomial coefficients can be computed in O(nr) time and avoids repeated factorial calculations.

6. Inclusion–Exclusion

The sum rule fails when categories overlap. For two finite sets A and B,

The intersection is subtracted because it was counted twice.

For three sets,

The general inclusion–exclusion formula is

where each sum ranges over subsets of the indicated number of sets.

Worked example. In a class of 60 students, 35 know Python, 28 know Java, and 15 know both. The number who know at least one is

35 + 28 − 15 = 48.

Thus 12 know neither, assuming these are the only two categories being measured.

In computing, inclusion–exclusion helps count configurations satisfying at least one constraint, records matching at least one query condition, and assignments avoiding forbidden positions.

7. The Pigeonhole Principle

The pigeonhole principle states that if more than n objects are placed into n boxes, at least one box contains at least two objects. Formally, distributing n + 1 objects among n categories guarantees a repeated category.

The generalized form states that distributing N objects among k boxes places at least ⌈N/k⌉ objects in some box, where ⌈x⌉ is the least integer greater than or equal to x.

Example. If 101 files are stored in 100 folders, at least one folder contains at least 2 files.

Application to hashing. A hash function maps a potentially very large key space into a finite table of m slots. If more than m distinct keys are inserted, a collision is mathematically unavoidable. A good hash function can distribute keys well, but it cannot eliminate collisions when the key space exceeds the slot count.

The principle proves existence, not necessarily the identity of the repeated object or a procedure for finding it. This distinction matters in algorithm design.

8. Counting Under Constraints

Real systems rarely permit every theoretical arrangement. Constraints must be incorporated into the count rather than handled informally.

8.1 Complementary counting

Sometimes it is easier to count all outcomes and subtract invalid outcomes:

Example. The number of 4-digit PINs using digits 0–9, with repetition allowed, is 10⁴ = 10,000. PINs whose four digits are not all identical number 10,000 − 10 = 9,990.

8.2 Restrictions by position

If a password has 6 characters, begins with an uppercase letter, and then contains 5 lowercase letters, the number is 26⁶ only if every position has the same allowed choices. Under the stated restriction, it is 26 × 26⁵ = 26⁶, but if the final positions are digits, the count changes accordingly. The lesson is to separate positions by their permitted alphabets.

8.3 At least one condition

“At least one” often signals either inclusion–exclusion or complementary counting. For example, among 8-bit strings, the number containing at least one 1 is 2⁸ − 1 = 255, because only the all-zero string is excluded.

9. Counting and Algorithmic Complexity

Counting exposes the size of a search space. If an algorithm examines every subset of n items, its search space has size 2ⁿ. If it examines every ordering, the space has size n!. If it chooses r items in order, it has P(n,r) possibilities.

These growth rates have different practical consequences:

For n = 30, 2ⁿ = 1,073,741,824, already too large for naive exhaustive enumeration in many applications. For n = 10, n! = 3,628,800; for n = 20, n! exceeds 2.4 × 10¹⁸. Counting therefore guides the choice between brute force, pruning, dynamic programming, approximation, and heuristic methods.

Counting possibilities does not by itself prove an algorithm’s running time: the cost of processing each possibility and the effectiveness of pruning must also be considered. Nevertheless, it provides a lower-level structural estimate of the work required by exhaustive methods.

10. Applied Case: Testing a Multifactor Authentication Policy

Background. Consider an illustrative university application that generates temporary authentication codes. Each code has 8 positions: the first 2 are uppercase letters and the remaining 6 are decimal digits. Digits may repeat, but letters may not.

Problem. The security team wants to estimate the code space and the proportion of codes that contain at least one zero.

Analysis. For the first two positions, the choices are 26 and 25. For each digit position, there are 10 choices. Thus

To count codes with at least one zero, use the complement. Codes with no zero have 9 choices for each digit, so

Therefore,

The fraction containing at least one zero is 518,780,000 ÷ 650,000,000 ≈ 0.7981, or approximately 79.81%.

Approach and outcome. The product rule handled position-by-position construction, while complementary counting handled the “at least one” condition. The result shows that zero occurrence is common and should not be treated as a meaningful security property. More importantly, the code space is only 650 million possibilities; rate limiting, expiration, monitoring, and multi-factor controls remain necessary.

Learning points. A large nominal space does not guarantee security. Counting must account for repetition rules, position-specific alphabets, and operational controls. Security analysis should also consider biased random generators, predictable timestamps, leaked codes, online attempt limits, and privacy requirements.

11. Limitations, Governance, and Best Practices

Counting models can be misleading when assumptions are hidden. Users may choose predictable passwords rather than uniformly selecting from the theoretical space. A database query may contain duplicate records, making set-based counting inappropriate. A hash table may have a nonuniform distribution. In each case, theoretical cardinality differs from observed frequency.

Best practices include:

• state whether objects are distinct;
• state whether order matters;
• state whether repetition is allowed;
• define the sample space before applying a formula;
• check boundary cases such as r = 0, r = n, and n = 0;
• use complements for restrictive “at least one” conditions when simpler;
• avoid double counting by defining disjoint cases or applying inclusion–exclusion;
• validate small instances by enumeration or a short program;
• protect sensitive search-space estimates, such as password and key-space analyses;
• distinguish mathematical possibility from realistic probability or human behavior.

In responsible computing, combinatorial analysis should support security and reliability rather than enable unauthorized enumeration or credential attacks. Access controls, audit logs, rate limits, and privacy-preserving data practices remain essential.

Chapter Summary

Counting is the disciplined analysis of finite possibilities. The sum rule applies to mutually exclusive alternatives, while the product rule applies to successive choices. Factorials count complete arrangements, permutations count ordered selections, and combinations count unordered selections. Repetition changes the formulas and must be stated explicitly.

Binomial coefficients describe selections, polynomial expansions, subsets, and dynamic-programming recurrences. Inclusion–exclusion corrects overcounting among overlapping categories. The pigeonhole principle guarantees repetition when objects exceed available categories. Complementary counting is often the most efficient method for restrictive conditions.

In computer applications, these tools quantify search spaces, explain hash collisions, guide security assessment, and predict when exhaustive algorithms become impractical. Correct counting depends less on memorizing formulas than on accurately identifying objects, order, repetition, overlap, and constraints.

Key Terms

Cardinality: The number of elements in a finite set.

Combination: An unordered selection of objects.

Combinatorics: The study of discrete arrangements and selections.

Complementary counting: Counting all outcomes and subtracting invalid outcomes.

Factorial: The product n × (n − 1) × ⋯ × 1, with 0! = 1.

Inclusion–exclusion: A method that corrects overcounting in unions of overlapping sets.

Multiset: A collection in which elements may occur repeatedly.

Pigeonhole principle: A principle guaranteeing repetition when more objects than categories are distributed.

Permutation: An ordered arrangement or selection.

Product rule: Multiplication of choices across successive stages.

Repetition: Reuse of an object or symbol in a selection or arrangement.

Set: A collection of distinct objects.

Sum rule: Addition of outcomes from mutually exclusive alternatives.

Search space: The complete collection of candidate solutions considered by a procedure.

Stars and bars: A model for distributing identical objects among distinct categories.

Subset: A set whose elements all belong to another set.

Binomial coefficient: C(n,r), the number of r-element subsets of an n-element set.

Disjoint sets: Sets with no common elements.

Review Questions

Short Answer Questions

1. Explain the difference between a permutation and a combination.
2. State the conditions under which the sum rule may be applied.
3. Why is 0! defined as 1?
4. State the generalized pigeonhole principle.
5. What does the expression 2ⁿ count when n is the size of a set?

Long Answer Questions

1. Derive the formula for P(n,r) using the product rule and explain its assumptions.
2. Explain the binomial theorem and derive the identity ∑ᵣ₌₀ⁿ C(n,r) = 2ⁿ.
3. Present the inclusion–exclusion formula for three sets and explain the signs.
4. Compare combinations with and without repetition using suitable examples.
5. Discuss how combinatorial counting informs the design and analysis of exhaustive algorithms.

Analytical / Application Questions

1. A system creates a 6-character identifier consisting of 2 distinct uppercase letters followed by 4 digits, with digit repetition allowed. Determine the number of possible identifiers and explain each factor.
2. In a population, 42 users access a web portal by mobile device, 35 by desktop, and 18 by both. If there are 70 users in total, determine how many use neither access method.
3. An algorithm searches every subset of a set of 25 features. Estimate the number of candidates and explain why a direct exhaustive search may be impractical.

Multiple Choice Questions with Answers

Question 1

A process has 4 choices in its first stage and 7 choices in its second stage for every first-stage choice. How many complete outcomes are possible?

A. 11

B. 28

C. 47

D. 2,804

Correct Answer: B. 28

Question 2

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

A. 24

B. 56

C. 336

D. 512

Correct Answer: C. 336

Question 3

How many committees of 4 can be selected from 10 distinct students?

A. 40

B. 120

C. 210

D. 5,040

Correct Answer: C. 210

Question 4

How many distinct arrangements can be made from the letters in LEVEL?

A. 20

B. 30

C. 60

D. 120

Correct Answer: B. 30

Question 5

How many subsets does a set containing 6 elements have?

A. 12

B. 36

C. 64

D. 720

Correct Answer: C. 64

Question 6

If |A| = 30, |B| = 22, and |A ∩ B| = 8, what is |A ∪ B|?

A. 36

B. 44

C. 52

D. 60

Correct Answer: B. 44

Question 7

What is guaranteed when 51 objects are distributed among 50 boxes?

A. Every box contains an object

B. At least one box contains at least two objects

C. Exactly one box contains two objects

D. No box contains more than two objects

Correct Answer: B. At least one box contains at least two objects

Question 8

How many ways can 5 identical objects be distributed among 3 distinct categories when categories may receive zero objects?

A. 10

B. 15

C. 21

D. 243

Correct Answer: C. 21

Question 9

Which identity expresses Pascal’s rule?

A. C(n,r) = n!/r!

B. C(n,r) = C(n−1,r−1) + C(n−1,r)

C. C(n,r) = r!/(n−r)!

D. C(n,r) = 2ⁿ

Correct Answer: B. C(n,r) = C(n−1,r−1) + C(n−1,r)

Question 10

An exhaustive algorithm examines every subset of 20 items. How many candidates does it examine?

A. 400

B. 1,048,576

C. 2,432,902,008,176,640,000

D. 20!

Correct Answer: B. 1,048,576