Loading ...
Sorry, an error occurred while loading the content.

Re: set problem

Expand Messages
  • alpercay2001
    ... can you solve my problem?
    Message 1 of 5 , Mar 1, 2004
    • 0 Attachment
      --- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
      wrote:
      > Let A={1,2,...,n}.Can you find the number of r-element subset of A
      > that not included consecutive integers?
      can you solve my problem?
    • clooneman
      No. But, when r = 1, the number of required subsets equals n. When r = 2, the number of subsets equals [n!(n-1)!]/2 - (n-1). And so on. When r = n-1, the
      Message 2 of 5 , Mar 3, 2004
      • 0 Attachment
        No. But, when r = 1, the number of required subsets equals n. When
        r = 2, the number of subsets equals [n!(n-1)!]/2 - (n-1). And so
        on. When r = n-1, the number of required subsets equals 0, except
        in the cases of n=1, n=2 and n=3. The trick is to find the total
        number of subsets containing consecutive numbers, and then do the
        subtraction.

        --- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
        wrote:
        > --- In mathforfun@yahoogroups.com, "alpercay2001"
        <alpercay2001@y...>
        > wrote:
        > > Let A={1,2,...,n}.Can you find the number of r-element subset of
        A
        > > that not included consecutive integers?
        > can you solve my problem?
      • jwwarrenva
        We were asked to find the number of ways in which r integers can be selected from 1,2,..,n subject to the constraint that no two consecutive integers are
        Message 3 of 5 , Mar 10, 2004
        • 0 Attachment
          We were asked to find the number of ways in which r integers can be
          selected from 1,2,..,n subject to the constraint that no two
          consecutive integers are selected.
          The answer is C(n-r+1, r), the number of combinations of n-r+1
          objects taken r at a time.

          To show this, we start with a
          Lemma: The number of distinct solutions of x_1 + x_2 + ... + x_k = n,
          where x_1, ..., x_k are positive integers, is C(n-1, k-1).
          Proof:
          Using a marker you can erase, write n X's separated by vertical bars,
          like this: X|X|X|....|X, so there are n-1 vertical bars. Select k-1
          of the vertical bars and erase the rest, a selection that can be
          made in C(n-1, k-1) ways. The selected bars divide the Xs into k
          groups, each group containing at least one X. Working from left to
          right, let x_1 = the number of Xs in the first group, x_2 = the
          number of Xs in the second group, etc. The total number of Xs is n,
          so x_1 + x_2 + ... + x_k = n. Conversely, given a solution to the
          equation, we can generate a selection of k-1 of the vertical bars; so
          the number of solutions of the equation is C(n-1, k-1).

          Now back to the original problem. Write down the integers 1 to n from
          left to right and circle the r selected integers (with no two
          consecutive integers selected)—say the selected integers are i_1,
          i_2, ..., i_r. We proceed to count the non-circled integers. Let
          x_1 = the number of non-selected integers to the left of i_1 = i_1-1
          x_2 = the number of non-selected integers between i_1 and i_2 = i_2-
          i_1-1
          x_3 = the number of non-selected integers between i_3 and i_2 = i_3-
          i_2-1
          ...
          x_r = the number of non-selected integers between i_r and i_(r-1) =
          i_r-i_(r-1)-1
          x_r+1 = the number of non-selected integers to the right of x_r = n-
          x_r
          so we have
          x_1 >= 0, x_(r+1) >= 0, and x_i >= 1 for i = 2,3, ..., r. Since the
          x's account for all the non-selected integers,
          x_1 + x_2 + ... + x_(r+1) = n – r
          We are almost in position to apply the lemma, except that x_1 and x_
          (r+1) don't fit the conditions. So we substitute x_1 =
          y_1-1 and x_(r+1) = y_(r+1) –1, with the result
          y_1 + x_2 + .... + x_r + y_(r+1) = n – r + 2
          All the x's and y's in this equation are positive, so the lemma now
          applies, and the total possible number of solutions of the equation
          is C(n-r+2-1, r+1-1) = C(n-r+1, r). Given a solution of the
          equation, we can reverse the process and generate an acceptable
          selection; so the total number of acceptable selections is C(n-r+1,
          r).

          --- In mathforfun@yahoogroups.com, "alpercay2001" <alpercay2001@y...>
          wrote:
          > Let A={1,2,...,n}.Can you find the number of r-element subset of A
          > that not included consecutive integers?
        • derpified
          Here is another proof. Let B(n,r) be the number of r-subsets of {1,2,...,n} containing no two consecutive integers. Then B(n,0)=1 and B(n,1)=n. Also B(n,r) = B
          Message 4 of 5 , Mar 10, 2004
          • 0 Attachment
            Here is another proof.

            Let B(n,r) be the number of r-subsets of {1,2,...,n} containing no
            two consecutive integers. Then B(n,0)=1 and B(n,1)=n. Also B(n,r) = B
            (n-2,r-1) + B(n-1,r), since every r-subset of {1,2,...,n} either
            contains n, which says that n-1 is not in the subset and we have an
            (r-1)-subset of {1,2,...,n-2}, or doesn't contain n, which says that
            we have an r-subset of {1,2,...,n-1}. These conditions uniquely
            determine B(n,r), and since C(n-r+1,r) also satisfies the recursion,
            we must have that B(n,r)=C(n-r+1,r).


            --- In mathforfun@yahoogroups.com, jwwarrenva <no_reply@y...> wrote:
            > We were asked to find the number of ways in which r integers can be
            > selected from 1,2,..,n subject to the constraint that no two
            > consecutive integers are selected.
            > The answer is C(n-r+1, r), the number of combinations of n-r+1
            > objects taken r at a time.
            >
            > To show this, we start with a
            > Lemma: The number of distinct solutions of x_1 + x_2 + ... + x_k =
            n,
            > where x_1, ..., x_k are positive integers, is C(n-1, k-1).
            > Proof:
            > Using a marker you can erase, write n X's separated by vertical
            bars,
            > like this: X|X|X|....|X, so there are n-1 vertical bars. Select k-
            1
            > of the vertical bars and erase the rest, a selection that can be
            > made in C(n-1, k-1) ways. The selected bars divide the Xs into k
            > groups, each group containing at least one X. Working from left to
            > right, let x_1 = the number of Xs in the first group, x_2 = the
            > number of Xs in the second group, etc. The total number of Xs is
            n,
            > so x_1 + x_2 + ... + x_k = n. Conversely, given a solution to the
            > equation, we can generate a selection of k-1 of the vertical bars;
            so
            > the number of solutions of the equation is C(n-1, k-1).
            >
            > Now back to the original problem. Write down the integers 1 to n
            from
            > left to right and circle the r selected integers (with no two
            > consecutive integers selected)—say the selected integers are i_1,
            > i_2, ..., i_r. We proceed to count the non-circled integers. Let
            > x_1 = the number of non-selected integers to the left of i_1 = i_1-1
            > x_2 = the number of non-selected integers between i_1 and i_2 = i_2-
            > i_1-1
            > x_3 = the number of non-selected integers between i_3 and i_2 = i_3-
            > i_2-1
            > ...
            > x_r = the number of non-selected integers between i_r and i_(r-1) =
            > i_r-i_(r-1)-1
            > x_r+1 = the number of non-selected integers to the right of x_r = n-
            > x_r
            > so we have
            > x_1 >= 0, x_(r+1) >= 0, and x_i >= 1 for i = 2,3, ..., r. Since
            the
            > x's account for all the non-selected integers,
            > x_1 + x_2 + ... + x_(r+1) = n – r
            > We are almost in position to apply the lemma, except that x_1 and x_
            > (r+1) don't fit the conditions. So we substitute x_1 =
            > y_1-1 and x_(r+1) = y_(r+1) –1, with the result
            > y_1 + x_2 + .... + x_r + y_(r+1) = n – r + 2
            > All the x's and y's in this equation are positive, so the lemma now
            > applies, and the total possible number of solutions of the equation
            > is C(n-r+2-1, r+1-1) = C(n-r+1, r). Given a solution of the
            > equation, we can reverse the process and generate an acceptable
            > selection; so the total number of acceptable selections is C(n-r+1,
            > r).
            >
            > --- In mathforfun@yahoogroups.com, "alpercay2001"
            <alpercay2001@y...>
            > wrote:
            > > Let A={1,2,...,n}.Can you find the number of r-element subset of
            A
            > > that not included consecutive integers?
          Your message has been successfully submitted and would be delivered to recipients shortly.