1. Problem 1: Definitions, language concatenations and a counting problem from the exam paper. 1. (a) Definitions. 1.1. Concatenation is the operation that joins two strings by placing one after the other, and for languages $L_1$ and $L_2$ the concatenation is $L_1L_2=\{xy\mid x\in L_1,\;y\in L_2\}$.\n 1.2. Permutation of $n$ distinct objects is an ordered arrangement of all $n$ objects, and the number of permutations of $n$ objects taken $r$ at a time is given by $P(n,r)=\dfrac{n!}{(n-r)!}$.\n 1.3. Combination is a selection of objects where order does not matter, and the number of combinations of $n$ objects taken $r$ at a time is $\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$.\n 1. (b) Evaluate language expressions for $M_1=\{a,b\}$, $M_2=\{a^2,ab,b^2\}$ and $M_3=\{a^2,a^3,a^4\}$.\n 1.4. Formula used: $M_iM_j=\{xy\mid x\in M_i,\;y\in M_j\}$.\n 1.5. Compute $M_1M_2$.\n - Take each $x\in M_1$ and $y\in M_2$ and form $xy$.\n - With $x=a$ we get $a\cdot a^2=a^3$, $a\cdot ab=a^2b$, $a\cdot b^2=ab^2$.\n - With $x=b$ we get $b\cdot a^2=ba^2$, $b\cdot ab=bab$, $b\cdot b^2=b^3$.\n - Hence $M_1M_2=\{a^3,\;a^2b,\;ab^2,\;ba^2,\;bab,\;b^3\}$.\n 1.6. Compute $M_1M_3$.\n - With $x=a$ and $y\in M_3$ we get $a^3,\;a^4,\;a^5$.\n - With $x=b$ and $y\in M_3$ we get $ba^2,\;ba^3,\;ba^4$.\n - Hence $M_1M_3=\{a^3,\;a^4,\;a^5,\;ba^2,\;ba^3,\;ba^4\}$.\n 1.7. Compute $M_3M_1$.\n - For each $x\in M_3$ and $y\in M_1$ form $xy$.\n - We obtain $a^2a=a^3$, $a^2b=a^2b$, $a^3a=a^4$, $a^3b=a^3b$, $a^4a=a^5$, $a^4b=a^4b$.\n - Hence $M_3M_1=\{a^3,\;a^2b,\;a^4,\;a^3b,\;a^5,\;a^4b\}$.\n 1. (c) Counting students in tutorial group. 1.8. Problem statement restated: In a group of 30 students, 17 study Nursing Science, 15 study Medical Lab Science, and 11 study neither. Find only Nursing, only Medical Lab Science, and both.\n 1.9. Use inclusion-exclusion.\n - Let $N=17$ and $M=15$.\n - Students in at least one of the two courses is $30-11=19$.\n - Inclusion-exclusion: $|N\cup M|=|N|+|M|-|N\cap M|$.\n - So $19=17+15-|N\cap M|$, hence $|N\cap M|=17+15-19=13$.\n 1.10. Therefore only Nursing $=17-13=4$.\n 1.11. Only Medical Lab Science $=15-13=2$.\n 1.12. Both Nursing and Medical Lab Science $=13$.\n 2. Problem 2: Venn-Euler sets, finite state automaton and alphabets. 2. (a) Venn-Euler explanation and set difference computations for $A=\{1,2,3,4\}$, $B=\{2,4,6,8\}$, $C=\{3,4,5,6\}$.\n 2.1. A Venn-Euler diagram is a visual representation of sets and their logical relations using overlapping regions to show intersections and set differences.\n 2.2. Formula used for set difference: $X- Y=\{x\in X\mid x\notin Y\}$.\n 2.3. Compute $A-B$.\n - $A=\{1,2,3,4\}$ and $B$ contains $2,4$.\n - So $A-B=\{1,3\}$.\n 2.4. Compute $C-A$.\n - $C=\{3,4,5,6\}$ and $A$ contains $3,4$.\n - So $C-A=\{5,6\}$.\n 2.5. Compute $B-C$.\n - $B=\{2,4,6,8\}$ and $C$ contains $4,6$.\n - So $B-C=\{2,8\}$.\n 2.6. Compute $B-A$.\n - $A$ contains $2,4$, so $B-A=\{6,8\}$.\n 2.7. Compute $B-B$.\n - Any set minus itself is the empty set, so $B-B=\emptyset$.\n 2. (b) Finite state automaton from given transition function.\n 2.8. Restate the data and correct a likely typo: states $S=\{s,t\}$, alphabet $A=\{a,b\}$, start state $s$, accept states $\{t\}$, and transitions given as $\delta(s,a)=s$, $\delta(s,b)=t$, $\delta(t,a)=s$, $\delta(t,b)=t$.\n 2.9. Transition table (rows states, columns input):\n - Row $s$: on $a$ go to $s$, on $b$ go to $t$.\n - Row $t$: on $a$ go to $s$, on $b$ go to $t$.\n 2.10. Define the FSA as the 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ with $Q=\{s,t\}$, $\Sigma=\{a,b\}$, $\delta$ as above, $q_0=s$, and $F=\{t\}$.\n 2.11. Two equivalent ways to specify the automaton are: as the 5-tuple $M=(Q,\Sigma,\delta,q_0,F)$ and as the transition diagram or the transition table displayed above.\n 2. (c) Five examples of an alphabet.\n 2.12. Example alphabets: $\{0,1\}$ for binary digits.\n 2.13. $\{a,b,c\}$ as a small letter alphabet.\n 2.14. $\{0,1,2,\dots,9\}$ as decimal digit alphabet.\n 2.15. $\{A,B,\dots,Z\}$ as uppercase letter alphabet.\n 2.16. $\{\text{space},\text{comma},\text{period}\}$ as a punctuation alphabet (finite symbol set).\n 3. Problem 3: Number theory and combinatorics. 3. (a) Prove by induction or modular arithmetic that $8^9-1$ is divisible by 7.\n 3.1. Key observation: $8\equiv 1\pmod{7}$.\n 3.2. Therefore $8^9\equiv 1^9\equiv 1\pmod{7}$.\n 3.3. Hence $8^9-1\equiv 0\pmod{7}$, so $7$ divides $8^9-1$.\n 3. (b) Football selection counting problem restated and solved.\n 3.4. Restate: From 15 players, where 6 can play center (C), 3 can keep goal (G), and none can do both, choose 11 players so that at least 4 centers and at least 2 goalkeepers are included.\n 3.5. Let Others = the remaining $15-6-3=6$ players.\n 3.6. We count by cases on number of goalkeepers $k_G$ which can be $2$ or $3$.\n 3.7. Case $k_G=2$.\n - Choose 2 goalkeepers: $\binom{3}{2}=3$.\n - Choose $k_C\ge 4$ centers from 6 and choose remaining players from Others so that total is 11.\n - If $k_C=4$ then Others chosen $=11-2-4=5$, ways $\binom{6}{4}\binom{6}{5}=\binom{6}{4}\binom{6}{5}$ and multiplied by 3 for goalkeepers gives $3\cdot\binom{6}{4}\cdot\binom{6}{5}=3\cdot 15\cdot 6=270$.\n - If $k_C=5$ then Others $=4$, ways $3\cdot\binom{6}{5}\cdot\binom{6}{4}=3\cdot 6\cdot 15=270$.\n - If $k_C=6$ then Others $=3$, ways $3\cdot\binom{6}{6}\cdot\binom{6}{3}=3\cdot 1\cdot 20=60$.\n - Total for $k_G=2$ is $270+270+60=600$.\n 3.8. Case $k_G=3$.\n - Choose 3 goalkeepers: $\binom{3}{3}=1$.\n - If $k_C=4$ then Others $=4$, ways $1\cdot\binom{6}{4}\cdot\binom{6}{4}=15\cdot 15=225$.\n - If $k_C=5$ then Others $=3$, ways $1\cdot\binom{6}{5}\cdot\binom{6}{3}=6\cdot 20=120$.\n - If $k_C=6$ then Others $=2$, ways $1\cdot\binom{6}{6}\cdot\binom{6}{2}=1\cdot 15=15$.\n - Total for $k_G=3$ is $225+120+15=360$.\n 3.9. Grand total number of ways $=600+360=960$.\n 3. (c) Properties of combinatorial analysis (listing and proofs of basic identities).\n 3.10. Property 1: Symmetry $\binom{n}{r}=\binom{n}{n-r}$.\n - Proof: $\dfrac{n!}{r!(n-r)!}=\dfrac{n!}{(n-r)!r!}$, so equality holds by algebraic symmetry.\n 3.11. Property 2: Pascal identity $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$.\n - Proof: Count ways to choose $r$ from $n$ by splitting on whether a fixed element is chosen or not.\n 3.12. Property 3: Binomial coefficient formula $\binom{n}{r}=\dfrac{n!}{r!(n-r)!}$ and $\binom{n}{0}=\binom{n}{n}=1$.\n 3.13. Property 4: Sum identity $\sum_{k=0}^n\binom{n}{k}=2^n$.\n - Proof: Expand $(1+1)^n$ by the binomial theorem.\n 4. Problem 4: Binomial theorem and expansions. 4. (a) State and prove the binomial theorem.\n 4.1. Statement: For any nonnegative integer $n$ and variables $x,y$ we have $$ (x+y)^n=\sum_{k=0}^n \binom{n}{k} x^{n-k}y^k. $$\n 4.2. Proof by induction on $n$.\n - Base $n=0$: $(x+y)^0=1$ and the sum $\sum_{k=0}^0\binom{0}{0}x^0y^0=1$.\n - Inductive step: assume true for $n$, then $(x+y)^{n+1}=(x+y)(x+y)^n=(x+y)\sum_{k=0}^n\binom{n}{k}x^{n-k}y^k$.\n - Multiply and regroup terms to obtain coefficients $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$ using Pascal identity, which yields the formula for $n+1$.\n - This completes the induction and proves the theorem.\n 4. (b) Use the binomial theorem to expand given expressions.\n 4.3. Expand $(2-3y)^5$.\n - Use formula $(x+y)^n=\sum_{k=0}^n\binom{n}{k} x^{n-k}y^k$ with $x=2$ and $y=-3y$ and $n=5$.\n - Compute term by term:\n k=0: $\binom{5}{0}2^5=32$.\n k=1: $\binom{5}{1}2^4(-3y)=5\cdot 16\cdot(-3y)=-240y$.\n k=2: $\binom{5}{2}2^3( -3y)^2=10\cdot 8\cdot 9y^2=720y^2$.\n k=3: $\binom{5}{3}2^2( -3y)^3=10\cdot 4\cdot(-27)y^3=-1080y^3$.\n k=4: $\binom{5}{4}2( -3y)^4=5\cdot 2\cdot 81y^4=810y^4$.\n k=5: $\binom{5}{5}( -3y)^5= -243y^5$.\n - Therefore $(2-3y)^5=32-240y+720y^2-1080y^3+810y^4-243y^5$.\n 4.4. Expand $(3-x)^4$.\n - Take $x_0=3$ and $y_0=-x$ with $n=4$.\n - k=0: $\binom{4}{0}3^4=81$.\n - k=1: $\binom{4}{1}3^3(-x)=4\cdot 27\cdot(-x)=-108x$.\n - k=2: $\binom{4}{2}3^2 x^2=6\cdot 9 x^2=54x^2$.\n - k=3: $\binom{4}{3}3(-x)^3=4\cdot 3\cdot(-x^3)=-12x^3$.\n - k=4: $\binom{4}{4}(-x)^4=x^4$.\n - Therefore $(3-x)^4=81-108x+54x^2-12x^3+x^4$.\n Final answers summary. - Question 1(b) results: $M_1M_2=\{a^3,a^2b,ab^2,ba^2,bab,b^3\}$.\n - $M_1M_3=\{a^3,a^4,a^5,ba^2,ba^3,ba^4\}$.\n - $M_3M_1=\{a^3,a^2b,a^4,a^3b,a^5,a^4b\}$.\n - Question 1(c): Only Nursing $=4$, Only Medical Lab $=2$, Both $=13$.\n - Question 2(a) differences: $A-B=\{1,3\}$, $C-A=\{5,6\}$, $B-C=\{2,8\}$, $B-A=\{6,8\}$, $B-B=\emptyset$.\n - Question 2(b) FSA: $Q=\{s,t\}$, $\Sigma=\{a,b\}$, $\delta$ as table above, $q_0=s$, $F=\{t\}$.\n - Question 3(a): $8^9-1$ is divisible by 7 because $8\equiv 1\pmod{7}$.\n - Question 3(b): Number of ways to choose the eleven with constraints $=960$.\n - Question 4(b) expansions: $(2-3y)^5=32-240y+720y^2-1080y^3+810y^4-243y^5$.\n - $(3-x)^4=81-108x+54x^2-12x^3+x^4$.\n