University Discrete Mathematics — Counting Techniques Worksheet

All 11 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one.

1. Q1The Sum and Product Rules

   Let $A=\{1,2,3,4\}$. A relation on $A$ is any subset of $A\times A$.

   1. How many relations on $A$ are there?
   2. How many of them are reflexive, that is, contain $(a,a)$ for every $a\in A$?
   3. How many of them are symmetric, that is, contain $(b,a)$ whenever they contain $(a,b)$?
   4. How many subsets of $\{1,2,\dots ,10\}$ contain $1$ but do not contain $2$?
2. Q2The Sum and Product Rules
   1. Given $720=2^4·3^2·5$, how many positive divisors does $720$ have?
   2. How many of those divisors are even?
   3. How many positive integers less than $1000$ have every digit odd?
3. Q3The Pigeonhole Principle
   1. What is the least number of integers that must be chosen from $\{1,2,\dots ,30\}$ to guarantee that two of them leave the same remainder on division by $7$? Show that one fewer is not enough.
   2. $58$ students each choose one of $5$ project topics. What is the largest number of students that is guaranteed to share a topic, whatever they choose?
   3. How many students would there have to be to guarantee that at least $15$ of them share a topic?
4. Q4The Pigeonhole Principle

   A set $S$ of $7$ integers is chosen from $\{1,2,\dots ,12\}$.

   1. Explain, naming the pigeons and the boxes, why $S$ must contain two consecutive integers.
   2. Give a set of $6$ integers from $\{1,2,\dots ,12\}$ with no two consecutive, and say what this shows about part (a).
5. Q5Permutations
   1. How many permutations of $\{1,2,\dots ,8\}$ are there?
   2. In how many of them do the four even numbers occupy the first four positions?
   3. In how many of them is $1$ immediately followed by $2$?
   4. How many injective (one-to-one) functions $f:\{1,2,3\}\to \{1,2,\dots ,8\}$ are there?
6. Q6Combinations

   A bit string is a string of $0$s and $1$s.

   1. How many bit strings of length $12$ have exactly five $1$s?
   2. How many bit strings of length $12$ have at least ten $1$s?
   3. How many $4$-element subsets of $\{1,2,\dots ,12\}$ have largest element $9$?
7. Q7Combinations

   A lattice path from $(0,0)$ to $(7,4)$ is a sequence of unit steps, each one to the right $(+1,0)$ or up $(0,+1)$.

   1. How many lattice paths go from $(0,0)$ to $(7,4)$?
   2. How many of them pass through the point $(3,2)$?
   3. How many of them avoid $(3,2)$?
8. Q8The Binomial Theorem and Pascal's Identity
   1. Find the coefficient of $x^5{y}^3$ in the expansion of $(2x-y{)}^8$.
   2. Find the term independent of $x$ in the expansion of ${(x^2+{\displaystyle \frac{3}{x}})}^6$.
   3. Find the coefficient of $x^4$ in $(1+x{)}^6(1-x{)}^2$.
9. Q9The Binomial Theorem and Pascal's Identity
   1. Given ${\displaystyle \left(\genfrac{}{}{0ex}{}{15}{6}\right)}=5005$ and ${\displaystyle \left(\genfrac{}{}{0ex}{}{15}{7}\right)}=6435$, find ${\displaystyle \left(\genfrac{}{}{0ex}{}{16}{7}\right)}$ and ${\displaystyle \left(\genfrac{}{}{0ex}{}{16}{9}\right)}$ without computing any factorial.
   2. Find the integer $n\ge 5$ with ${\displaystyle \left(\genfrac{}{}{0ex}{}{n}{3}\right)}={\displaystyle \left(\genfrac{}{}{0ex}{}{n}{5}\right)}$.
   3. Evaluate ${\displaystyle {\sum }_{k=0}^8(-1{)}^k(\genfrac{}{}{0ex}{}{8}{k})3^{8-k}}$.
