Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By Plato

Math Help - Number of k-subsets of an n-set, no pair of consecutive integers

  1. #1
    Newbie
    Joined
    Feb 2014
    From
    South Africa
    Posts
    8

    Number of k-subsets of an n-set, no pair of consecutive integers

    Let f(n,k) be the number of k-subsets of an n set {1,2,....,n} that does not contain a pair of consecutive integers. Show that f(n,k)= {n-k+1} \choose {k} I know we can think of it as a sequence of k 1's and n-k 0's with no pair of consecutive 1's, but I can't figure out why this would be the same as choosing k places from n-k+1. Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Number of k-subsets of an n-set, no pair of consecutive integers

    Quote Originally Posted by sawleha View Post
    Let f(n,k) be the number of k-subsets of an n set {1,2,....,n} that does not contain a pair of consecutive integers. Show that f(n,k)= {n-k+1} \choose {k} I know we can think of it as a sequence of k 1's and n-k 0's with no pair of consecutive 1's, but I can't figure out why this would be the same as choosing k places from n-k+1. Any help would be appreciated.
    First, it should be clear to you that $k \le \left\lceil {{n \over 2}} \right\rceil $ (that is the ceiling function).
    Think of a bit-string consisting of k ones and n-k zeros.
    Any rearrangement of that string represents a k-element subset of an n-set.
    How many rearrangements are there in which no two ones are consecutive?

    Well the zeros create n-k+1 places to place the ones, chose k of them.
    Thanks from sawleha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 16th 2011, 07:54 PM
  2. Find a pair of integers
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 27th 2009, 10:33 PM
  3. Replies: 3
    Last Post: July 30th 2009, 12:19 AM
  4. Replies: 2
    Last Post: November 8th 2008, 08:05 PM
  5. Replies: 4
    Last Post: February 24th 2008, 03:08 PM

Search Tags


/mathhelpforum @mathhelpforum