1. Let $\Sigma = \{0, \, 1\}$ and $A = \{0, \, 01, \, 11\} \subseteq \Sigma^*.$ For $n \geq 1,$ let $a_n$ count the number of strings in $A^*$ of length $n.$ Find and solve a recurrence relation for $a_n.$ (10%)

2. Let $A = \{a, \, b, \, c, \, d, \, e\},$

(a) How many closed binary operations $f$ on $A$ satisfy $f(a, \, b) \neq c?$
(b) How many closed binary operations $f$ on $A$ have an identity and $f(a, \, b) = c?$
(c) How many $f$ in (b) are commutative?
(d) Determine the number of relations on $A$ that are reflexive and symmetric but not transitive.
(e) Determine the number of equivalence relations where $b \in [e].$
(Note: Values of Stirling number of the second kind: S(4,2)=7, S(4,3)=6, S(5,2)=15, S(5,3)=25) (20%)

3. (a) Find the number of permutations of 0, 1, 2, 3, …, 8 in which none of the patterns ‘1234’, ’76’, ’23’, ’81’ occurs. (b) How many three-element subsets of $S = \{1, \, 2,…, \, 10\}$ contains no consecutive integers? (20%)

(a) $9! – (3 \times 8!) + (3 \times 7!) – 6! = 256320$
(b) $\binom{4+5-1}{5} = \binom{8}{5} = 56$

### 2 留言

1. #### 小q

請問第二題(e) 的15是怎麼算的?

• 文章作者的留言

#### mt

這題等價關係個數是用Stirling number算的喔～
S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1 + 7 + 6 + 1 = 15