10. Q10Permutations and Combinations with Repetition
    1. How many solutions does $x_1+x_2+x_3+x_4=15$ have in nonnegative integers?
    2. How many of those solutions have every $x_i\ge 2$?
    3. How many different strings can be formed by rearranging all the letters $a,a,b,b,b,c,c,c$?
11. Q11Synthesis — drawing on several topics in this unit

    Count the functions $f:\{1,2,3,4\}\to \{1,2,3,4,5,6\}$ that are

    1. arbitrary;
    2. injective;
    3. strictly increasing, $f(1)<f(2)<f(3)<f(4)$;
    4. nondecreasing, $f(1)\le f(2)\le f(3)\le f(4)$.

The 7 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

The sum and product rules

Every count in this set begins with one question about the thing being counted: is it built by a sequence of independent decisions, or does it split into cases, exactly one of which happens? Decisions in sequence multiply; cases add. Nothing else on this sheet is new.

Q1 counts relations on a four-element set, and the whole question turns on the definition it gives you: a relation is a subset of A × A. So one decision per ordered pair — in or out — and the count of subsets of any finite set is a product of two-way choices. Q1(b) and Q1(c) add a constraint, and the method is the same in both: sort the ordered pairs into those the condition forces, those it leaves free, and those it ties to each other so that one decision settles two pairs at once. Reflexivity forces a pair; symmetry ties (a, b) to (b, a). Count the free decisions, not the pairs. Q1(d) is the same idea on plain subsets: two elements are decided for you, and the rest are free.

Q2(c) is where the sum rule earns its place. "Less than 1000" is not one shape, it is three (one-digit, two-digit, three-digit), and those cases do not overlap, so count each with the product rule and add. Decide before you start whether a leading zero would count an object twice — that decision, made explicitly, is what keeps the cases disjoint.

The pigeonhole principle

The principle itself is one line: if more objects than boxes are placed into boxes, some box holds two objects. All the difficulty is in choosing the boxes, and a proof that does not name them is not a proof.

Q3(a) tells you what the boxes are — the possible remainders on division by 7 — so the work is counting them, stating the principle in the form "one more than the number of boxes forces a repeat", and then doing the second half, which is the half students skip: showing that one fewer is not enough. That takes an explicit selection with all remainders different. A bound is only proved least when both halves are there.

Q4 gives you neither. Seven integers are chosen from a twelve-element set and you must show two of them are consecutive, "naming the pigeons and the boxes" — so the pigeons are the chosen integers, and the boxes are yours to invent. Design them against two requirements at once: there must be fewer boxes than chosen integers, and two integers that land in the same box must be consecutive automatically. Partition the whole set of twelve so that both hold, and the argument is three lines.

Permutations

A permutation is an ordered arrangement. n! counts the orders of n distinct objects, and P(n, r) = n!/(n − r)! counts the ordered selections of r of them, because each position placed removes one object from the pool for the next.

Q5 runs four variations on one set of eight. Part (a) is the plain factorial. Part (b) restricts which values may sit in which positions, and the method is the product rule over two independent blocks: arrange the values that must occupy the first four positions among themselves, arrange the rest among the remaining positions, and multiply. Part (c) is the block trick: when one value must be immediately followed by another, glue the two into a single object, arrange the objects that remain, and ask whether the glued block has more than one internal order — here the order inside it is fixed by the word "followed", which is exactly the detail to notice.

Combinations

A combination is an unordered selection: C(n, r) = n!/(r!(n − r)!). The test is always the same — would rearranging the chosen items give a different object? If not, divide out the r! orders.

Q6 works with bit strings, where the useful move is to stop thinking about strings and start thinking about positions. A string of length 12 with exactly five 1s is determined by which five of the twelve positions hold the 1s, so the count is a choice of a five-element subset. Q6(b) says "at least ten", which is not one combination but a union of disjoint cases — exactly ten, exactly eleven, exactly twelve — so count each and add by the sum rule. Q6(c) is the same conversion in the other direction: fixing the largest element of a subset decides one element outright and confines the rest to the values below it, so count the rest as a combination from that smaller range.

