2 files changed, 72 insertions, 0 deletions
diff --git a/tech-math/lect-notes.tex b/tech-math/lect-notes.tex
new file mode 100644
index 0000000..ea60dfa
--- /dev/null
+++ b/tech-math/lect-notes.tex
@@ -0,0 +1,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
diff --git a/tech-math/ws1.tex b/tech-math/ws1.tex
new file mode 100644
index 0000000..79624c8
--- /dev/null
+++ b/tech-math/ws1.tex
@@ -0,0 +1,40 @@
+\input color %allows colored answers
+\def\underline#1{\vbox{\hbox{#1}\vskip 1pt\hrule\vskip-1pt}}
+\long\def\question#1#2{%question and answer
+\par #1
+\bigskip
+
+{\color{red}%
+#2
+}\vfil
+}
+
+{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}}
+Fall 2019\par\noindent
+Worksheet 1\par\noindent
+Due 08/27/2019}
+\smallskip \hrule \medskip
+\question{
+Q1 - The Greek alphabet consists of 24 letters. How many five-character strings can be made using the Greek alphabet (ignoring the distinction between uppercase and lowercase)?
+}{
+$24^5$ because the number of strings which can exist is the product of the number of the individual choices ($m = m_1\cdot m_2\ldots m_{n-1}\cdot m_n$), and each of the 5 individual choices has 24 options from the 24 letters.
+}
+\question{
+Q2 - Assume that a license plate consists of 3 Latin alphabet letters followed by 4 numerals. How many license plates are there such that the numerals are distinct from one another and the last numeral is less than 3?
+
+}{
+By a similar method, the alphabet letters have $26^3$ possibilities. The numerals can be treated as choosing 2 distinct objects (for the last numeral), then ${9!}\over{6!}$ for the other 3, the options having been reduced by whichever chosen as the last numeral. This gives a final enumeration of $26^3\cdot 2 \cdot 504 = 17,716,608$.
+}\eject
+
+\question{
+Q3 - Twenty-three students compete in a math competition in which the top three students are recognized with trophies for first, second, and third place. How many different outcomes are there for the top three places?
+}{
+$P(23,3)$ because order matters and there are three people chosen from twenty-three.
+}
+
+\question{
+Q4 - Continuing the above problem---now assume that 3 additional students (distinct from the top 3) are awarded an honorable mention. How many different ways may non-placing students be awarded an honorable mention?
+}{
+Order doesn't matter, and there are now only 20 students to choose, from so there are ${20 \choose 3}$ ways to choose honorable mentions.
+}\eject
+\bye