HSC 2015 MX2 Permutations & Combinations Marathon (archive) (5 Viewers)

glittergal96 · Sep 6, 2015

Re: 2015 permutation X2 marathon

A recursive formula is easy enough.

Picture the n people as black beads, numbered 1 through n, and the n committees as white beads, numbered 1 through n.

How many ways can we create a finite collection of bracelets, where the beads on each bracelet alternate in colour, and each bracelet has at least four beads total?

Each way of doing this corresponds to a unique way of putting people into committees. (adjacency <=> committee membership).

Now if $T_n$ is the number of ways of doing this with n beads of each colour, we have:

$T_n=\sum_{k=2}^{n-2} \binom{n-1}{k-1}\binom{n}{k}B_kT_{n-k}+B_n$

where $B_n$ is the number of ways of making a single bracelet with n beads of each colour.

This formula comes from considering the size of the bracelet containing the alphabetically first person, choosing the other n-1 black beads and n white beads for this bracelet, forming a bracelet from these beads, and forming a finite collection of bracelets with the remaining n-k beads of each colour.

Of course, it is also possible that all beads are in a single bracelet, which is where the last term comes from.

Since $B_n=\frac{n!(n-1)!}{2}$ , our expression simplifies to:

$\boxed{T_n=\frac{n!(n-1)!}{2}\sum_{k=0}^{n-2}\frac{T_k}{(k!)^2} \quad (n\geq 2)}$

(We set $T_0=1,T_1=0$ by convention.)

braintic · Sep 6, 2015

Re: 2015 permutation X2 marathon

glittergal96 said:
A recursive formula is easy enough.

Picture the n people as black beads, numbered 1 through n, and the n committees as white beads, numbered 1 through n.

How many ways can we create a finite collection of bracelets, where the beads on each bracelet alternate in colour, and each bracelet has at least four beads total?

Each way of doing this corresponds to a unique way of putting people into committees. (adjacency <=> committee membership).

Now if $T_n$ is the number of ways of doing this with n beads of each colour, we have:

$T_n=\sum_{k=2}^{n-2} \binom{n-1}{k-1}\binom{n}{k}B_kT_{n-k}+B_n$

where $B_n$ is the number of ways of making a single bracelet with n beads of each colour.

This formula comes from considering the size of the bracelet containing the alphabetically first person, choosing the other n-1 black beads and n white beads for this bracelet, forming a bracelet from these beads, and forming a finite collection of bracelets with the remaining n-k beads of each colour.

Of course, it is also possible that all beads are in a single bracelet, which is where the last term comes from.

Since $B_n=\frac{n!(n-1)!}{2}$ , our expression simplifies to:

$\boxed{T_n=\frac{n!(n-1)!}{2}\sum_{k=0}^{n-2}\frac{T_k}{(k!)^2} \quad (n\geq 2)}$

(We set $T_0=1,T_1=0$ by convention.)

I'm trying to digest this, but without much success.

What I DO understand is:
* the colouring of the beads
* the alternating colours
* "adjacency <=> committee membership"

What I don't understand:
* why are you considering bracelets and not just a ROW of beads?
* why "at least 4 beads"? Why four? And why "at least"? A why a "collection" of such bracelets.

I guess I only understand on a pair by pair basis, and am not seeing how these pairs group.

I haven't even looked at the counting yet - I don't get the setup.

glittergal96 · Sep 7, 2015

Re: 2015 permutation X2 marathon

braintic said:
What I don't understand:
* why are you considering bracelets and not just a ROW of beads?
* why "at least 4 beads"? Why four? And why "at least"? A why a "collection" of such bracelets.

I guess I only understand on a pair by pair basis, and am not seeing how these pairs group.

I haven't even looked at the counting yet - I don't get the setup.

Yeah, sorry about the wording and explanation being a bit terse.

Bracelets because this thing has a looped structure.

Say I am in two committees, choose one of them arbitrarily. This committee has one other member, this member is in one further committee, this next committee has ANOTHER member in it, etc etc. This process cannot continue indefinitely, and it ends when we loop back around to me.

This loop may contain ALL the people/committees, or it may only contain a finite subset, in which case we need to form more "bracelets" with the remaining "beads".

This should explain why we are looking at a collection of bracelets. The "at least four beads" condition comes from the fact that we need each committee to have two people in it and each person to be in two committees.

glittergal96 · Sep 7, 2015

Re: 2015 permutation X2 marathon

You might find it easier to think about if the committees are indistinguishable, in which case the bracelets are monochromatic and are just splitting the people up into groups separated by the the partnership relation a finite number of times, adjacency meaning partnership.

braintic · Sep 8, 2015

Re: 2015 permutation X2 marathon

glittergal96 said:
Yeah, sorry about the wording and explanation being a bit terse.

Bracelets because this thing has a looped structure.

Say I am in two committees, choose one of them arbitrarily. This committee has one other member, this member is in one further committee, this next committee has ANOTHER member in it, etc etc. This process cannot continue indefinitely, and it ends when we loop back around to me.

This loop may contain ALL the people/committees, or it may only contain a finite subset, in which case we need to form more "bracelets" with the remaining "beads".

This should explain why we are looking at a collection of bracelets. The "at least four beads" condition comes from the fact that we need each committee to have two people in it and each person to be in two committees.

I think I am going to have to give up on this one. I now understand what you just explained, but it is not helping me to see the resulting calculation.

RecklessRick · Sep 9, 2015

Re: 2015 permutation X2 marathon

You have 8 shirts which are grouped into pairs - so there are 4 distinct pairs of shirts, each pair consisting of 2 identical shirts. How many arrangements of these shirts are possible with no pairs together?

You can do it case by case, but is there a more eloquent way to do it?

InteGrand · Sep 9, 2015