The binomial theorem and Pascal's identity

The binomial theorem says that expanding (a + b)ⁿ means choosing, from each of the n factors, either a or b — so the coefficient of the term with k copies of b is the number of ways to choose those k factors.

Q8(c) is a product of two expansions, so one exponent is no longer enough. Expand the smaller factor in full — it is short — and then collect: the coefficient of x⁴ in the product is a sum of products of coefficients whose exponents add to four. Write the two lists side by side and pair them off; that bookkeeping is the question.

Q9 is about the identities rather than the expansion. Pascal's identity builds a coefficient from the two above it, and the symmetry identity reflects one across the middle of its row:

Q9(a) hands you two coefficients from one row and forbids factorials, so the only route is the two identities: one of them steps down a row, the other moves along it, and the second half of the question is reachable from the first only if you spot which reflection lands on it. Q9(b) is the symmetry identity used as an equation — two coefficients from the same row are equal when their lower entries are equal or when they add to the top entry, and the condition n ≥ 5 is there to tell you which solutions to keep. Q9(c) is the binomial theorem read from right to left: match the sum term by term against the expansion of (a + b)ⁿ, reading n off the upper index, b off the factor carrying the sign, and a off the remaining power. It collapses to a single power of a number.

Permutations and combinations with repetition

Two formulas, and they solve different problems. Choosing r objects from n kinds, with repetition allowed and order irrelevant, is counted by C(n + r − 1, r), equivalently C(n + r − 1, n − 1); arranging n objects that are not all distinct divides the factorial by the orders inside each group of identical objects.

Q10(a) is the equation form, and the translation is the point: a solution is a way of distributing n identical units among four labelled variables, so picture n stars in a row with three bars dropped among them, the bars marking where one variable ends and the next begins. The count is then a choice of positions for the bars, which is an ordinary combination. Q10(b) adds a floor to every variable, and the move is substitution: give each variable its required minimum up front, set yᵢ equal to what is left over, and count the solutions of the smaller equation in the yᵢ — which has no constraint beyond nonnegativity, so part (a) applies unchanged.

The synthesis question

Q11 counts functions from a four-element set to a six-element set under four conditions, and the four answers use four different tools from this set — which is why it is last.

Part (a) is the product rule: specifying a function means choosing an output for each input, independently, with nothing ruled out. Part (b) is Q5(d) again — an injective function is an ordered selection of outputs, so P(n, r). Part (c) is the one worth thinking about: a strictly increasing function is completely determined by the set of its four output values, because once you know which four values are used there is exactly one order they can appear in. So the count is a choice of a four-element subset, with no arrangement at all. Part (d) allows equality, which is repetition — the same four values may be reused — so it is Q10's question in function language.

Preview all 6 pages

Click any page to open the full PDF.

Getting the most out of it

Describe one object before you count them all

Write a sentence saying what someone would have to tell you to pin down a single object — one relation, one divisor, one path, one function. Almost every counting error is a count of something slightly different from what was asked, and the sentence is what exposes it.

Ask "does order matter?" and "may things repeat?"

Those two questions, answered out loud, select among the four formulas in this set: P(n, r), C(n, r), counting with repetition and the multiset arrangement. Answer them before writing any symbol, not after.

Count the complement when the condition says "at least" or "avoid"

Write the complement beside the event and count whichever is shorter, as Q7(c) invites. A single subtraction beats a union of cases, and it is the habit that keeps Q6(b)-style case lists short enough to be right.

Check a small count by listing it

When the numbers allow it, list the objects and compare the length of the list with the formula. A disagreement tells you which assumption about order or repetition was wrong, and the habit carries into the counts far too large to list.

Write the argument, not just the number

The pigeonhole questions and the correspondence in Q11(c) are marked as proofs: name the objects and the boxes, state the principle you are applying, and say why the correspondence misses nothing. A number with no argument under it is a guess that happens to be right.

Common questions