Results 1 to 5 of 5

Math Help - Choosing Non-Consecutive Integers from a list of N Integers

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    6

    Choosing Non-Consecutive Integers from a list of N Integers

    Prove that the number of ways choosing k integers from the integers 1,2,3...n, such that no two of the chosen integers are consecutive is:
    (n-k+1) C k [as in : (n-k+1)CHOOSE(k) ]
    with a suitable adjustment when n - k +1 < k
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by Niall2 View Post
    Prove that the number of ways choosing k integers from the integers 1,2,3...n, such that no two of the chosen integers are consecutive is:
    {{n-k+1} \choose {k}}
    Note that k \le \left\lfloor {\frac{{n + 1}}{2}} \right\rfloor ; from the set <br />
\left\{ {1,2,3,4,5,6,7,8,9} \right\} the subset \left\{ {3,5,7,9} \right\}
    can be represented by the string 001010101. If fact, any subset of four such that no two are consecutive can be represented by a 9-bit string of four 1ís and five zeros in which there are no adjacent 1ís.

    Thus, from the set \left\{ {1,2,3, \cdots ,n} \right\} we can use an n-bit string consisting of k 1ís and n-k 0ís, having no adjacent 1í to represent a subset of k elements containing no consecutive integers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2008
    Posts
    6
    Ah. I can see how you can use an n-bit string to represent the problem.

    Does that mean \begin{pmatrix}n-k+1 \\ k\end{pmatrix} is the number of ways to arrange 1's and 0's in an n-bit string so that no two 1's are consecutive?
    And if so, how can I prove that is the case?
    Last edited by Niall2; February 24th 2008 at 03:40 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by Niall2 View Post
    Ah. I can see how you can use an n-bit string to represent the problem. Does that mean \begin{pmatrix}n-k+1 \\ k\end{pmatrix} is the number of ways to arrange 1's and 0's in an n-bit string so that no two 1's are consecutive? And if so, how can I prove that is the case?
    EXACTLY!

    Letís take a particular case: 1111000000 (four ones and six zeros).
    We are going to use the zeros to separate the ones from each other: _0_0_0_0_0_0_. We have seven spaces into which we can put four ones.
    That can be done in \binom {7}{4} ways.
    Now you generalize.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2008
    Posts
    6
    Brilliant...
    EDIT: I now see completely

    Thanks a lot
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Consecutive Integers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 27th 2011, 06:40 PM
  2. Consecutive Integers
    Posted in the Algebra Forum
    Replies: 9
    Last Post: September 9th 2011, 05:30 AM
  3. consecutive odd integers
    Posted in the Algebra Forum
    Replies: 10
    Last Post: March 30th 2010, 11:01 AM
  4. Consecutive integers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 12th 2009, 07:24 PM
  5. n consecutive integers
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: October 22nd 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum