1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Given positive interger N, now many non-decreasing sequences of length

  1. Jan 4, 2010 #1
    Given positive interger N, now many non-decreasing sequences of length N are there whose entries are less than N?
     
  2. jcsd
  3. Jan 4, 2010 #2
    Re: Sequence

    are the entries positive integers?
     
  4. Jan 4, 2010 #3
    Yes .
     
  5. Jan 4, 2010 #4
    Re: Sequence

    This isn't in the homework section so I'm assuming it isn't homework.

    Let A be the set of sequences of the type in the post.
    Let B be the set of sequences of N+1 non-negative integers with sum N-2.
    A and B are in bijection by associating a sequence [itex]a_1,a_2, \ldots ,a_N[/itex] of A to [itex]b_1,b_2,\ldots,b_{N+1}[/itex] defined by [itex]b_i = a_i - a_{i-1}[/itex] where we let [itex]a_0 = 1, a_{N+1}=N[/itex]. The inverse is given by associating a sequence [itex]b_1,b_2,\ldots,b_{N+1}[/itex] of B to [itex]a_1,\ldots,a_N[/itex] defined by [itex]a_{i+1} = a_{i}+b_{i+1}[/itex] where we let [itex]a_0 = 1[/itex].

    Thus we can just count B which has
    [tex]\binom{(N+1)+(N-2)-1}{(N+1)-1} = \binom{2N-2}{N}[/tex]
    elements.
     
  6. Jan 5, 2010 #5
    Re: Sequence

    Wow I would never have thought of that. Thanks. Unfortunately it grows too fast for my purposes.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook