Math 386: Combinatorics: Announcements

Fall 2024
Tom Zaslavsky

Index

Test Grade Guidelines
Quizzes
LaTeX: Mathematical Typesetting
Corrections to the Textbook
Additions to the Textbook

Definitions and Notation
Terminology
Theorems and Other Results
Supplements, Explanations, Hints

To the main class page | the schedule page | problems page | my home page.

Test Grade Guidelines & Solutions

The letter grades are only to give you an idea of how well you're doing. I don't add letter grades. I add up your scores to get the total of test points.

Test 1 (10/16)

A	B	C	D	F
72-100	58-71	40-57	30-39	0-29

Here are solutions (not yet).

Test 2 (11/26)

A	B	C	D	F
76-100	58-75	40-57	30-39	0-29

Here are solutions (not yet).

Final Exam (12/13)

A	B	C	D	F

Quizzes and Solutions

A quiz question is graded out of 4 points (per part), like a homework problem.

To the main class page | the schedule page | problems page | my home page.

LaTeX: Mathematical Typesetting

LaTeX is a way to type ordinary characters and get attractive mathematics. (You can use it for plain text, too; I type letters with LaTeX.) You need a LaTeX compiler, which turns your typing into the result (usually a PDF). There's an online compiler called Overleaf, but I prefer to download a free compiler from the TeX User's Group. The simplest download page is https://www.tug.org/begin.html. (I like Texshop, which is contained in the TeXLive distribution, but there are other options.)

How do you learn what to type? Here are two sample files for download: a TeX source file ".tex" and the resulting ".pdf". Compare the source with the PDF to see how to do things like square roots, fractions, etc., etc.

Corrections to the Textbook

Page 27, Pascal's Triangle (at the top): There are two wrong numbers. Row 3 should be 1 3 3 1 (I call the top "row 0"). In row 8, the next-to-last number should be 8. (Thanks, Melody Chen.)
Ch. 3, Exercise 3(e) should say "if n is odd".
Ch. 3, Exercise 5 should say "x_k = x", not "x₁ = x".
On page 131, the definition of a projective plane should say B is a set of subsets of X (not of B).

Additions to the Textbook

Definitions and Notation

:= means "is defined to be".

[n] := {1, 2, ..., n} where n is a positive integer, and [0] := ∅. Examples: [1] = {1}, [2] = {1, 2}.

C(n, k) := the number of k-combinations (k-element subsets) of an n-element set. (n, k are nonnegative integers.) The important thing is the letters C, n, k. The book writes ⁿC_k. Another way is _nC_k. All are correct.

P(n, k) := the number of k-permutations (k-element ordered subsets) of an n-element set. (n, k are nonnegative integers.)
Also, P(n) := P(n, n).

Falling factorial: (n)_k := n(n−1)(n−2)···(n−[k−1]) (with k factors). (k is a nonnegative integer and n is any number, variable, etc.)
In particular, (n)₀ := 1, since the product of no factors is defined as 1.
Each (n)_k is a polynomial of degree k; so why n can be anything that can go into a polynomial, such as a negative number or a variable.

Binomial coefficient (n over k) := (n)_k/k!. (k must be a nonnegative integer.) Question. What do you get if n is a nonnegative integer and n < k?
This is the book's first definition in Eq. (3.2.1), but it is different from the book's second definition. In the second definition you cannot put any value for n other than a nonnegative integer and you can't put any value for k other than an integer in the range from 0 to n.

A group is a set G with a binary operation * that has nice rules of algebra. The rules are: (1) x*(y*z) = (x*y)*z (associativity); (2) ∃ special element e (or "1") ∈ G such that e*x = x = x*e for every x (identity element); (3) every element x has an inverse, x^-1, such that x*x^-1 = e = x^-1*x. We do not assume the commutative law; some groups are commutative and some are not.
Examples: (1) Z with operation +. (2) R \ 0 with operation ×. (3) R with operation +. (4) All nonsingular n × n real matrices with operation ×. (Not) Z \ 0 with operation × (why not?). (Also not) R with operation × (why not?).

Big O and little o notation: Given two functions f, g of the positive integers or reals with values in the positive integers or reals, we say

f = O(g) if there is some positive constant c such that f(x)/g(x) ≤ c for all sufficiently large x. We don't care what the best c is, only that some c exists. (Note that if c is a valid constant, so is any c' > c.)
f = o(g) if f(x)/g(x) → 0 as x → ∞.

The purpose of this notation is to compare the rates of growth of f and g as x → ∞.
For example, 5x² = O(x² - 18) (take c = 6, for example). Also, x² = o(x³) (and therefore x² = O(x³)), but x² ≠ O(x²/log x).

Fibonacci numbering: Our two books use different numbering.
- Cameron defines F₀ = F₁ = 1, then F₂ = 2, F₃ = 3, etc.
- Brualdi defines F₁ = F₂ = 1, then F₃ = 2, F₄ = 3, etc.
Use Brualdi's notation for problems in his book and use Cameron's notation for every other problem.
Finite fields have two standard notations: Cameron likes GF(q) and I like F_q. That is for prime powers q. For plain, ordinary prime numbers p, GF(p) = F_p = Z_p = [Cameron] Z/(p) (too many notations; don't blame me).

Terminology

Use the word unique correctly. In mathematics, "unique" means "only one". It never means "different". If you mean that, say "different" or "distinct". I deduct points for incorrect usage.
(In ordinary English "unique" basically means "unlike all others", which is similar to the mathematical meaning. However, it is often abused, as in "unique user" which really means "distinct user". A truly unique user is the only user.)
Equivalent and equal do not mean the same thing. They are not "equivalent", especially when we get to equivalence relations.

Theorems and Other Results

Theorem 1. P(n,k) = (n)_k, where n and k are any nonnegative integers.

Theorem 2. C(n,k) = (n)_k/k!, where n and k are any nonnegative integers.

The union version of PIE:
|A₁ ∪ A₂ ∪ ··· ∪ A_n| = ∑_i=1ⁿ |A_i| − ∑_{i,j}⊆[n] |A_i ∩ A_j| + ∑_{{i,j,k}⊆[n]} |A_i ∩ A_j ∩ A_k| − ···
= ∑_r=1ⁿ (−1)^r ∑_{I⊆[n],|I|=r} |∩_i∈I A_i|.
The difference from (5.1.1) is that we omit |X| and the signs are reversed.