Question

for the tutorial in week 5, let us discuss• additional exercise, ex. 6.5.1, 6.5.4, 6.5.12, 6.5.11, 6.5.14, 6.5.19, 6.5.32, 6.5.59.additional exercise. how many seating arrangements are there with six boys and six girls if the table is hexagonal with 2 seats on each side, out of which one must be occupied by a boy and the other one by a girl?ex. 6.5.11. how many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 21$, where $x_i$, $i = 1,2,3,4,5$, is a non-negative integer, such that(a) $x_1 \geq 1$?(b) $x_i \geq 2$ for $i = 1,2,3,4,5$?(c) $0 \leq x_1 \leq 10$?(d) $0 \leq x_1 \leq 3$ and $x_2 \geq 15$?ex. 6.5.14. how many solutions are there to the inequality$x_1 + x_2 + x_3 \leq 11$,where $x_1, x_2, x_3$ are non-negative integers?hint: introduce an auxiliary variable $x_4$ such that $x_1 + x_2 + x_3 + x_4 = 11$.ex. 6.5.19. how many positive integers strictly lesser than 1,000,000 have the sum of their digits equal to 19?ex. 6.5.1, 6.5.4, additional exercise.(a) in how many different ways can five elements be selected in order from a set with three elements when repetition is allowed?(b) how many ways are there to select five unordered elements from a set with three elements when repetition is allowed?(c) how many ways are there to assign three distinct jobs to five (of course distinct) employees if each employee can be given more than one job?

Explanation:

Additional Exercise (Seating Arrangements)

Step1: Fix side seat assignments

A hexagonal table has 6 sides. For each side, we can arrange the boy and girl in 2 ways (boy first then girl, or girl first then boy). The number of ways to assign gender positions per side is $2^6$.

Step2: Arrange 6 boys

We have 6 distinct boys to place in the 6 boy seats. The number of permutations is $6!$.

Step3: Arrange 6 girls

We have 6 distinct girls to place in the 6 girl seats. The number of permutations is $6!$.

Step4: Calculate total arrangements

Multiply the three results together.
<Expression>
Total = 2^6 \times 6! \times 6!
</Expression>

We use the stars and bars formula: the number of non-negative integer solutions to $y_1+y_2+...+y_k=n$ is $\binom{n+k-1}{k-1}$.

(a) Step1: Substitute $x_1'=x_1-1$

New equation: $x_1'+x_2+x_3+x_4+x_5=20$, all variables non-negative.
<Expression>
$\binom{20+5-1}{5-1}=\binom{24}{4}$
</Expression>

(b) Step1: Substitute $x_i'=x_i-2$

New equation: $x_1'+x_2'+x_3'+x_4'+x_5'=21-5\times2=11$, all variables non-negative.
<Expression>
$\binom{11+5-1}{5-1}=\binom{15}{4}$
</Expression>

(c) Step1: Calculate total solutions

Total solutions without restriction: $\binom{21+5-1}{5-1}=\binom{25}{4}$.

Step2: Subtract invalid solutions

Invalid solutions: $x_1\geq11$, substitute $x_1'=x_1-11$, equation becomes $x_1'+x_2+x_3+x_4+x_5=10$. Number of invalid solutions: $\binom{10+5-1}{5-1}=\binom{14}{4}$.
<Expression>
$\binom{25}{4}-\binom{14}{4}$
</Expression>

(d) Step1: Substitute $x_2'=x_2-15$

New equation: $x_1+x_2'+x_3+x_4+x_5=21-15=6$, with $0\leq x_1\leq3$.

Step2: Calculate valid solutions

Sum solutions for $x_1=0,1,2,3$: for each $x_1=k$, solve $x_2'+x_3+x_4+x_5=6-k$.
<Expression>
$\binom{6+4-1}{4-1}+\binom{5+4-1}{4-1}+\binom{4+4-1}{4-1}+\binom{3+4-1}{4-1}=\binom{9}{3}+\binom{8}{3}+\binom{7}{3}+\binom{6}{3}$
</Expression>

Step1: Introduce auxiliary variable

Let $x_4\geq0$, convert inequality to $x_1+x_2+x_3+x_4=11$.

Step2: Apply stars and bars

Use the formula for non-negative integer solutions.
<Expression>
$\binom{11+4-1}{4-1}=\binom{14}{3}$
</Expression>

Answer:

$5529600$

---

Ex. 6.5.11 (Non-negative integer solutions)