04-BS-16 · May 2013

Question 7 of 12: Permutations, Combinations, and Multiset Arrangements

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, May 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 7: Permutations, Combinations, and Multiset Arrangements (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Word STATEMENTS (10 letters: S×2, T×3, A×1, E×2, M×1, N×1). Equation $x_1+x_2+x_3+x_4=11$, $x_i\ge0$ integers.

Find. (a) Number of distinguishable arrangements: unrestricted; all T's together; no two T's together. (b) Number of non-negative integer solutions.

(a-i) Unrestricted arrangements. STATEMENTS has 10 letters with repeats S:2, T:3, A:1, E:2, M:1, N:1. The multiset-permutation formula gives $$\frac{10!}{2!\,3!\,2!} = \frac{3{,}628{,}800}{2\cdot6\cdot2} = \frac{3{,}628{,}800}{24} = \boxed{151{,}200.}$$
(a-ii) All three T's together. Glue the 3 T's into one block "TTT," leaving 8 units to arrange: S,S,A,E,E,M,N,[TTT] — with S:2 and E:2 still repeated: $$\frac{8!}{2!\,2!} = \frac{40{,}320}{4} = \boxed{10{,}080.}$$
(a-iii) No two T's adjacent. First arrange the 7 non-T letters (S,S,A,E,E,M,N): $\dfrac{7!}{2!\,2!}=\dfrac{5040}{4}=1260$ arrangements. Each such arrangement creates $7+1=8$ gaps (including both ends); choose 3 of these 8 gaps to drop one T each (T's identical, so order among chosen gaps doesn't matter): $\binom{8}{3}=56$. Multiplying, $$1260 \times 56 = \boxed{70{,}560.}$$
(b) Stars-and-bars. The number of non-negative integer solutions of $x_1+x_2+x_3+x_4=11$ is the number of ways to place 3 dividers among 11 stars: $$\binom{11+4-1}{4-1} = \binom{14}{3} = \boxed{364.}$$

Final results — Question 7
Part	Result
(a-i) Unrestricted	151,200
(a-ii) T's together	10,080
(a-iii) No two T's together	70,560
(b) $x_1+x_2+x_3+x_4=11$	$\binom{14}{3}=364$

Topic: Multiset permutations, the gap (slot) method for "no two adjacent," and stars-and-bars for integer compositions.

Key relations: Distinguishable arrangements of a multiset $=\dfrac{n!}{n_1!\,n_2!\cdots}$; "block" trick glues required-together items into one unit; "gap" trick places forbidden-adjacent identical items into $\binom{\text{gaps}}{\text{count}}$ slots; non-negative integer solutions of $x_1+\cdots+x_k=n$ is $\binom{n+k-1}{k-1}$.

Why this works: Gluing the T's into a single block converts "all T's together" into an ordinary multiset-arrangement problem on one fewer distinguishable repeated letter; conversely, arranging the OTHER letters first and inserting T's into non-adjacent gaps guarantees no two land next to each other by construction, and because the T's are identical, only which gaps are chosen matters (a combination, not a permutation) of gaps.

Common pitfall: Forgetting to divide by the OTHER repeated letters (S,E) after gluing the T-block; using $\binom{7}{3}$ (only interior gaps) instead of $\binom{8}{3}$ (including both end gaps) in the no-two-adjacent count.

Source: Rosen, Discrete Mathematics and Its Applications, §6.3-6.5 (permutations, combinations, permutations with repetition), §6.5 example (stars and bars).

← Question 6 Next: Question 8 →