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

[Ekman]

Re: 2015 permutation X2 marathon

In how many ways can you climb 12 stairs by stepping 1 or 2 steps at a time?
(Not necessarily all 1's or all 2's)
Answer: 233

Via stars and bars method:

12C0 + 11C1 + 10C2 + 9C3 + 8C4 + 7C5 + 6C6 = 233

 

[braintic]

Re: 2015 permutation X2 marathon

Via stars and bars method:

12C0 + 11C1 + 10C2 + 9C3 + 8C4 + 7C5 + 6C6 = 233

Without referring to nCr, nPr, factorials, or even simple multiplication, how else can this answer be generated?
(Think Robert Langdon)

[BTW, not sure what 'stars and bars' refers to, but you can get your calculation by simply counting "words" that can be formed from the right numbers of 1s and 2s.]

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

Without referring to nCr, nPr, factorials, or even simple multiplication, how else can this answer be generated?
(Think Robert Langdon)

[BTW, not sure what 'stars and bars' refers to, but you can get your calculation by simply counting "words" that can be formed from the right numbers of 1s and 2s.]

I dont get how any of you did this...
EDIT: i Pmed Ekman and he showed his working out and its what you said about counting words

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

NEW QUESTION!
How many ways can you arrange 5 letter words from : SLEEPY SENATE
answer : 11555

 

[Ekman]

Re: 2015 permutation X2 marathon

Without referring to nCr, nPr, factorials, or even simple multiplication, how else can this answer be generated?
(Think Robert Langdon)

[BTW, not sure what 'stars and bars' refers to, but you can get your calculation by simply counting "words" that can be formed from the right numbers of 1s and 2s.]

Well it turns out you do know what it means. I treated 1s as barriers (aka bars) and the 2s as objects (aka stars). This basically finds out the number of combinations of 'words' that can be formed.

 

[braintic]

Re: 2015 permutation X2 marathon

I dont get how any of you did this...
EDIT: i Pmed Ekman and he showed his working out and its what you said about counting words

So no-one can see the connection to Fibonacci numbers?

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

So no-one can see the connection to Fibonacci numbers?

wth the answers the 12th number of the fibonacci sequence....

 

[braintic]

Re: 2015 permutation X2 marathon

wth the answers the 12th number of the fibonacci sequence....

13th

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

13th

Excluding the first one of course can you explain

 

[braintic]

Re: 2015 permutation X2 marathon

Excluding the first one of course can you explain

Let S(n) be the number of ways of climbing n steps.

The first move is either 1 step or 2 steps.
If it is 1 step, there are S(n-1) ways of climbing the remaining n-1 steps.
If it is 2 steps, there are S(n-2) ways of climbing the remaining n-2 steps.
So S(n) = S(n-1) + S(n-2), for n>2
This is the definition of the Fibonacci series.
The base cases S(1) and S(2) must be actually counted ... S(1) = 1, S(2) = 2.
These are the 2nd & 3rd terms of the Fibonacci series.

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

Let S(n) be the number of ways of climbing n steps.

The first move is either 1 step or 2 steps.
If it is 1 step, there are S(n-1) ways of climbing the remaining n-1 steps.
If it is 2 steps, there are S(n-2) ways of climbing the remaining n-2 steps.
So S(n) = S(n-1) + S(n-2), for n>2
This is the definition of the Fibonacci series.
The base cases S(1) and S(2) must be actually counted ... S(1) = 1, S(2) = 2.
These are the 2nd & 3rd terms of the Fibonacci series.

Hmmm... why would you add them though?

 

[braintic]

Re: 2015 permutation X2 marathon

Hmmm... why would you add them though?

Because your initial move is 1 step OR 2 steps.

There are S(n-1) moves you can make if your first step is 1, and another S(n-2) moves you can make if your first step is 2.

 

[braintic]

Re: 2015 permutation X2 marathon

NEW QUESTION!
How many ways can you arrange 5 letter words from : SLEEPY SENATE
answer : 11555

Are you sure about your answer? I am getting 10 more.

 

[rand_althor]

Re: 2015 permutation X2 marathon

NEW QUESTION!
How many ways can you arrange 5 letter words from : SLEEPY SENATE
answer : 11555

Letters: A EEEE L N P SS T Y

Case 1: 5 unique letters - ALNPT
8P5 = 6720

Case 2: 3 unique letters, 2 identical letters - EELNP
(7C3*5!)/2! = 2100. Multiply by 2 as it can happen with EE or SS, so the total number of words is 4200.

Case 3: 2 unique letters, 3 identical letters - EEELN
(7C2*5!)/3! = 420

Case 4: 1 unique letter, 4 identical letters - EEEEL
(7C1*5!)/4! = 35

Case 5: 1 unique letter, 2 pairs of identical letters - AEESS
(6C1*5!)/2!2! = 180

Case 6: A pair and trio of identical letters - EEESS
5!/3!2! = 10

Total amount of words = 6720 + 4200 + 420 + 35 + 180 + 10 = 11565

 

[Drsoccerball]

Re: 2015 permutation X2 marathon

Forgot the last case my bad aahah

 

[shervos]

Re: 2015 permutation X2 marathon

It might be a good idea to number the questions

 

[braintic]

Re: 2015 permutation X2 marathon

[*]

Including the empty set, how many subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} do not contain any consecutive integers?

Answer: 377


(Since I am not going to count what question we are up to, perhaps we should mark new questions as I have - in the largest font)

 

[rand_althor]

Re: 2015 permutation X2 marathon

Including the empty set, how many subsets of {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} do not contain any consecutive integers?

What's the answer?

 

[InteGrand]

Re: 2015 permutation X2 marathon

What's the answer?

Fibonacci

 

[braintic]

Re: 2015 permutation X2 marathon

What's the answer?

Sorry - forgot. Edited now.