maths.free › Combinatorics & Graph Theory › 4. Combinatorial Basics › Combinatorial Basics: exercises

Combinatorial Basics: exercises

Combinatorial Basics: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (4)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. If you have to put \(n+1\) pigeons into \(n\) holes, you have to put two pigeons into the same hole. What happens if you have to put \(mn+1\) pigeons into \(n\) holes?

  2. Consider the set \(X=\{1,2,3,4,5\}\) and suppose you have two holes. Also suppose that you have \(10\) pigeons: the \(2\)-element subsets of \(X\). Can you put these \(10\) pigeons into the two holes in a way that there is no \(3\)-element subset \(S=\{a,b,c\}\subset X\) for which all pigeons from \(S\) go in the same hole? Then answer the same question if \(X=\{1,2,3,4,5,6\}\) with \(15 = C(6,2)\) pigeons.

  3. Let \(n=10,000\). Suppose a friend tells you that he has a secret family of subsets of \(\{1,2,\dots,n\}\), and if you guess it correctly, he will give you one million dollars. You think you know the family of subsets he has in mind and it contains exactly half the subsets, , the family has \(2^{n-1}\) subsets. Discuss how you can share your hunch with your friend in an effort to win the prize.

  4. Let \(N\) denote the set of positive integers. When \(f:N\rightarrow N\) is a function, let \(E(f)\) be the function defined by \(E(f)(n) = 2^{f(n)}\). What is \(E^5(n^2)\)?

Symbols used here

x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Kuri Gukoresha

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

in Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs