wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Non-Decreasing Positive Integers
        
(Message started by: joh on Sep 6th, 2008, 6:26pm)
Title: Non-Decreasing Positive Integers
Post by joh on Sep 6th, 2008, 6:26pm
Find the number of 11-digit positive integers such that the digits from left to right are non-decreasing. (For example, 12345678999,55555555555,23345557889.)
Title: Re: Non-Decreasing Positive Integers
Post by Grimbal on Sep 7th, 2008, 4:17am
Hint:
[hide]That would be the same as the number of paths to go from (0,0) to (11,10) going only in directions (0,1) and (1,0).[/hide]
Solution:
[hide]That is C(21,10) = 352716.[/hide]

[edit]shown incorrect.  see below.[/edit]
Title: Re: Non-Decreasing Positive Integers
Post by rmsgrey on Sep 7th, 2008, 6:51am

on 09/07/08 at 04:17:21, Grimbal wrote:
Hint:
[hide]That would be the same as the number of paths to go from (0,0) to (11,10) going only in directions (0,1) and (1,0).[/hide]
Solution:
[hide]That is C(21,10) = 352716.[/hide]

Which would include the number 0123456789X?

[hide]You can make any number of the desired form by starting with n=1, and applying any permutation of {n++;}8{print n;}11 - C(19,8) possibilities[/hide]
Title: Re: Non-Decreasing Positive Integers
Post by 1337b4k4 on Sep 7th, 2008, 12:24pm
What we need is [hide]C(20,11)[/hide] to me since we don't have to start at 1.
Title: Re: Non-Decreasing Positive Integers
Post by cool_joh on Sep 7th, 2008, 1:38pm

on 09/07/08 at 04:17:21, Grimbal wrote:
Hint:
[hide]That would be the same as the number of paths to go from (0,0) to (11,10) going only in directions (0,1) and (1,0).[/hide]
Solution:
[hide]That is C(21,10) = 352716.[/hide]

I don't understand why does it end at (11,10), instead of (11,9), but I think some paths would correspond to numbers which starts with 0, which is not allowed.

So, actually the number of such integers is the same as the number of paths from (0,1) to (11,9), that is C(19,8), the same as rmsgrey's answer.
Title: Re: Non-Decreasing Positive Integers
Post by rmsgrey on Sep 7th, 2008, 1:40pm

on 09/07/08 at 12:24:17, 1337b4k4 wrote:
What we need is [hide]C(20,11)[/hide] to me since we don't have to start at 1.

Depends whether you count 00000000000 as an 11-digit number or not. If you're happy with leading zeros, then your answer is right; if not, mine is.

Of course, you can generalise to other bases as well - in binary, it's a very easy question (in other bases, it's still reasonably straightforward)
Title: Re: Non-Decreasing Positive Integers
Post by 1337b4k4 on Sep 7th, 2008, 2:15pm
I think we were both trying to count the same thing, I just made a silly error. (thinking there were 9 spaces btw. 1 and 9 instead of 8.)
Title: Re: Non-Decreasing Positive Integers
Post by Grimbal on Sep 8th, 2008, 1:07am

on 09/07/08 at 06:51:08, rmsgrey wrote:
Which would include the number 0123456789X?

