maths.free › Combinatorics & Graph Theory › 1. An Introduction to Combinatorics › Discussion

Discussion

Over coffee after their first combinatorics class, Xing remarked This doesn't seem to be going like calculus. I'm expecting the professor to teach us how to solve problemsat least some kinds of problems.

Discussion

Over coffee after their first combinatorics class, Xing remarked This doesn't seem to be going like calculus. I'm expecting the professor to teach us how to solve problemsat least some kinds of problems. Instead, a whole bunch of problems were posed and we were asked whether we could solve them.

Yolanda jumped in, saying You may be judging things too quickly. I'm fascinated by these kinds of questions. They're different.

Zori grumpily laid bare her concerns: After getting out of Georgia Tech, who's going to pay me to count necklaces, distribute library books or solve Sudoku puzzles?

Bob politely countered, But the problems on networks and graphs seemed to have practical applications. I heard my uncle, a very successful business guy, talk about franchising problems that sound just like those.

Alice speculated, All those network problems sound the same to me. A fair to middling computer science major could probably write programs to solve any of them.

Dave mumbled, Maybe not. Similar sounding problems might actually be quite different in the end. Maybe we'll learn to tell the difference.

After a bit of quiet time interrupted only by lattes disappearing, Carlos said softly, It might not be so easy to distinguish hard problems from easy ones.

Alice followed, Regardless, what strikes me is that we all, well almost all of us, she said, rolling her eyes at Bob, seem to understand everything talked about in class today. It was so very concrete. I liked that.

Symbols used here

y',\ y''
first and second derivative of y
Prime notation for derivatives with respect to x (or t).
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.

Tente o seu próprio

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

Mais em 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