diff options
Diffstat (limited to 'tech-math/comb')
| -rw-r--r-- | tech-math/comb/hw1.tex | 146 | ||||
| -rw-r--r-- | tech-math/comb/hw3.tex | 70 | ||||
| -rw-r--r-- | tech-math/comb/hw4.tex | 36 | ||||
| -rw-r--r-- | tech-math/comb/hw5.tex | 61 | ||||
| -rw-r--r-- | tech-math/comb/hw6.tex | 33 | ||||
| -rw-r--r-- | tech-math/comb/ws1.tex | 31 | ||||
| -rw-r--r-- | tech-math/comb/ws2.tex | 74 | ||||
| -rw-r--r-- | tech-math/comb/ws3.tex | 64 | ||||
| -rw-r--r-- | tech-math/comb/ws4.tex | 52 | ||||
| -rw-r--r-- | tech-math/comb/ws5.tex | 28 | ||||
| -rw-r--r-- | tech-math/comb/ws6.tex | 29 |
11 files changed, 624 insertions, 0 deletions
diff --git a/tech-math/comb/hw1.tex b/tech-math/comb/hw1.tex new file mode 100644 index 0000000..6f94327 --- /dev/null +++ b/tech-math/comb/hw1.tex @@ -0,0 +1,146 @@ +\input ws-form.tex + +{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}} +Fall 2019\par\noindent +Homework 1\par\noindent +Due 09/03/2019} \smallskip \hrule \medskip +%#18 +\question{% +Q1 (\#18) - How many integer solutions are there to the inequality $$x_1 + x_2 + x_3 + x_4 + x_5 \leq 782$$ provided that $x_1, x_2 > 0$, $x_3 \geq 0$, and $x_4, x_5 \geq 10$? +}{ +This problem is equivalent to distributing 782 objects to 6 groups, each of which has identical restrictions on quantity (except the sixth, which follows $x_6 \geq 0$, in order to allow the integers to sum to less than or equal to $782$). The base case of all variables being strictly greater than 0 is ${781 \choose 5}$ because it can be modeled as choosing 5 distinct "gaps" of 781 gaps would split the 782 items into 6 groups. However, $x_3$ and $x_6$ can be equal to 0. Therefore, two fictitious objects are added to be chosen for group 3 and 6, which will be removed afterwards, making the enumeration ${783 \choose 5}$. The last irregular restriction of $x_4, x_5 \geq 10 \to x_4, x_5 > 9$ can be treated as distributing 18 total objects to the fourth and fifth groups before normal distribution. The final enumeration is ${765 \choose 5}$. +} \vfil +%#20 +\question{% +Q2 (\#20) - Give a combinatorial argument to prove the identity $k{n \choose k} = n{n-1 \choose k-1}$ +}{ +${n \choose k}$ is choosing k objects from a collection of n. ${1 \choose k} = k$ is choosing one object from a collection of k. Therefore, $k{n \choose k}$ is choosing k objects from n and one special object from the new collection. + +$n{n-1 \choose k-1}$ is, similarly, choosing a special object for one collection from $n$ objects and $k-1$ from a remaining $n-1$. The chosen group of one special object and $k-1$ ordinary objects from a group of $n$ is equivalent to the first group and thus equal in numeration (the expressions are equal). +}\vfil\eject +%#25 +\question{% +Q3 (\#25) - How many lattice paths from $(0,0)$ to $(17,12)$ are there that pass through $(7,6)$ and $(12,9)$? +}{ +Because a lattice path only travels rightward and upward, each conformant path has a one-to-one correspondence to a set of lattice paths---one of which is between $(0,0)$ and $(7,6)$; one is between $(7,6)$ and $(12,9)$; the last is between $(12,9)$ and $(17,12)$. + +Each lattice path's enumeration follows the form ${n+k \choose n}$ where $k$ is the $(n,k)$ is the difference in coordinates. By the basic enumeration theorem, the enumerations are multiplied---giving ${13 \choose 6}{8 \choose 3}{8 \choose 3}$. +} +\vfil +%#5 +\question{% +Q4 (\#5) - Let $S$ be the set of substrings on the alphabet $\{0,1,2,3\}$ that do not contain $12$ or $20$ as a substring. Give a recursion for the number $h(n)$ of strings in $S$ of length $n$. +}{ +$h(n) = 0$ for $n < 0$ because strings cannot have negative length. + +$h(0) = 1$ because there is only the empty string. + +$h(n) = 4h(n-1) - 2h(n-2) + h(n-3)$ for $n > 0$. +Starting with a string of length $n-1$, adding a character makes all potential strings of length $n$. But not all are valid. The number of invalid strings is determined by adding invalid substrings to the a smaller $n-2$ character long string. These have a one-to-one relation with invalid strings, but $h(n-1)$ has already ``caught some.'' Adding $120$ to a string of length $n-3$ will be removed from $h(n-1)$ because $12$ is caught, but it won't be removed from $h(n-2)$ because the $12$ hasn't appeared yet in its parsing. This gives the final value above. +} \vfil \eject +%#9 +\question{% +Q5 (\#9) - For each formula, give both a proof using the Principle of Mathematical Induction and a combinatorial proof. +$$1^2+2^2+3^2+\ldots+n^2={n(n+1)(2n+1) \over 6} \leqno(a)$$ +$${n \choose 0}2^0+{n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n = 3^n \leqno(b)$$ +}{ +{\bf Part A; Induction:} + +The statement is true for n=1. $1^2 = {1(1+1)(2(1)+1) \over 6} = {1\cdot2\cdot3 \over 6} = 1.$ + +If the statement is true for k-1, it is also true for k. +$$1^2+2^2+3^2+\ldots+(k-1)^2 = {(k-1)((k-1)+1)(2(k-1)+1) \over 6} = {(k-1)(k)(2k-1) \over 6}.$$ +$$1^2+2^2+3^2+\ldots+(k-1)^2+k^2 = {k(k-1)(2k-1) \over 6} + k^2 + = {k(k-1)(2k-1) + 6k^2 \over 6} + = {k(2k^2-3k+1) + 6k^2 \over 6}$$$$ + = {k(2k^2-3k+1+6k) \over 6} + = {k(2k^2+3k+1) \over 6} + = {k(2k+1)(k+1) \over 6}$$ + +{\bf Combinatorial:} + +%${n(n+1)(2n+1) \over 6} = {n+1 \choose 2} + 2{n+1 \choose 3}$ + +Let there be a collection of $n$ indistinct objects. $1 \leq k \leq n$ objects are chosen. Of those $k$ objects, $0 \leq k_b < k$ objects are blue and $0 \leq k_r < k$ objects are red. An object can be both, one, or neither. +There are $1^2+2^2+3^2+\ldots+n^2$ possible groups because for all values of $k$ between $1$ and $n$, $k_b$ and $k_r$ each have $k$ possible values (giving, by the Basic Principle of Enumeration, a count of $k \cdot k = k^2$). + +This can also be constructed as a collection of three positive integers and a boolean to order the lower two---if different. When all three integers are distinct, the count is ${n+1 \choose 3}$, or $2{n+1 \choose 3}$ with the boolean. If the lesser two are the same, the count is ${n+1 \choose 2}$ and the boolean is unimportant. The total number of groups is +$2{n+1 \choose 3}+{n+1 \choose 2} = {2(n+1)(n)(n-1) \over 6}+{(n+1)(n) \over 2} = {2(n+1)(n)(n-1) + 3(n+1)(n) \over 6} = {(2n-2)(n+1)(n) + 3(n+1)(n) \over 6} = {(2n-2+3)(n+1)(n) \over 6} = {(2n+1)(n+1)(n) \over 6}$ + +By double-counting the set of groups, $$1^2+2^2+3^2+\ldots+n^2={(2n+1)(n+1)(n) \over 6}$$ is true. +\medskip +{\bf Part B; Induction:} + +$${n \choose 0}2^0+{n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n = \sum_{i=0}^n{n \choose i}2^i$$ + +For $n=0$, the identity is true: ${0 \choose 0}2^0 = 1 = 1 = 3^0$. Assuming that it is true for $k$, it is also true for $k+1$. + +$$\sum_{i=0}^k{k \choose i}2^i = 3^k$$ +$$3\sum_{i=0}^k{k \choose i}2^i = 3(3^k)$$ +$$3^{k+1} = 2\sum_{i=0}^k{k \choose i}2^i + \sum_{i=0}^k{k \choose i}2^i += \sum_{i=0}^k{k \choose i}2^{i+1} + \sum_{i=0}^k{k \choose i}2^i += \sum_{i=1}^{k+1}{k \choose i-1}2^i + \sum_{i=0}^k{k \choose i}2^{i} $$$$ += \sum_{i=0}^{k+1}{k \choose i-1}2^i - {k \choose -1}2^0 + \sum_{i=0}^{k+1}{n \choose i}2^i - {k \choose k+1}2^{k+1} += \sum_{i=0}^{k+1}{k \choose i-1}2^i + \sum_{i=0}^{k+1}{k \choose i}2^i $$$$ += \sum_{i=0}^{k+1}\left({k \choose i-1} + {k \choose i}\right)2^i += \sum_{i=0}^{k+1}{k+1 \choose i}2^i. +$$ +By induction, the identity is true. +\medskip +{\bf Combinatorial:} + +By the binomial theorem, +$$3^n = (2+1)^n = {n \choose 0}2^0 1^n + {n \choose 1}2^1 1^{n-1} + {n \choose 2}2^2 1^{n-2} + \ldots + {n \choose n}2^n 1^0 $$$$ += {n \choose 0}2^0 + {n \choose 1}2^1 + {n \choose 2}2^2 + \ldots + {n \choose n}2^n.$$ + +The binomial theorem works because in the expansion of $(x+y)^n$, there are ${n \choose k}$ ways to multiply to $x^ky^{n-k}$. +} \vfil +%#10 +\question{% +Q6 (\#10) - Show that for all integers $n \geq 4$, $2^n < n!$. +}{ +For $n=4$, $2^n < n!$ holds: $2^4 = 16 < 24 = 4!$. + +Assuming that $2^n < n!$ is true for $k$, it is true for $k+1$. +$$2^{k+1} < (k+1)! \to 2\cdot 2^{k} < (k+1)k!$$ +\par$2 < k+1$, and $ab<cd$ if $a<c$, $b<d$, and $a,b,c,d>0$ (all of which are true). QED +} \vfil \eject +%#16 +\question{% +Q7 (\#16) - Give a proof by induction of the Binomial Theorem. How do you think it compares to the combinatorial argument given in Chapter 2? Binomial Theorem: {\it Let $x$ and $y$ be real numbers with $x$, $y$ and $x+y$ non-zero. Then for every non-negative integer $n$, $$(x+y)^n = \sum_{i=0}^{n} {n \choose i}x^{n-i}y^i.$$} +}{ +For $n = 0$, $(x+y)^n = \sum_{i=0}^{n}{n \choose i}x^{n-i}y^i \to 1 = {0 \choose 0}1\cdot1 = 1$. + +Assuming the statement to be true for $k$, it is also true for $k+1$: +$$(x + y)^k = \sum^k_{i=0}{k \choose i}x^{k-i}y^i.$$ +$$(x + y)^k(x+y) = (x+y)\sum^k_{i=0}{k \choose i}x^{k-i}y^i.$$ +$$(x + y)^{k+1} = x\sum^k_{i=0}{k \choose i}x^{k-i}y^i + y\sum^k_{i=0}{k \choose i}x^{k-i}y^i + = \sum^k_{i=0}{k \choose i}x^{k+1-i}y^i + \sum^k_{i=0}{k \choose i}x^{k-i}y^{i+1} $$$$ + = \sum^{k}_{i=0}{k \choose i}x^{k+1-i}y^{i} + \sum^{k+1}_{i=i}{k \choose i-1}x^{k+1-i}y^i $$$$ + = -{k \choose k+1}y^{k+1}+\sum^{k+1}_{i=0} {k \choose i}x^{k+1-i}y^{i} - {k \choose -1}x^k + \sum^{k+1}_{i=0}{k \choose i-1}x^{k+1-i}y^i $$$$ + = \sum^{k+1}_{i=0} {k \choose i}x^{k+1-i}y^i + \sum^{k+1}_{i=0} {k \choose i-1}x^{k+1-i}y^i + = \sum^{k+1}_{i=0} \left({k \choose i} + {k \choose i-1}\right)x^{k+1-i}y^i $$$$ + = \sum^{k+1}_{i=0} {k+1 \choose i}x^{k+1-i}y^i. +$$ + +The identity is true for $n \geq 0$. QED + +This is much more convoluted than the combinatoric proof, and it lacks many of the key components the combinatoric proof uses to give a good intuitive understanding. However, it maintains some of the ideas of how the binomial theorem can be constructed---especially clear with knowledge of the combinatoric proof. When a term is ``added'' to the multiplicands, a new term forms because it's the sum of $y\cdot x^iy^{n-1-i}$ and $x\cdot x^{i-1}y^{n-i}$---a more incremental/recursive process than the combinatoric proof's very explicit ``one-time calculation.'' +} \vfil +%#19 +\question{% +Q8 (\#19) - Suppose that $x \in {\bf R}$ and $x > -1$. Prove that for all integers $n \geq 0$, $(1+x)^n \geq 1 + nx$. +}{ +For $n=0$, $$(1+x)^0 \geq 1 + 0x \to 1 \geq 1.$$ + +Assuming it is true for $k$, it also is true for $k+1$: +$$(1+x)^k \geq 1 + kx.$$ +$$(1+x)^k(1+x) \geq (1 + kx)(1+x).$$ +$$(1+x)^{k+1} \geq 1 + (1+k)x + kx^2$$ + +$1 + (1+k)x + kx^2 \geq 1 + (1+k)x$ because $kx^2 > 0$, so +$$(1+x)^{k+1} \geq 1 + (1+k)x.$$ + +QED +} \vfil \eject +\bye diff --git a/tech-math/comb/hw3.tex b/tech-math/comb/hw3.tex new file mode 100644 index 0000000..8880ff8 --- /dev/null +++ b/tech-math/comb/hw3.tex @@ -0,0 +1,70 @@ +\input ws-form.tex +\def\pre#1{\par\leavevmode\llap{\hbox to .5in{\hfil #1 \hfil}}} +\def\prebullet{\pre{$\bullet$}} +\def\em{\it\bf} +\parindent=.5in +\question{% +Q1 (5.34) -- Below are three sequences of length 10. One of the sequences cannot be the degree sequence of any graph. Identify it and say why. For each of the other two, say why (if you have enough information) a connected graph with that degree sequence: +\prebullet is definitely hamiltonian/cannot be hamiltonian; +\prebullet is definitely eulerian/cannot be eulerian; +\prebullet is definitely a tree/cannot be a tree; and +\prebullet is definitely planar/cannot be planar. + +(If you do not have enough information to make a determination for a sequence without having specific graph(s) with that degree sequence, write “not enough information” for that property.) +\pre{a.} $(6,6,4,4,4,4,2,2,2,2)$ +\pre{b.} $(7,7,7,7,6,6,6,2,1,1)$ +\pre{c.} $(8,6,4,4,4,3,2,2,1,1)$ +}{ +Sequence $c$ cannot be a degree sequence because $\sum deg = 2q = 35$ where $q$ is the number of edges, which means there is a fractional number of edges, which is impossible. + +\pre{a.} There is not enough info for hamiltonian. Definitely eulerian, because the degree of all vertices is even. Cannot be a tree because there must be exactly $n-1$ edges, and the sum of degrees is greater than $2n-2$. Not enough info for planar because the number of edges, $18 \leq 3n - 6 = 24$, the restriction on planar graphs derived from Euler's formula. + +\pre{b.} Definitely not hamiltonian because there are two vertices of degree 1, which means there's no way to ``escape'' them to form a cycle. Definitely not eulerian because many vertices are not of even degree. Similar to $a$, $b$ cannot be a degree sequence of a tree because $25 \neq 10-1 = 9$. Definitely not planar by the same inequality used for $a$: $25 \not\leq 24$.} +\question{% +Q2 (5.39) -- Determine pr\"ufer$({\bf T})$ for the tree ${\bf T}$ in Figure 5.58 (not pictured). +}{ +$(9,3,9,5,9,4,5,14,1,6,5,1)$ +} +\question{% +Q3 (6.1) -- We say that a relation $R$ on a set $X$ is {\em symmetric} if $(x,y) \in R$ implies $(y,x) \in R$ for all $x, y \in X$. If $X = {a, b, c, d, e, f}$, how many symmetric relations are there on $X$? How many of these are reflexive? +}{ +Constructing symmetric relations as a choice of 2 elements from 7 (adding an artificial element to account for reflexive pairs), there are ${2 \choose 7} = 21$ symmetric relations on $X$. + +Further restricting the set to exclusively reflexive relations, reflexive pairs needn't be considered, so no artifical element need be added. Therefore, there are ${2 \choose 6} = 15$ symmetric, reflexive relations on $X$. +} +\question{% +\def\mod{\thinspace({\rm mod\thinspace} m)} +Q4 (6.2) -- A relation $R$ on a set $X$ is an {\em equivalence relation} if $R$ is reflexive, symmetric, and transitive. Fix an integer $m \geq 2$. Show that the relation defined on the set $\bf Z$ of integers by $aRb(a, b \in {\bf Z})$ if and only if $a \equiv b \thinspace({\rm mod\thinspace} m)$ is an equivalence relation. (Recall that $a \equiv b \thinspace({\rm mod \thinspace} m)$ means that when dividing $a$ by $m$ and $b$ by $m$ you get the same remainder.) +}{ +Assume that $a \equiv b \thinspace({\rm mod \thinspace} m)$ is not an equivalence relation---that is, it is either not reflexive, not symmetric, or not transitive. It is clearly transitive because if $a \equiv b \equiv c \mod$, then the remainders of $a$ and $b$ are the same and the remainders of $b$ and $c$ are the same, so $a$ and $c$ are the same. It is also clearly symmetric, because equality of remainders transfers to equivalency from mod. Third, it is reflexive because the remainder of $b \div m$ is equal to $b \div m$. By contradiction, this means that no relation $aRb$ on $\bf Z$ could exist if $a \equiv b \mod$ is not an equivalence relation. +} +\question{% +Q5 (6.7) -- Alice and Bob are considering posets $\bf P$ and $\bf Q$. They soon realize that $\bf Q$ is isomorphic to ${\bf P}^d$. After 10 minutes of work, they figure out that $\bf P$ has height 5 and width 3. Bob doesn't want to find the height and width of $\bf Q$, since he figures it will take (at least) another 10 minutes to answer these questions for $\bf Q$. Alice says Bob is crazy and that she already knows the height and width of $\bf Q$. Who's right and why? +}{ +If $\bf P^d$ is isomorphic to $\bf Q$, then there is a bijection $f: X \to Y$ between the base sets of $\bf P^d$ and $\bf Q$ such that all the same comparisons exist on relations $P^d$ and $Q$ for respective $v$ and $f(v)$. This means that any comparison or set of comparisons valid or invalid on $\bf P^d$ would be valid or invalid, respectively, on $\bf Q$. Therefore, a given chain or anti-chain will be retained and thus the heights and widths are the same of $\bf P^d$ and $\bf Q$. Note also that the heights and widths of $\bf P^d$ and $\bf P$ are the same because they have the same comparable objects, just opposite comparisons. (Alice is right) +} +\question{% +Q6 (6.8) -- For this exercise, considef the poset $\bf P$ in Figure 6.5 (not pictured). +\pre{a.} List the maximal elements of $\bf P$. +\pre{b.} List the minimal elements of $\bf P$. +\pre{c.} Find a maximal chain with two points in $\bf P$. +\pre{d.} Find a chain in $\bf P$ with three points that is {\it not} maximal. Say why your chain is not maximal. +\pre{e.} Find a maximal antichain with four points in $\bf P$. +}{ +\pre{a.} $(15, 8, 11, 2, 17, 3)$ +\pre{b.} $(16, 1, 5, 14)$ +\pre{c.} $(16, 8)$ +\pre{d.} $(15, 7, 13)$ is not maximal because, with transitivity, adding $1$ would form a larger chain. +\pre{e.} $(16, 1, 5, 14)$ +} +\question{% +Q7 (6.9) -- Find the height $h$ of the poset ${\bf P} = (X, P)$ shown below as well as a maximum chain and a partition of $X$ into $h$ antichains using the algorithm from this chapter. +}{ +Partition: $(23,12,22,18) \cup () \cup () +} +\question{% +Q8 (6.11) -- A restaurant chef has designed a new set of dishes for his menu. His set of dishes contains 10 main courses, and he will select a subset of them to place on the menu each night. To ensure variety of main courses for his patrons, he wants to guarantee that a night's menu is neither completely contained in nor completely contains another night's menu. What is the largest number of menus he can plan using his 10 main courses subject to this requirement? +}{ +This is equivalent to asking the size of the maximum anti-chain of the subset lattice ${\bf 2}^{10}$, which is ${10 \choose 5}=252$, by Sperner's Theorem. +} +\bye diff --git a/tech-math/comb/hw4.tex b/tech-math/comb/hw4.tex new file mode 100644 index 0000000..4c0413a --- /dev/null +++ b/tech-math/comb/hw4.tex @@ -0,0 +1,36 @@ +\noindent {\bf Q4)} + +C1: f, d, j, k + +C2: b, h, c, l, e, m, o + +C3: g, n, a, i + +Width = w = 3. + +Antichain: $\{f,b,g\}$ + +\noindent {\bf Q5)} + +1. If vertex A has vertex B in its down set, then vertex B has vertex A in its up set. Therefore, any vertex in the "difference" between two adjacent up sets in the "subset chain" outlined in the text must have a unique down set to any of the other "differences" and the same as every other vertex within the same "difference." If it didn't have the same down set as the other vertices, then a vertex which is in one down set but not the other could not have one of the original vertices in its up set (meaning they wouldn't be in the same difference, which is a contradiction). Similarly, if it had the same up set as a vertex within a different "difference," the vertex appearing "later" in the sequence should have appeared "earlier." The bijection establishes a similarity in size. + +2. For all $x \in X$, $i \leq j$ in R because the largest (least) up set it could have must be smaller than the up sets of anything in its down set. As described in part 1, the subset sequence means that if there are i-1 lesser down sets, the vertices behind those downsets must define at least i-1 lesser up sets, so $j \geq i$. + +3. If $x < y$ in P, x is in the down set of y and y is in the up set of x. All of the lesser (larger) up sets than x's also have lesser (smaller) down sets than y's. As a subposet, $|D|=|U|$ and with the addition of x's down set, k (number of y down sets) $>$ j (number of x up sets) in all cases. + +4. For every up and down set, at least one vertex has that up or down set. This means that every integer is used at least once as a left endpoint and as a right endpoint in the final interval representation. If the interval representation could be made on [d-1], this would force two previously comparable intervals to be incomparable (a right endpoint that was one away from a left endpoint is now on the same integer). It is also unique because none of the endpoints could be moved w/o similar dilemma. + +\noindent {\bf Q6)} + +a. If each of the linear orders are "flipped" so that if $a < b$, $a' > b'$, then the intersection of those linear orders is the dual of P. The number of linear orders defining an intersection stays the same. + +b. Let Q=(Y,Q) be a superset of P=(X,P) --- that is, $X \subset Y$ and $P = Q \cap (X \times X)$. Each linear order used to define Q can be stripped of elements in Y but not in X to create a set of linear orders defining P, so $dim(Q) \geq dim(P)$. + +c. When a point is removed, all of its comparisons are removed, so it can just be "taken out" of each linear order. Once removed, there are two possible cases. Either all remaining linear orders are non-identical or more than one are the same. In the first case, the dimension stays the same. In the second, it can only decrease by one because if there were more than 2 identical orders, one of the orders would've been originally non-minimal (if point 'a' is removed and 3+ orders are removed, the one with 'a' positioned between its other two locations is redundant because any comparisons it defines are covered by one of the other two) + +d. 3, for all. + +e. Dillworth's theorem states that there is a maximal partition of size width=w into chains. The order of each chain must be preserved in every linear order by definition, so each element can be referred to by its chain without loss of generality. A first "basic order" can be created, containing all comparisons. It takes at most w-1 orders to distinctly label the invalid comparisons in that list (moving vertices from one chain along the line until all valid comparisons still exist creates one order without invalidating any proper relations). + +f. A poset like the example on the left (complete bipartite except incomparability between opposites) with 2n vertices clearly has a width equal to n because all points from one independent set makes the maximum antichain. Its dimension is equal to n because it can only define one of the partner incomparabilities per linear order. In general, set 1 $<$ set 2, so a linear order has to look like "$2 < 4 ... 9 < 10 < 7 ...$" Within n linear orders, incomparability within independent sets can be easily defined. +\bye diff --git a/tech-math/comb/hw5.tex b/tech-math/comb/hw5.tex new file mode 100644 index 0000000..b20efb0 --- /dev/null +++ b/tech-math/comb/hw5.tex @@ -0,0 +1,61 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} +\noindent {\bf Q1)} %#2 + +\pre{a.} +$$\sum_{i=0}^\infty x^{i+1} = {x \over 1-x}$$ + +\pre{c.} +$$\sum_{i=0}^\infty 2^ix^i = {1 \over 1-2x}$$ + +\pre{d.} +$$\sum_{i=0}^\infty x^{i+4} = {x^4 \over 1-x}$$ + +\pre{f.} +$$(2+x)^8$$ %%BUG BUG BUG + +\pre{i.} +$$3+2x+4x^2+x^3\sum_{i=0}^\infty x^i = 3 + 2x + 4x^2 + {x^3 \over 1 - x}$$ + +\noindent {\bf Q2)} %#7 + +The generating function for $x_1$ is $1 \over 1-x$ because it is possible for all $n$. For $x_2$, $x^2 \over 1-x$ because there is no way of satisfying the restriction for $n<2$. For $x_3$, $1 \over 1-x^4$ as it is impossible for $n \not\equiv 0 ({\rm mod} 4)$ and $1+x+x^2+x^3$ for $x_4$ (because it cannot be all of the partition for $n$ more than $4$). One must also consider a fictional $x_5$ to account for the solutions which sum to less than $n$. This has the generating function $1 \over 1-x$. The combined possible number of solutions $c_n$ is the value of the coefficient for $x^n$ in their product. The product is $$x^2(1+x+x^2+x^3) \over (1-x)^3(1-x^4),$$ but by the fact that $$1+x+x^2+x^3={1-x^4 \over 1-x},$$ this is equal to $$x^2 \over (1-x)^4.$$ + +This, in closed form, becomes $${x^2 \over 6}\sum^\infty_{n=0} n(n-1)(n-2)x^{n-2} += \sum^\infty_{n=0} {n(n-1)(n-2) \over 6}x^n += \sum^\infty_{n=0} {n \choose 3}x^{n-1} += \sum^\infty_{n=-1} {n+1 \choose 3}x^n,$$ +giving a number of solutions $n+1 \choose 3$ + + + +\noindent {\bf Q3)} %#9 + +$$\sum^\infty_{n=0} {n \choose p}x^n$$ + +Note: in this problem and Q2, I used 0 and infinity as my bounds (mostly) because ${k \choose n}=0$ for $k<0$ and $k>n$. + +\noindent {\bf Q4)} %#21 + +\pre{a.} +$a_n = 7^n$ + +\pre{b.} +$$x^2e^{3x} += x^2\sum^\infty_{n=0} {(3x)^n \over n!} += x^2\sum^\infty_{n=0} {3^n x^n \over n!} += \sum^\infty_{n=0} {3^n x^{n+2} \over n!} += \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!} += \sum^\infty_{n=2} {3^{n-2} x^n \over {n-2}!} += \sum^\infty_{n=2} {3^{n-2}(n)(n-1) x^n \over n!}.$$ + +This shows $a_n = n(n-1)3^n$. + +\pre{c.} +$a_n = (-1)^n n!$ + +\pre{d.} +\def\mod#1{\thinspace(\thinspace{\rm mod} #1)} +$$e^{x^4} = 1 + x^4 + {x^8 \over 2!} \dots $$ +$$a_n = \left\{{ 0 : n\not\equiv 0 \mod{4} \atop {n! \over {n\over 4}!}: n\equiv 0\mod{4} }\right\}$$ + +\bye diff --git a/tech-math/comb/hw6.tex b/tech-math/comb/hw6.tex new file mode 100644 index 0000000..6d0ab8c --- /dev/null +++ b/tech-math/comb/hw6.tex @@ -0,0 +1,33 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\noindent {\bf Q1)} %#13:2 + +Bob is right because if the flow of the network were greater than eighteen, the flow into the sink (T) would have to be greater than 18, which is greater than the sum of the capacities of incoming edges from G, A, and H. + +\noindent {\bf Q2)} %#13:3 + +$(S,H,B,I,A,D,T)$ has a flow $\delta = 1$ because of the limiting factor BI. The update would change SH to a flow of 2, HB to 2, IB to 0, IA to 10, and AT to 4---setting $\hat\phi = \phi + 1 = 16.$ + +\noindent {\bf Q3)} %#13:6 + +54. + +\noindent {\bf Q4)} %#13:10 + +$\phi = 73.$ + +Cut: $$\left\{ {L = \{S,C,F,G,E\} \atop U = \{T,A,B,D\}}\right\}$$ + +\noindent {\bf Q5)} %#10:4 + +According to Theorem 7.12, $$lim_{n\to\infty} {d_n\over n!} = {1\over e}.$$ This means that the odds one of the permutations Zori chooses is a derangement is approximately ${1\over e}$, meaning that if Bob paid one dollar to pay, he should win with a slightly higher payout around $2.72$ (to make the game fair). + +\noindent {\bf Q6)} %#10:5 + +\pre{a.} Because the connections are independent, the graph generation can be simulated as only running on that 3-element subgraph. Because it is connected if all three possible edges exist, the odds that all three were selected to exist is ${1\over2}^3 = {1\over8} = P(E_S).$ + +\pre{b.} $P(E_S) = P(E_S|E_T)$ because $P(E_S) = {1\over 8}$ and $E_T$ being true guarantees nothing about any of the independent selections on $S$ (i.e. if their intersection is one vertex, $E_T$ doesn't show that any vertex pair on $S$ shares an edge). + +\pre{c.} Regardless of if connections form between 3 and 5 or 4 and 5, both conditions state that $\{2,3,4\}$ is fully connected. Thus, $23$ is an edge, and the odds that $S$ is connected are equal to the independent coin tosses respective to $12$ and $13$ (a $1\over4$ chance in either case). + +\bye diff --git a/tech-math/comb/ws1.tex b/tech-math/comb/ws1.tex new file mode 100644 index 0000000..afb8374 --- /dev/null +++ b/tech-math/comb/ws1.tex @@ -0,0 +1,31 @@ +\input ws-form.tex + +{\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 diff --git a/tech-math/comb/ws2.tex b/tech-math/comb/ws2.tex new file mode 100644 index 0000000..0251a1d --- /dev/null +++ b/tech-math/comb/ws2.tex @@ -0,0 +1,74 @@ +\input ws-form.tex +\input tikz.tex%have to draw graphs + +{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}} +Fall 2019\par\noindent +Worksheet 2\par\noindent +Due 09/10/2019} +\smallskip \hrule \medskip + +\question{ +Q1 - 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. +}{ +Each 3-element subset has 3 2-element subsets, so $m=3$. Treating the number of holes as $n$, we have greater than $mn+1=3\cdot 2+1=7$ pigeons, so there is no way to satisfy the condition. By the same calculus, a 6-element set cannot be organized in such a way to fulfil this condition. +}\vfil +\question{ +Q2 - 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, i.e., the family has $2^{n-1}$ subsets. Discuss how you can share your hunch with your friend in an effort to win the prize. +}{ +Treating the family of all subsets as a set $S$, $S$ has $2^n$ members because any item can either be in or not in the subset. +If my family of subsets were also treated as a set $P$, $P$ could be defined as $2^{10,000} \choose 2^{9,999}$ different families. +Communicating such information would be impossible unless another symbolic definition could be derived. +For example, $N = x \in S : 0 \notin x$ is easily communicable, as any set I have a hunch about would likely be, but most sets satisfying these solutions cannot---in general---be easily communicated. +}\vfil\eject +\question{ +Considering graph G in Figure 5.47, + +a) Let $V_1 = {g,j,c,h,e,f}$ and $E_1={ge,jg,ch,ef}$. Is $(V_1,E_1)$ a subgraph of $\bf G$? + +c) Let $V_3 = {a,d,c,h,b}$ and $E_3={ch,ac,ad,bc}$. Is $(V_3,E_3)$ an induced subgraph of $\bf G$? + +e) Draw the subgraph of $\bf G$ induced by {c,h,f,i,j} + +f) Draw a subgraph of $\bf G$ having vertex set ${e,f,b,c,h,j}$ that is {\it not} an induced subgraph. + +g) Draw a spanning subgraph of $\bf G$ with exactly 10 edges. +}{ +a) Yes because $V_1 \subset V_G$ and $E_1 \subset E_G$. + +c) No because $dh \in V_G$ but $dh \notin V_3$ and $d, h \in E_3, E_G$ + +e) \tikzpicture + \draw (2,0) -- (1,0) -- (0,0) -- (0, 1); %ifhc + \node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {i}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {f}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {h}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (3,1) {j}; + \endtikzpicture + +f) \tikzpicture + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {c}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {h}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {f}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,1) {e}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {b}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {j}; + \endtikzpicture + +g) \tikzpicture + %abcdghij + \draw (0,0) -- (0,1) -- (0,2) -- (1,2) -- (3,2) -- (0,1);%bchdac + \draw (1.75,3) -- (3,2) -- (1,5) -- (0,2);%gaih + \draw (1.75,3) -- (0.75,3) -- (1,2);%gjd + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {b}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {h}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,2) {d}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (3,2) {a}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1.75,3) {g}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,5) {i}; + \node[draw,circle,inner sep=0.1cm,fill=white] () at (0.75,3) {j}; + \endtikzpicture +} + +\bye diff --git a/tech-math/comb/ws3.tex b/tech-math/comb/ws3.tex new file mode 100644 index 0000000..841c9a9 --- /dev/null +++ b/tech-math/comb/ws3.tex @@ -0,0 +1,64 @@ +\input ws-form.tex +\input tikz%graphs + +{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}} +Fall 2019\par\noindent +Worksheet 2\par\noindent +Due 09/10/2019} +\smallskip \hrule \medskip + +\def\G{{\bf G}} +\question{% +Q1 - (Chapter 5, Exercise 18) Find a proper $(t+1)$-coloring of the graph $\G_{t+1}$ in Mycielski's proof of Proposition 5.25. This establishes that $\chi(\G_{t+1})\leq t+1$. +}{ +$\G_{t+1}=(V,E)$ is constructed as a $t$-colorable graph $\G_t$, an independent graph $I$ where $|I|=|G_t|=n$, and a separate vertex $z$. For the distinct vertices $i_1,i_2,\dots,i_n \in I$, $\{i_k,z\} \in E$ and $\{i_k,g_{G_j}\} \in E$ if $\{G_{t_j},G_{t_i}\} \in E$, given a similar enumeration on $G$. + +Let $\phi:V\to C$ be a proper coloring where $C$ is a set of colors $|C|=t+1$. If $\phi(i_k)=\phi(G_{t_j})$ and $\phi(z)=c$ where $c \notin \phi(I)$, $\phi$ is a proper coloring of $G_{t+1}$ on $t+1$ colors. +} +\question{% +Q2 - (Chapter 5, Exercise 20) Construct and draw the graph $\G_5$ from Mycielski's proof of Proposition 5.25. +}{ +\tikzpicture + \node[draw,circle,inner sep=0.1cm,fill=white] (a) at (0,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (b) at (0,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (c) at (1,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (d) at (2,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (e) at (1,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (f) at (0,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (g) at (3,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (h) at (2,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (i) at (1,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (j) at (0,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (k) at (4,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (l) at (3,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (m) at (2,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (n) at (1,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (o) at (0,4) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (p) at (5,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (q) at (4,1) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (r) at (3,2) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (s) at (2,3) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (t) at (1,4) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (u) at (0,5) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (v) at (6,0) {}; + \node[draw,circle,inner sep=0.1cm,fill=white] (w) at (5,1) {}; + \draw (a) -- (b) -- (c) -- (d) -- (e) -- (a); + \draw (a) -- (f) -- (c); + \draw (b) -- (g) -- (d); + \draw (c) -- (h) -- (e); + \draw (d) -- (i) -- (a); + \draw (e) -- (j) -- (b); + \draw (f) -- (k); \draw (g) -- (k); \draw (h) -- (k); \draw (i) -- (k); \draw (j) -- (k); %G_4 + \draw (a) +\endtikzpicture + Starting with $C_5$, I constructed $G_4$ and then $G_5$ outwards from the origin. + AAAAAAAHHHHHHH. I have decided to complete this on paper. +} +\question{% +Q3 - (Chapter 5, Exercise 31) Exhibit a planar drawing of an eulerian planar graph with 10 vertices and 21 edges. +}{ +} +\question{% +Q4 - (Chapter 5, Exercise 32) Show that every planar graph has a vertex that is incident to at most five edges. + }{} +\bye diff --git a/tech-math/comb/ws4.tex b/tech-math/comb/ws4.tex new file mode 100644 index 0000000..5a6ad0c --- /dev/null +++ b/tech-math/comb/ws4.tex @@ -0,0 +1,52 @@ +\input ws-form.tex + +{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}} +Fall 2019\par\noindent +Worksheet 2\par\noindent +Due 09/10/2019} +\smallskip \hrule \medskip + +\def\pre#1{\par\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} +\question{% +Q1 (7.1) -- A school has 147 third graders. The third grade teachers have planned a special treat for the last day of school and brought ice cream for their students. There are three flavors: mint chip, chocolate, and strawberry. Suppose that 60 students like (at least) mint chip, 103 like chocolate, 50 like strawberry, 30 like mint chip and strawberry, 40 like mint chip and chocolate, 25 like chocolate and strawberry, and 18 like all three flavors. How many students don't like any of the flavors available? +}{ +Students who don't like available flavors = $147 - 60 - 103 - 50 + 30 + 40 + 25 - 18 = 11$. +} +\question{% +Q2 (7.4) -- How many positive integers less than or equal to 100 are divisible by none of 2, 3, and 5? +}{ +$100 - ({100 \over 2} + {99 \over 3} + {100 \over 5}) + ({96 \over 2\cdot3} + {100 \over 2\cdot5} + {90 \over 3\cdot5}) - {90 \over 2\cdot3\cdot5} = 26$ +} +\question{% +Q3 (7.11) -- As in Example 7.4, let $X$ be the set of functions from $[n]$ to $[m]$ and let a function $f \in X$ satisfy property $P_i$ if there is no $j$ such that $f(j) = i$. + +\pre{a.} Let the function $f:[8]\to[7]$ be defined by the following table. Does $f$ satisfy property $P_2$? Why or why not? What about property $P_3$? List all the properties $P_i$ (with $i \leq 7$) satisfied by $f$. + +\medskip +\centerline{\vbox{\halign{& #\hfil \cr + $i$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr \noalign{\smallskip\hrule\smallskip} + $f(i)$ & 4 & 2 & 6 & 1 & 6 & 2 & 4 & 2 \cr +}}} + +\pre{b.} Is it possible to define a function $g: [8] \to [7]$ that satisfies no property $P_i$, $i\leq7$? If so, give an example. If not, explain why not. + +\pre{c.} Is it possible to define a function $h: [8] \to [9]$ that satisfies no property $P_i$, $i\leq9$? If so, give an example. If not, explain why not. +}{ +\pre{a.} No because $f(2)=f(6)=f(8)=2$. However, it does satisfy $P_3$ because for no $i\in [8]$ is $f(i)=3$. Overall, it satisfies properties $\{3,5,7\}$ but not $8$ because $8 \not\in [7]$. +\pre{b.} Yes. $\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(1,1)\}$ satisfies none of the properties. +\pre{c.} No. Any function of the nature of $h$ cannot satisfy no properties (i.e. there must be at least one i for which $f(j)\neq i$ for all $j\in[8]$). This is by the pigeonhole theorem: to assign [9] to [8], one must put two outputs into one input, contradicting the definition as a function. +} +\question{% +List all the derangements of $[4]$. (For brevity, you may write a permutation $\sigma$ as a string $\sigma(1)\sigma(2)\sigma(3)\sigma(4)$.) +}{ +2143, +2341, +2413, +3142, +3412, +3421, +4123, +4312, +4321 +} +\bye diff --git a/tech-math/comb/ws5.tex b/tech-math/comb/ws5.tex new file mode 100644 index 0000000..ff21fa2 --- /dev/null +++ b/tech-math/comb/ws5.tex @@ -0,0 +1,28 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} +\noindent {\bf Q1} %#1 + +\pre{a.} $(A^2-A-2)r(n) = 0$ + +\pre{b.} $(A^4-3A^3+A^2+A)r(n) = 0$ + +\pre{c.} $(A^3-5A+1)g(n) = 3^n$ + +\pre{d.} $(A^3-A^2+2A-1)h(n-3) = 0$ + +\pre{e.} $(A^5 - 4A^4 - A^2 - 3)r(n-5) = (-1)^n$ + +\pre{f.} $(A^2 - A - 1)b(n-2) = 2^{n+1} - n^2$ + +\noindent {\bf Q2)} %#3 + +Equivalent to $$(A^2-3A+2)g(n) = 0.$$ $$A^2-3A+2=(A-1)(A-2).$$ Thus, $g(n) = c_1 + 2^n$. + +\noindent {\bf Q3)} %#5 + +The Fibonacci formula is $a_{n+2} = a_{n+1} + a_n \to (A^2-A-1)a(n) = 0$. This has roots $1 + \sqrt{5} \over 2$ and $1 - \sqrt{5} \over 2$. Thus, its solution set is $$a(n) = c_1\left({1+\sqrt{5} \over 2}\right)^n + c_2\left({1+\sqrt{5} \over 2}\right)^n.$$ + +\noindent {\bf Q4)} %#7 + +This yields the solution set, by previously mentioned methods, $$f(n) = c_1 5^n + c_2 (-2)^n.$$ For this set, $$f(0)=2= c_1 + c_2$$ and $$f(1) = 10 = 5c_1 - 2c_2.$$ Solving as a system of equations, this gives $c_1 = 2$ and $c_2 = 0$. The solution is, therefore, $$f(n) = 2(5)^n$$. + +\bye diff --git a/tech-math/comb/ws6.tex b/tech-math/comb/ws6.tex new file mode 100644 index 0000000..5042920 --- /dev/null +++ b/tech-math/comb/ws6.tex @@ -0,0 +1,29 @@ +\def\pre#1{\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} + +\noindent {\bf Q1)} %#14:2 + +Considering a flow from Source $S$ which is connected to all members of $V_1$ and a similar sink $T$ with respect to $V_2$, this can be solved by the Ford-Fulkerson algorithm. + +Let $V_{kj}$ be the $j^{th}$ member, from left to right of $V_k$. The optimum matching is $$\{V_11\to V_22, V_12\to V_27, V_13\to V_25, V_14\to V_21, V_15\to V_26, V_17\to V_24\}$$ because the Ford-Fulkerson algorithm halts, and Hall's theorem holds: there is a grouping of vertices in $V_1$ with a fewer number of neighbors than in the group. + +\noindent {\bf Q2)} %#14:8 + +$w=3$. + +Antichain: $\{x_1,x_2,x_3\}$. + +Chain Partition: $\{x_3,x_4,x_5\}\cup\{x_6,x_1\}\cup\{x_2\}$. + +\noindent {\bf Q3)} %#15:2 + +\let\sp\thinspace +$$\pi_1\pi_2 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop + 3\sp 6\sp 4\sp 2\sp 1\sp 5}\right)$$ +$$\pi_2\pi_1 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6 \atop + 3\sp 1\sp 4\sp 5\sp 6\sp 2}\right)$$ +$$\pi_3\pi_4 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop + 1\sp 3\sp 8\sp 5\sp 7\sp 4\sp 6\sp 2}\right)$$ +$$\pi_4\pi_3 = \left({1\sp 2\sp 3\sp 4\sp 5\sp 6\sp 7\sp 8 \atop + 5\sp 4\sp 3\sp 6\sp 7\sp 8\sp 1\sp 2}\right)$$ + +\bye |