Re: 2015 permutation X2 marathon

RecklessRick said:
You have 8 shirts which are grouped into pairs - so there are 4 distinct pairs of shirts, each pair consisting of 2 identical shirts. How many arrangements of these shirts are possible with no pairs together?

You can do it case by case, but is there a more eloquent way to do it?

Inclusion-exclusion principle

Drsoccerball · Sep 9, 2015

Re: 2015 permutation X2 marathon

RecklessRick said:
You have 8 shirts which are grouped into pairs - so there are 4 distinct pairs of shirts, each pair consisting of 2 identical shirts. How many arrangements of these shirts are possible with no pairs together?

You can do it case by case, but is there a more eloquent way to do it?

No restrictions : 8!
All pairs are together:4!2!2!2!2!
Such that no pairs are together : 8! -4!2!2!2!2!=39936

braintic · Sep 9, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
No restrictions : 8!
All pairs are together:4!2!2!2!2!
Such that no pairs are together : 8! -4!2!2!2!2!=39936

Ahhhhh - no.

For starters, no restrictions gives you 8! / (2!)^4

All pairs together is 4!.

And ... you do know that "all pairs together" and "no pairs together" are not opposites?

Drsoccerball · Sep 9, 2015

Re: 2015 permutation X2 marathon

braintic said:
Ahhhhh - no.

IS this that tricky thing you were talking about ?

braintic · Sep 9, 2015

Re: 2015 permutation X2 marathon

Drsoccerball said:
IS this that tricky thing you were talking about ?

I'm not sure which tricky thing I was talking about.
But I've edited my previous comment now.

braintic · Sep 9, 2015

Re: 2015 permutation X2 marathon

RecklessRick said:
but is there a more eloquent way to do it?

Are you sure you don't mean "elegant"?

Or do you want us to write the answer in Shakespearean language?

"Take thine shirts and partition into twos like loving ducks in a pond ....."

Ekman · Sep 9, 2015

Re: 2015 permutation X2 marathon

RecklessRick said:
You have 8 shirts which are grouped into pairs - so there are 4 distinct pairs of shirts, each pair consisting of 2 identical shirts. How many arrangements of these shirts are possible with no pairs together?

You can do it case by case, but is there a more eloquent way to do it?

Is it possible to use insertion method?

braintic · Sep 9, 2015

Re: 2015 permutation X2 marathon

Ekman said:
Is it possible to use insertion method?

Well the answer happens to be equal to 2^5 times 3^3, but I can't see a logical way of getting it that way.
Perhaps you could expand on what you mean.

Drsoccerball · Sep 9, 2015

Re: 2015 permutation X2 marathon

braintic said:
Are you sure you don't mean "elegant"?

Or do you want us to write the answer in Shakespearean language?

"Take thine shirts and partition into twos like loving ducks in a pond ....."

sig worthy

RecklessRick · Sep 12, 2015

Re: 2015 permutation X2 marathon

braintic said:
Are you sure you don't mean "elegant"?

Or do you want us to write the answer in Shakespearean language?

"Take thine shirts and partition into twos like loving ducks in a pond ....."

Hoh boy, yeah that must've been the word I was looking for.

I totally forgot I asked this.

What on earth is insertion method?

kawaiipotato · Sep 12, 2015

Re: 2015 permutation X2 marathon

RecklessRick said:
Hoh boy, yeah that must've been the word I was looking for.

I totally forgot I asked this.

What on earth is insertion method?

used for a question like how many ways can you arrange 8 boys and 4 girls so that no girl is next to each other
arrange boys first (looks like this): B B B B B B B B = 8!
then you "insert" the girls inbetween the spaces so that at least one B separates two G's
* B * B * B * B * B * B * B * B * (the stars show the possible spots for a girl to be inserted)
There are 9 spots possible and you choose 4 girls and arrange them = 9x8x7x6

RecklessRick · Sep 12, 2015

Re: 2015 permutation X2 marathon

kawaiipotato said:
used for a question like how many ways can you arrange 8 boys and 4 girls so that no girl is next to each other
arrange boys first (looks like this): B B B B B B B B = 8!
then you "insert" the girls inbetween the spaces so that at least one B separates two G's
* B * B * B * B * B * B * B * B * (the stars show the possible spots for a girl to be inserted)
There are 9 spots possible and you choose 4 girls and arrange them = 9x8x7x6

ah kk, I didn't know there was a proper name for that or anything.

The answer to drsoccerball then is no, I don't think you can use insertion method, because there are more ways to do it than simply ABABCDCD etc.

braintic · Sep 13, 2015

Re: 2015 permutation X2 marathon

*

There are n balls in a bag, numbered with consecutive integers 1 to n.

Show that the probability that if p balls are chosen that no chosen ball has number 1 to q is the same as the probability that if q balls are chosen that no chosen ball has number 1 to p.

Drsoccerball · Sep 13, 2015

Re: 2015 permutation X2 marathon

braintic said:
*

There are n balls in a bag, numbered with consecutive integers 1 to n.

Show that the probability that if p balls are chosen that no chosen ball has number 1 to q is the same as the probability that if q balls are chosen that no chosen ball has number 1 to p.

Probability 1 : $\frac{\binom{n-q}{p}}{\binom{n}{p}} = \frac{(n-q)!(n-p)!}{n!(n-p-q)!}$

Probability 2 : $\frac{\binom{n-p}{q}}{\binom{n}{q}} =\frac{(n-q)!(n-p)!}{n!(n-p-q)!}$

[]

HSC 2015 MX2 Permutations & Combinations Marathon (archive) (5 Viewers)

Active Member

Well-Known Member

Active Member

Active Member

Well-Known Member

Active Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Active Member

Well-Known Member

Active Member

Well-Known Member

Well-Known Member

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