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