help on abstract perms and combs (1 Viewer)

mathsbrain

Member
Joined
Jul 16, 2012
Messages
161
Gender
Male
HSC
N/A
Given 50 cards with the integers 1, 2, 3, ... 50 printed on them, how many ways are there to select 9 distinct cards, such that no two cards have consecutive numbers printed on them?
Detailed explanation appreciated! Thanks
 

aa180

Member
Joined
Sep 21, 2016
Messages
55
Location
Euclidean 3-space
Gender
Male
HSC
2012
Do you have the answer? I have a formula for the general case but I'm not fully sure that it is correct.
 

aa180

Member
Joined
Sep 21, 2016
Messages
55
Location
Euclidean 3-space
Gender
Male
HSC
2012
I think its 42C7 or something
Hm, I don't think that's quite right, but I could be wrong. Here's my formula for the general case (I worked it out as a probability):




The numerator should be the number of ways in which the desired event occurs, and the denominator is the total number of arrangements. Plugging in N = 50 and n = 9 should give an answer of 445891810, which is a fair bit larger than 42C7. Hopefully someone can verify which answer is the correct one (I can explain my formula if required).
 

Idkwhattoput

Member
Joined
Mar 14, 2018
Messages
93
Gender
Male
HSC
2019
Uni Grad
2024
The way it is to consider writing out the series of integers 1,2,3,4... Imagine placing a red counter over the numbers you select (part of the 9 cards chosen), and a blue counter over the others. Here the question is simplified to 'how many ways are there of arranging 9 blue counters and 41 red counters such that no two blue counters are next to eachother?'. This is a relatively simple question to which the answer is 42C9 = 445891810. I do not know if aa180's general formula is correct, but I think their answer for this specific question is.
 

aa180

Member
Joined
Sep 21, 2016
Messages
55
Location
Euclidean 3-space
Gender
Male
HSC
2012
The way it is to consider writing out the series of integers 1,2,3,4... Imagine placing a red counter over the numbers you select (part of the 9 cards chosen), and a blue counter over the others. Here the question is simplified to 'how many ways are there of arranging 9 blue counters and 41 red counters such that no two blue counters are next to eachother?'. This is a relatively simple question to which the answer is 42C9 = 445891810. I do not know if aa180's general formula is correct, but I think their answer for this specific question is.
After checking with Wolfram Alpha, I can confirm that my general formula is correct.
 

Idkwhattoput

Member
Joined
Mar 14, 2018
Messages
93
Gender
Male
HSC
2019
Uni Grad
2024
After checking with Wolfram Alpha, I can confirm that my general formula is correct.
There may be something I haven't considered, but that would mean your general formula can be simplified to (N-n+1)C(n)?
 

TheOnePheeph

Active Member
Joined
Dec 13, 2018
Messages
241
Gender
Male
HSC
2019
There may be something I haven't considered, but that would mean your general formula can be simplified to (N-n+1)C(n)?
Yes, and this formula can be derived quite easily using binary (which is exactly the same method you used to solve this question, but with red and blue counters instead of 1 and 0).








 
Last edited:

sharky564

Member
Joined
Jul 15, 2016
Messages
59
Location
Null
Gender
Male
HSC
2019
In general, the number of ways of choosing cards from consecutive cards such that there are at least cards between any pair of cards is , which isn't too difficult to prove using double-counting.
 

TheOnePheeph

Active Member
Joined
Dec 13, 2018
Messages
241
Gender
Male
HSC
2019
In general, the number of ways of choosing cards from consecutive cards such that there are at least cards between any pair of cards is , which isn't too difficult to prove using double-counting.
Can this be derived in the same way with binary, but grouping them in such a way that you have c 0s behind each 1, then adding up all the individual cases, which are starting with 1, 01, 001 etc?
 

sharky564

Member
Joined
Jul 15, 2016
Messages
59
Location
Null
Gender
Male
HSC
2019
Can this be derived in the same way with binary, but grouping them in such a way that you have c 0s behind each 1, then adding up all the individual cases, which are starting with 1, 01, 001 etc?
See if it can :), you might have another approach to it.
 

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

Top