1

I am trying to construct combinations of sequences. Given n integers (to choose from), say 1 <= n <= k and the requirements to construct sequences of length m. The number of sequences is simply C(n, r) and I even have a program to display them all.

However, now I am trying to construct sequences where no adjacent numbers are only 1 digit apart, let's call it S. I can easily list them all with my program. For example. S(9,4):

1 3 5 7 
1 3 5 8 
1 3 5 9 
1 3 6 8 
1 3 6 9 
1 3 7 9 
1 4 6 8 
1 4 6 9 
1 4 7 9 
1 5 7 9 
2 4 6 8 
2 4 6 9 
2 4 7 9 
2 5 7 9 
3 5 7 9 
tot:15

I need to work out the "15" without listing them all.

So, to calculate S(n,m), I know that in terms of permutations, it simply is: n(n-2)(n-4)..(n-2m). However, that gives me permutations and not only combinations? A little help here please... How can I work this out?

Jaco Van Niekerk
  • 135
  • 2
    Hint: Subtract $1$ from the second number, $2$ from the third number and $3$ from the $4$th to get one of $C(9-3,4)=\binom{9-3}{4}$ subsets of ${1,2,\dots,6}=15$. – Thomas Andrews Jul 28 '14 at 15:34
  • 1
    And no, it is not $n(n-2)\dots(n-2m)$. It doesn't work that way. Once you've picked a first number, you might have removed $2$, or $3$ options from the list. For example, if you pick $6$ first, then you can't pick $5,6,7$ for your sequence... – Thomas Andrews Jul 28 '14 at 15:37
  • 2
    Another way to do this is to first arrange sticks in a row representing the numbers not being chosen. (In this example, there would be 5 sticks.) Then you have to choose the gaps created by the sticks to represent the numbers chosen. (In the example, this would be choosing 4 gaps out of the 6, which gives $\binom{6}{4}$ choices.) – user84413 Jul 28 '14 at 15:38
  • It works perfectly well, thanks. I was able to adapt my program to give me the k^th combination set as well. That's an algorithm all on its own! – Jaco Van Niekerk Jul 28 '14 at 16:10

0 Answers0