1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
\input notes.tex
\newcount\lecturect%lecturect
\def\lecture#1{{\bf Lecture \the\lecturect: #1} \advance\lecturect by 1}
\lecturect=2
\lecture{Enumeration Basics}
Strings, words, arrays, and vectors are all the same object with respect to combinatorics. Mathematicians prefer "string." Strings are ordered sequences of characters from an alphabet. An alphabet is a set of allowed characters. "01" is an alphabet which forms binary/bit strings. "012" forms ternary strings. The English language is a 59 letter alphabet, including punctuation. These are typically best represented by concatenation of letters with minimal delimiters (spaces for example instead of comma and space).
The First Principle of Enumeration: if an ordered set of choices each have $m_i$ options for the $i^{\rm th}$ choice, the total number of combined choices is $m_0 \times m_1 \times m_2 \ldots m_{n-1} \times m_{n-2}$. This applies to choosing a set of strings from an alphabet as $m^n$ for an $n$ length string from an $m$ letter alphabet.
Permutations are a type of enumeration forbidding repetition of letters from an alphabet. The value of the permutation of a $m$-length string from an $n$-letter alphabet is $P(n,m) = m(m-1)(m-2)\ldots(m-n+1)$. This is equal to choosing $m$ objects from $n$ in a specific order.
Combinations are similar, but the order is unimportant. Using the same convention, $C(n,m) = {P(n,m)}\over{n!}$. The typical convention---graphic notation---is, however, $$\left({38}\atop{17}\right) = C(38,17) = 38\ {\rm choose}\ 17$$ (in contrast to inline notation).
Another convention is explicit definitions preferred to implicit definitions (using ``$\ldots$''). $1 + 2 + \ldots 6$ is worse than ``the sum of the first six integers'' is worse than ``$a_6$ where $a_0=0$ and $a_n=n+a_{n-1}$.'' Recursion is a very useful tool in combinatorics for making precise definitions (such as for factorials and permutations).
$\left({n}\atop{k}\right)$ represents the number of $k$-bit strings with $n$ 1's or choosing $n$ items from $k$ items. From the idea of choosing a bit string comes complements: choosing $n$ 0's is the same as choosing $m-n$ 1's.
Also derived from bit-strings is the complement identity: the enumeration for a bit string of length $k$ with $n$ 1's can be determined by an algorithm which chooses one position at a time. If the chosen bit is 1, the new enumeration is $\left(n\atop{k-1}\right)$; if it's 0, the new enumeration is $\left({n-1}\atop{k-1}\right)$. The total enumeration for the original is, therefore, $\left(n\atop{k-1}\right)\left({n-1}\atop{k-1}\right)$. This is where Pascal's triangle comes from: every point on the array is equal to $n$ choose $k$ where $n$ is the column and $k$ is the row---therefore, each can also be defined recursively as the sum of its parents.
Basic enumeration generalizes combinations. They are phrased as: ``Given a set of $m$ objects and $n$ cells, how many ways can the objects be distributed into the cells?'' Such problems must be constrained in certain ways: distinct and non-distinct objects (are the objects different from each other?), distinct and non-distinct cells (are the cells distinct?), and the allowance of empty cells (can a cell have 0 objects?) in the larger category of upper and lower bounds on the number of objects in a cell.
\lecture{Binomial Coefficients, Lattice Paths, and Recurrences}
The foundational enumeration problem of ``distributing $m$ identical objects into $n$ distinct cells such that no cell is empty'' is solved as $\left({m-1}\over{n-1}\right)$ because a line of the objects could be split by $n-1$ ``gaps'' between groups, chosen from $m-1$ (not $m$ so that neither end is chosen---which would give an empty cell).
That problem can expand to allowing empty objects by creating $n$ artificial objects and taking 1 away from every cell at the end. This allows that the final counts are 0, and the ``taking away'' doesn't have to be calculated. The formula becomes $\left({m+n-1}\atop{n-1}\right)$. \def\bin#1#2{\left({#1}\atop{#2}\right)}%binomial coefficient
A similar extension for a minimum number of objects is to ``set aside'' $n$ objects if the restriction of objects is $x>n$ where $x$ is the number of objects in a given cell. %%fix
\bye
|
