×

# Combinatorics (1st math Thailand POSN 2014)

1.) Answer with factorial notations and simplify into numbers.

• 1.1) Find the coefficients of $$x^{5}$$ from the expansion of $$(2+x+x^{2})^{8}$$
• 1.2) There're 10 people, including A,B,C,D. If we set them arrange in the long bench, find the number of different ways are there, such that only 2 of A,B,C,D are sitting together.

2.) Prove these statements by combinatorial proof.

• 2.1) $$\displaystyle \sum\limits_{k=0}^{r} \dbinom{r}{k}^{2} = \dbinom{2r}{r}$$ for any natural number $$r$$.

• 2.2) $$\displaystyle \frac{(9n)!}{2^{5n}3^{n}}$$ is always integer for any natural number $$n$$.

3.) Throw 15 6-sided regular dice, find the number of different ways such that every 6 different sides are shown and no more than 3 same sides are shown.

4.) Let $$V(r,n)$$ be the number of ways of putting $$r$$ different objects into $$n$$ identical boxes such that each boxes must have at least $$k$$ objects Prove that

$V(r,n) = nV(r-1,n) + \dbinom{r-1}{r-k}V(r-k,n-1)$

for any natural number $$r,n,k$$ and $$r \geq nk$$.

5.) There was a rumour inside the group of 10 people. This rumour is spread by e-mail and continuously spread by following rules.

• First, there was only 1 people know about the rumour called rumour-er.
• Each e-mail can be either forwarded directly (exactly 1 people and can forward again) or people who receive copies (can be 0 people or any number of people, but cannot forward again)
• People who received the e-mail (by both ways) can know who sent the mail, and those are considered to be rumoured
• People who received by forwarding can only forward the mail once and only forward to people who are not rumoured.
• Rumour-er can send as many e-mails as he/she want.

How many ways are there if the e-mails are sent exactly 2 times, and how many ways if sent exactly 3 times?

This is the part of Thailand 1st round math POSN problems.

Note by Samuraiwarm Tsunayoshi
2 years, 3 months ago

Sort by:

3) You are looking for the number of solutions to

$$a + b + c + d + e + f = 15$$, subject to $$1 \leq a \leq 3$$, and similarly for all the other variables.

Hint: Use the substitution $$z = 3 - a$$. Staff · 2 years, 3 months ago

Wow, this is nice! Thank you ^_^ · 2 years, 3 months ago

2.) I use multiset to prove, but I forgot how to form a multiset. · 2 years, 3 months ago

$$M =\{ 4n\cdot a_{1}, 2n\cdot a_{2}, 2n\cdot a_{3}, 1n\cdot a_{4}\}$$ such that $$|M| = 9n$$.

Number of permutations = $$\displaystyle \frac{(9n)!}{(4!)^{n}(2!)^{n}(2!)^{n}(1!)^{n}} = \frac{(9n)!}{2^{5n}3^{n}}$$ which is always integer. Done!

I swear to goat that I haven't done this for years since the last year test. · 2 years, 3 months ago