Home Page Forums Puzzles Non-Strictly Increasing Sequences

Tagged: 

  • Non-Strictly Increasing Sequences

     Puzzle Prime updated 1 week, 4 days ago 2 Members · 5 Posts
  • Puzzle Prime

    Administrator
    November 13, 2020 at 9:48 pm

    What is the number of non-strictly increasing sequences of M integer numbers between 1 and N?

  • Vivek

    Member
    November 16, 2020 at 2:12 pm

    Let xi be the number of times the number “i” appears in the sequence.

    So, We need to find the number of solutions for the equation

    x1+x2+x3+…+xN = M where xi>=0

    And That is ((M+N-1) choose (N-1)).

    • Puzzle Prime

      Administrator
      November 16, 2020 at 4:27 pm

      That’s true, but how do you calculate the number of solutions of x1+x2+… +xN=M?

    • Vivek

      Member
      November 17, 2020 at 3:29 am

      Usually the standard explanation goes like this :- Consider for example , X1+X2+X3=5. The solution can be considered equivalent to 5 *s separated by 2 |s . For example (1,2,2) corresponds to *|**|** . In the general case, M *s and N-1 |s and that gives ((M+N-1) choose (N-1))

    • Puzzle Prime

      Administrator
      November 17, 2020 at 2:48 pm

      That’s right:) Alternatively (or more like equivalently), you can add 1 to the second smallest element, 2 to the third smallest element, and so on, and reduce the problem to choosing M different numbers from 1 to N + M – 1.

Log in to reply.

Original Post
0 of 0 posts June 2018
Now