1. Define Group, Semigroup, Monoid, Subgroup, Abelian Group, Cyclic Group, and Lattice with properties. - Group: A set $G$ with a binary operation $\cdot$ is a group if it satisfies: 1. Closure: $\forall a,b \in G, a \cdot b \in G$ 2. Associativity: $\forall a,b,c \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)$ 3. Identity element: $\exists e \in G$ such that $\forall a \in G, e \cdot a = a \cdot e = a$ 4. Inverse element: $\forall a \in G, \exists a^{-1} \in G$ such that $a \cdot a^{-1} = a^{-1} \cdot a = e$ - Semigroup: A set $S$ with an associative binary operation. - Monoid: A semigroup with an identity element. - Subgroup: A subset $H$ of a group $G$ that itself forms a group under the operation of $G$. - Abelian Group: A group where the operation is commutative: $a \cdot b = b \cdot a$ for all $a,b$. - Cyclic Group: A group generated by a single element $g$, i.e., every element is $g^n$ for some integer $n$. - Lattice: A partially ordered set $(L, \leq)$ where every pair has a least upper bound (join) and greatest lower bound (meet). 2. Define Algebraic System and examples. - Algebraic system: A set with one or more operations defined on it. - Examples: $(\mathbb{Z}, +)$ integers under addition; $(\mathbb{R}, \cdot)$ real numbers under multiplication. - Binary operations combine two elements to produce another element in the set, fundamental in defining algebraic structures. 3. Define Boolean Algebra and properties. - Boolean Algebra: A set $B$ with operations $+$ (join), $\cdot$ (meet), and complement $\bar{a}$ satisfying axioms like commutativity, distributivity, identity, complements. - a) De Morgan's Laws: $$\overline{p + q} = \bar{p} \cdot \bar{q}$$ $$\overline{p \cdot q} = \bar{p} + \bar{q}$$ - b) For every $a \in B$, there exists a unique complement $\bar{a}$ such that: $$a + \bar{a} = 1, \quad a \cdot \bar{a} = 0$$ 4. Semigroup and Monoid examples. - $N$ with operation $a * y = \max(a,y)$: - Associative: Yes, max is associative. - Identity: 0 (if 0 in $N$) since $\max(a,0) = a$. - So $N$ is a monoid if 0 included. - $Z$ with operation $a * y = \min(a,y)$: - Associative: Yes. - Identity: No integer $e$ such that $\min(a,e) = a$ for all $a$. - So $Z$ is semigroup but not monoid. 5. Permutations with repetitions. - a) Formula: $$\frac{n!}{n_1! n_2! \cdots n_k!}$$ where $n$ total elements, $n_i$ repetitions. - b) "MISSISSIPPI" has 11 letters with counts: M=1, I=4, S=4, P=2. Number of arrangements: $$\frac{11!}{1!4!4!2!} = 34650$$ 6. Inclusion-Exclusion Principle. - a) For three sets $A,B,C$: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$$ - b) Given: $|A|=21, |B|=26, |C|=29, |A \cap B|=74, |C \cap D|=12, |B \cap C|=14, |A \cap B \cap C|=8$ Find $|C \text{ only}| = |C| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$ Since $|A \cap C|$ not given, assuming typo or missing data. 7. Number of integral solutions to $$x_1 + x_2 + x_3 + x_4 = 20$$ with bounds: $$1 \leq x_1 \leq 6, 1 \leq x_2 \leq 7, 1 \leq x_3 \leq 8, 1 \leq x_4 \leq 9$$ - Use substitution $y_i = x_i - 1$ to convert to nonnegative solutions with adjusted bounds. 8. Binomial and multinomial theorems. - a) Binomial theorem: $$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$ - Coefficient of $x^3 y^7$ in $(2x + 9y)^{10}$: $$\binom{10}{3} (2)^3 (9)^7 = 120 \times 8 \times 4782969 = 45916561920$$ - b) Multinomial theorem: $$(x_1 + x_2 + \cdots + x_m)^n = \sum \frac{n!}{k_1! k_2! \cdots k_m!} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$$ where $\sum k_i = n$. 9. Counting problems. - a) Number of ways to seat 10 people so a pair is not adjacent: Total permutations: $10!$ Treat pair as one unit: $9! \times 2!$ So ways with pair adjacent: $9! \times 2!$ Not adjacent ways: $$10! - 9! \times 2! = 3628800 - 725760 = 2903040$$ - b) Number of 10-digit binary numbers with exactly six 1's: $$\binom{10}{6} = 210$$ 10. Boolean algebra and lattice properties. - a) Elements 0 and 1 are unique identity elements for join and meet. For every $a \in B$, complement $\bar{a}$ satisfies: $$a + \bar{a} = 1, \quad a \cdot \bar{a} = 0$$ - b) Lattice properties: - Commutativity: $a \vee b = b \vee a$, $a \wedge b = b \wedge a$ - Associativity: $(a \vee b) \vee c = a \vee (b \vee c)$, similarly for $\wedge$ - Absorption: $a \vee (a \wedge b) = a$, $a \wedge (a \vee b) = a$ - c) $L = \{1,2,3,5,30\}$ with relation $R$ defined by divisibility. Since divisibility is a partial order and every pair has gcd and lcm in $L$, $L$ is a lattice.