HSC 2016 MX2 Combinatorics Marathon (archive) (4 Viewers)

Drsoccerball · Feb 10, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

davidgoes4wce said:
If all the letters of the word REARRANGE are arranged at random, what is the probability that the R's are together?

Ans: 1/12

I think this thread is an extension 2 combinations thread.

davidgoes4wce · Feb 10, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
I think this thread is an extension 2 combinations thread.

I got that question from the Maths Extension 2 Year 12, Trialmaths Enterprises text

Drsoccerball · Feb 10, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

davidgoes4wce said:
I got that question from the Maths Extension 2 Year 12, Trialmaths Enterprises text

Doesn't matter this is clearly a 3U question level.

kawaiipotato · Feb 10, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

davidgoes4wce said:
If all the letters of the word REARRANGE are arranged at random, what is the probability that the R's are together?

Ans: 1/12

Satisfy the condition first (group the R's) so that they look like
RRREEAANG
Treat the Rs as one group and so there are 7 'groups'.
Arranging these groups, the amount of ways this is possible is
7!/(2!2!) (Dividing by 2! And 2! because there are two of As and Es)
The total possible ways of rearranging is equal to 9!/(3!*2!*2!)
Divide those to get the probability

Paradoxica · Feb 11, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

$$\noindent Consider a group of $n$ people where we are to select one captain and a team of $r$ people.$\\$By considering the team members first, determine the number of possible teams with $r$ people.$\\$By considering the captain first, determine the number of possible teams over all possible $r.\\$Hence, show that $\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\cdots+n\binom{n}{n}\equiv n2^{n-1}$

braintic · Feb 11, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

kawaiipotato said:
Satisfy the condition first (group the R's) so that they look like
RRREEAANG
Treat the Rs as one group and so there are 7 'groups'.
Arranging these groups, the amount of ways this is possible is
7!/(2!2!) (Dividing by 2! And 2! because there are two of As and Es)
The total possible ways of rearranging is equal to 9!/(3!*2!*2!)
Divide those to get the probability

We don't actually need to worry about the other letters at all. They aren't relevant to the problem.

The number of ways of choosing the positions for the Rs is 9C3.
The number of such positions satisfying the condition is 7 (123, 234, 345, ..., 789).

7 / 9C3 = 1/12

Drsoccerball · Feb 14, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
$$\noindent Consider a group of $n$ people where we are to select one captain and a team of $r$ people.$\\$By considering the team members first, determine the number of possible teams with $r$ people.$\\$By considering the captain first, determine the number of possible teams over all possible $r.\\$Hence, show that $\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+\cdots+n\binom{n}{n}\equiv n2^{n-1}$

$$ If team is selected first $ \binom{n}{r} \cdot \binom{n-r}{1}$

$$ If captain is selected first $ \binom{n}{1} \cdot \binom{n-1}{r}$

$Taking note that the first and second methods give exactly the same value$

$\binom{n}{0} \cdot \binom{n}{1} = \binom{n}{1}$

$\binom{n}{1} \cdot \binom{n-1}{1}= \binom{n}{1} \cdot \binom{n-1}{1}$

$\binom{n}{2} \cdot \binom{n-2}{1} = \binom{n}{1} \cdot \binom{n-1}{2}$
...
$\binom{n}{r} \cdot \binom{n}{n-r}= \binom{n}{1} \cdot \binom{n-1}{r}$
...
$\binom{n}{n} \cdot \binom{n}{0} = \binom{n}{1} \cdot \binom{n-1}{n-1}$

$By summing the LHS and RHS we get :$

$\binom{n}{1}(1+\binom{n-1}{1}+\binom{n-1}{2}+...+\binom{n-1}{n-1}) = \binom{n}{0} \cdot \binom{n}{1} + \binom{n}{1} \cdot \binom{n-1}{1}+...$

$LHS= n2^{n-1} $ Since $ n(1+x)^{n-1}= LHS $ When $ x=1$

$$ Also using the fact that $ \binom{n}{r}= \binom{n-r}{r}$

$\therefore n2^{n-1}= \binom{n}{1} + 2 \binom{n}{2} +3 \binom{n}{3} +...+n\binom{n}{n}$

braintic · Feb 14, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
$$ If team is selected first $ \binom{n}{r} \cdot \binom{n-r}{1}$

$$ If captain is selected first $ \binom{n}{1} \cdot \binom{n-1}{r}$

$Taking note that the first and second methods give exactly the same value$

$\binom{n}{0} \cdot \binom{n}{1} = \binom{n}{1}$

$\binom{n}{1} \cdot \binom{n-1}{1}= \binom{n}{1} \cdot \binom{n-1}{1}$

$\binom{n}{2} \cdot \binom{n-2}{1} = \binom{n}{1} \cdot \binom{n-1}{2}$
...
$\binom{n}{r} \cdot \binom{n}{n-r}= \binom{n}{1} \cdot \binom{n-1}{r}$
...
$\binom{n}{n} \cdot \binom{n}{0} = \binom{n}{1} \cdot \binom{n-1}{n-1}$

$By summing the LHS and RHS we get :$

$\binom{n}{1}(1+\binom{n-1}{1}+\binom{n-1}{2}+...+\binom{n-1}{n-1}) = \binom{n}{0} \cdot \binom{n}{1} + \binom{n}{1} \cdot \binom{n-1}{1}+...$

$LHS= n2^{n-1} $ Since $ n(1+x)^{n-1}= LHS $ When $ x=1$

$$ Also using the fact that $ \binom{n}{r}= \binom{n-r}{r}$

$\therefore n2^{n-1}= \binom{n}{1} + 2 \binom{n}{2} +3 \binom{n}{3} +...+n\binom{n}{n}$

You should be able to justify the 2^n without summing a series.

braintic · Feb 15, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

New question: Prove that:

$\sum_{r=0}^{n} \left[\binom{n}{r}\cdot \sum_{s=0}^{n-r}\binom{n-r}{s} 2^{n-r-s}\right] = 4^n$

braintic · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

No Takers?

Drsoccerball · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

braintic said:
No Takers?

We should leave this for new students.

Paradoxica · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Looks like a tedious double application of the binomial theorem. I'll pass, not in the mood for that kind of thing.

Drsoccerball · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
Looks like a tedious double application of the binomial theorem. I'll pass, not in the mood for that kind of thing.

It took me half a page.

Paradoxica · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
It took me half a page.

Which is exactly why I'll pass.

Binomial theorem is one of those things where you can't have neat 5 line proofs.

seanieg89 · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

It's not that tedious.

$4^n=(1+3)^n=\sum_{r=0}^n \binom{n}{r}3^{n-r}\\ \\ = \sum_{r=0}^n \binom{n}{r} (1+2)^{n-r}\\ \\ =\sum_{r=0}^n\left(\binom{n}{r}\sum_{s=0}^{n-r}\binom{n-r}{s}2^{n-r-s}\right)$

Drsoccerball · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

seanieg89 said:
It's not that tedious.

$4^n=(1+3)^n=\sum_{r=0}^n \binom{n}{r}3^{n-r}\\ \\ = \sum_{r=0}^n \binom{n}{r} (1+2)^{n-r}\\ \\ =\sum_{r=0}^n\left(\binom{n}{r}\sum_{s=0}^{n-r}\binom{n-r}{s}2^{n-r-s}\right)$

I never thought of doing it like that :O

InteGrand · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Drsoccerball said:
It took me half a page.

$\noindent In my opinion, much nicer to prove as a `story proof' (aka double counting proof or combinatorial proof).$

$\noindent Consider a group of $n$ people whom we wish to sort into four labelled teams $A, B, C, D$. On the one hand, this can be done in $4^n$ ways (four choices for each of the $n$ people). On the other hand, say we choose $r$ people to put into team $A$, done in $\binom{n}{r}$ ways, and we place the remaining $n-r$ people into teams $B, C, D$, done in $\alpha_{n-r}$ ways. Then $4^n = \sum _{r =0}^{n} \binom{n}{r} \alpha_{n-r}$ (summing over all possible $r$). But $\alpha_{n-r} = \sum _{s=0 }^{n-r} \binom{n-r}{s} 2^{(n-r)-s}$ (choose $s$ people to be in team $B$, then the remaining $(n-r)-s$ people go into either team $C$ or $D$, then sum over all possible $s$. Thus $4^n =\sum _{r=0 }^{n} \left[\binom{n}{r} \sum_{s=0}^{n-r} \binom{n-r}{s} 2^{n-r-s} \right]$.$

InteGrand · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

$\noindent \textbf{NEW QUESTIONS}$

$\noindent 1) Generalise the result in braintic's previous question.$

$\noindent 2) By considering a `story', come up with a combinatorial identity of your own.$

Paradoxica · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

InteGrand said:
$\noindent \textbf{NEW QUESTIONS}$

$\noindent 1) Generalise the result in braintic's previous question.$

$\noindent 2) By considering a `story', come up with a combinatorial identity of your own.$

In what way do you want us to generalise it? Number of people?

That second one is easy, but I'm saving it for a good time.

InteGrand · Feb 16, 2016

Re: HSC 2016 MX2 Combinatorics Marathon

Paradoxica said:
In what way do you want us to generalise it? Number of people?

Number of teams (in braintic's there were four).

HSC 2016 MX2 Combinatorics Marathon (archive) (4 Viewers)

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Well-Known Member

-insert title here-

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

-insert title here-

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 4)