04-BS-16 · December 2013

Question 6 of 12: Counting — Multiset Permutations and Stars-and-Bars

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

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 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, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 6: Counting — Multiset Permutations and Stars-and-Bars (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. ONTARIO: 7 letters — O appears twice (letters O,N,T,A,R,I,O), the other five (N,T,A,R,I) once each; vowels present are O,O,A,I. Equation $x_1+x_2+x_3+x_4=15$.

Find. (a) Arrangement counts under three conditions. (b) Non-negative and "greater than one" integer-solution counts.

(a-i) Unrestricted arrangements. 7 letters with O repeated twice, all others distinct: $$\frac{7!}{2!} = \frac{5040}{2} = \boxed{2520.}$$
(a-ii) The two O's together. Glue "OO" into one block, leaving 6 fully distinct units (block, N, T, A, R, I): $$6! = \boxed{720.}$$
(a-iii) All vowels together. The vowels are O,O,A,I (4 letters, O repeated); glue them into one block. Internal arrangements of the block: $\frac{4!}{2!}=12$. The block plus the 3 remaining consonants (N,T,R) gives $4$ distinct units to arrange: $4!=24$. Total: $$12\times24 = \boxed{288.}$$
(b-a) Non-negative solutions (stars-and-bars). Place 3 dividers among 15 stars: $$\binom{15+4-1}{4-1} = \binom{18}{3} = \boxed{816.}$$
(b-b) All variables $>1$ (i.e. $\ge2$). Substitute $x_i=y_i+2$ with $y_i\ge0$; the equation becomes $y_1+y_2+y_3+y_4=15-4(2)=7$: $$\binom{7+4-1}{4-1} = \binom{10}{3} = \boxed{120.}$$

Final results — Question 6
Part	Result
(a-i) Unrestricted	2,520
(a-ii) O's together	720
(a-iii) Vowels together	288
(b-a) $x_i\ge0$	816
(b-b) $x_i>1$	120

Topic: Multiset permutations (the "glue the repeated/grouped letters" technique) and stars-and-bars for integer compositions.

Key relations: Multiset permutations of $n$ items with repeat counts $n_1,n_2,\dots$: $\frac{n!}{n_1!n_2!\cdots}$; "block" trick for togetherness constraints reduces $n$ items to $n-(\text{block size})+1$ units; stars-and-bars: non-negative solutions of $\sum x_i=k$ in $m$ variables $=\binom{k+m-1}{m-1}$; shift $x_i=y_i+c$ handles a uniform lower bound $x_i\ge c$.

Why this works: Gluing repeated/adjacent-required letters into one super-letter converts a "together" constraint into an ordinary unrestricted arrangement of fewer, more distinct units — the internal order of the glued block is then counted separately and multiplied in. The shift substitution in stars-and-bars converts a floor constraint into the standard non-negative form by absorbing the guaranteed minimum up front.

Common pitfall: Forgetting to divide by $2!$ for the internal O,O arrangement inside the "vowels together" block (undercounting) or over-diluting by treating the two O's as distinguishable (overcounting); using $\binom{k+m-1}{m-1}$ with the wrong total after the shift substitution.

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

← Question 5 Next: Question 7 →