help on abstract perms and combs (1 Viewer)

[mathsbrain]

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]

Do you have the answer? I have a formula for the general case but I'm not fully sure that it is correct.

 

[mathsbrain]

Do you have the answer? I have a formula for the general case but I'm not fully sure that it is correct.

I think its 42C7 or something

 

[aa180]

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]

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]

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]

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)?

 

[aa180]

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, they are equivalent.

 

[TheOnePheeph]

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).

 

[sharky564]

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]

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]

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.