# help on abstract perms and combs (1 Viewer)

#### mathsbrain

##### Member
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
Do you have the answer? I have a formula for the general case but I'm not fully sure that it is correct.

#### mathsbrain

##### Member
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

##### Member
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):

$\bg_white \textbf{Conjecture:} \text{ Suppose that } N \text{ cards are each labelled with a distinct number from } 1 \text{ to } N, \text{ inclusive. If } n \text{ cards are drawn out at random, where } n \leq \frac{N-1}{2}, \text{ then the probability, } P_{n}, \text{ that no two cards contain consecutive numbers is given by:}$
$\bg_white P_{n} = \frac{\sum\limits_{k=0}^{N-2n+1}(N-2n+2-k)\cdot{^{n-2+k}C_{k}}}{^{N}C_{n}}$

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

##### Member
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

##### Active Member
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).

$\bg_white \text{Imagine you have N cards and want to select n such that no cards have consecutive integers. This is exactly the same as organizing a}$ $\bg_white \text{binary chain of length N with n 1s, where none of the 1s are next to each other. Here we have 2 cases:}$

$\bg_white \text{Case 1) 1 is the first number in the chain.}$
$\bg_white \text{Here we have N-1 places left, with n-1 groups of (01) and N-2n+1 0s to arrange. This can be done in} \binom{N-n}{n-1} \text{ways}$
$\bg_white \text{Case 2) 0 is the first number of the chain.}$
$\bg_white \text{Here we have n groups of (01) and N-2n 0s to arrange. This can be done in} \binom{N-n}{n} {ways}$
$\bg_white \text{Adding these two cases together, we get} \binom{N-n}{n-1} + \binom{N-n}{n}$
$\bg_white \text{This gives:} \binom{N-n+1}{n}$

Last edited:

#### sharky564

##### Member
In general, the number of ways of choosing $\bg_white a$ cards from $\bg_white b$ consecutive cards such that there are at least $\bg_white c$ cards between any pair of cards is $\bg_white \binom{b+c-ac}{a}$, which isn't too difficult to prove using double-counting.

#### TheOnePheeph

##### Active Member
In general, the number of ways of choosing $\bg_white a$ cards from $\bg_white b$ consecutive cards such that there are at least $\bg_white c$ cards between any pair of cards is $\bg_white \binom{b+c-ac}{a}$, 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
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.