Oops!  Right.  :-[

Replace 10 by 8 (for no loading zeroes) and I align with rmsgrey.
Title: Re: Non-Decreasing Positive Integers
Post by ecoist on Sep 8th, 2008, 2:23pm
Didn't understand Grimbal's solution, so I looked at the problem slightly differently.

[hide]Each non-decreasing positive integer corresponds to a unique distribution of 11 identical objects into 9 different boxes.  If such an integer contains three 7's, that corresponds to putting three objects in the 7th box.  Conversely, if, in a box distribution, box 5 contains 6 objects, that corresponds to a non-decreasing integer containing exactly six 5's.  As learned in a combinatorics course, the number of ways to distrubute 11 objects into 9 boxes is C(11+9-1,11)=C(19,11).[/hide]
Title: Re: Non-Decreasing Positive Integers
Post by Grimbal on Sep 8th, 2008, 3:44pm
I saw it more graphically.
I imagined a histogram with 11 columns, each column has height 1 to 9 and is higher or equal to the previous column.
Title: Re: Non-Decreasing Positive Integers
Post by ecoist on Sep 8th, 2008, 5:22pm
My senility must be worse than I thought.  Still don't get it, Grimbal.  I do get that the problem is equivalent to counting all non-decreasing functions from {1,...,11} into {1,...,9}.

My first solution involved letting f(n,k) be the number of n-letter words in non-decreasing letters from an ordered alphabet of k letters.  Then I split all such words into two sets, those which contain the least letter from the alphabet and those which do not contain the least letter.  Then the number of words in the first set is f(n-1,k) and the number of words in the second set is f(n,k-1).  The table of f-values is thus seen to be a portion of Pascal's triangle.
Title: Re: Non-Decreasing Positive Integers
Post by towr on Sep 9th, 2008, 12:05am

on 09/08/08 at 17:22:26, ecoist wrote:
My senility must be worse than I thought.  Still don't get it, Grimbal.  
You could look at it like this, you start with digit 1, and "moving to the right" changes the digit by 1; "moving up" fixes the digit at the current position. So you get a path through an 12x9 grid (you can go up 11 times, and right 8 times).
And every path that reaches the top right (or top row) is a different solution, and together they make up all solutions.
Title: Re: Non-Decreasing Positive Integers
Post by ecoist on Sep 9th, 2008, 6:20pm
Essentially the same as Grimbal's explanation, towr.  Don't see the connection between the graph and the solution.  Except via the trick I used in my hidden solution.
Title: Re: Non-Decreasing Positive Integers
Post by towr on Sep 10th, 2008, 12:04am
Well, do you see that you get all non-decreasing numbers with this method?
After that it's just a matter of counting them. And that is a matter of counting all combinations of the 11 up and 8 left moves. Which is 19!/11!/8!.
Title: Re: Non-Decreasing Positive Integers
Post by Hippo on Sep 10th, 2008, 1:27am

on 09/09/08 at 18:20:44, ecoist wrote:
Essentially the same as Grimbal's explanation, towr.  Don't see the connection between the graph and the solution.  Except via the trick I used in my hidden solution.


Make a grid of 9x11 squares.
Fill first row with 1s, Second with 2s, ... Ninth with 9s.
Represent k-th digit of given 11digit number by marking cell in the k-th column filled with the digit.
Now the centers of the cells are the graph vertices. Add additional 12th column, too.

Now how the path corresponds to the number. Start with the 1,1 cell and go down to the marked cell in the column and than move to the next column. Repeat until last marked cell is visited. Than move right to the 12th column and move down to the 9th row.

The numbers and paths with 8 steps down, 11 right are in one-one correspondence.
Title: Re: Non-Decreasing Positive Integers
Post by ecoist on Sep 10th, 2008, 8:50am
Yes, towr, I get the equivalence of the graph problem with the non-decreasing integer problem.  If the graph problem had an obvious or well known solution, I would not have been lost.

Thanks, Hippo.  You provide the missing connection between the graph problem and its solution.  I hadn't thought of "the centers of the cells" and "Add additional 12th column".  Translating your explanation in Grimbal's histogram terms, one can say this.  A non-decreasing integer leads to a histogram with 11 columns of maximum height 9.  Append to the right end a column of height 9 ("Add additional ...").  The associated graph is the path formed by the left side and top of the histogram, ignoring the guaranteed first "up" move and the guaranteed last "right" move ("the centers of ...").
Title: Re: Non-Decreasing Positive Integers
Post by towr on Sep 10th, 2008, 9:34am

on 09/10/08 at 08:50:49, ecoist wrote:
If the graph problem had an obvious or well known solution, I would not have been lost.
Maybe I've hung around these forums too long, cause I considered it pretty well known. We've certainly had such 'number of paths on a rectangular grid' puzzles before.
Title: Re: Non-Decreasing Positive Integers
Post by ecoist on Sep 10th, 2008, 4:59pm
Yes, towr, counting paths joining two points on a grid is a basic counting problem.  But Hippo was the first to clear my fog by describing the paths associated with non-decreasing integers precisely enough so that every path had exactly 11 "right" moves and 8 "up" moves.  Thanks to all for helping me understand Grimbal's solution.
Title: Re: Non-Decreasing Positive Integers
Post by Hippo on Sep 11th, 2008, 2:51am

on 09/10/08 at 08:50:49, ecoist wrote:
Yes, towr, I get the equivalence of the graph problem with the non-decreasing integer problem.  If the graph problem had an obvious or well known solution, I would not have been lost.

Thanks, Hippo.  You provide the missing connection between the graph problem and its solution.  I hadn't thought of "the centers of the cells" and "Add additional 12th column".  Translating your explanation in Grimbal's histogram terms, one can say this.  A non-decreasing integer leads to a histogram with 11 columns of maximum height 9.  Append to the right end a column of height 9 ("Add additional ...").  The associated graph is the path formed by the left side and top of the histogram, ignoring the guaranteed first "up" move and the guaranteed last "right" move ("the centers of ...").


:) You are wellcomed. :) It's fun that the language barrier was overcamed by better empathy.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board