Author |
Topic: Non-Decreasing Positive Integers (Read 1816 times) |
|
joh
Newbie
Posts: 4
|
 |
Non-Decreasing Positive Integers
« on: Sep 6th, 2008, 6:26pm » |
 Quote  Modify
|
Find the number of 11-digit positive integers such that the digits from left to right are non-decreasing. (For example, 12345678999,55555555555,23345557889.)
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Non-Decreasing Positive Integers
« Reply #1 on: Sep 7th, 2008, 4:17am » |
Quote Modify
|
Hint:
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).
Solution:
That is C(21,10) = 352716.
[edit]shown incorrect. see below.[/edit]
|
| « Last Edit: Sep 10th, 2008, 1:31am by Grimbal » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Non-Decreasing Positive Integers
« Reply #2 on: Sep 7th, 2008, 6:51am » |
Quote Modify
|
on Sep 7th, 2008, 4:17am, Grimbal wrote:Hint:
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).
Solution:
That is C(21,10) = 352716. |
|
Which would include the number 0123456789X?
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, possibilities
|
|
IP Logged |
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Non-Decreasing Positive Integers
« Reply #3 on: Sep 7th, 2008, 12:24pm » |
Quote Modify
|
What we need is C(20,11) to me since we don't have to start at 1.
|
| « Last Edit: Sep 7th, 2008, 12:46pm by teekyman » |
IP Logged |
|
|
|
cool_joh
Newbie
Gender:
Posts: 50
|
|
Re: Non-Decreasing Positive Integers
« Reply #4 on: Sep 7th, 2008, 1:38pm » |
Quote Modify
|
on Sep 7th, 2008, 4:17am, Grimbal wrote:Hint:
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).
Solution:
That is C(21,10) = 352716. |
|
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.
|
|
IP Logged |
MATH PRO
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Non-Decreasing Positive Integers
« Reply #5 on: Sep 7th, 2008, 1:40pm » |
Quote Modify
|
on Sep 7th, 2008, 12:24pm, 1337b4k4 wrote:| What we need is C(20,11) 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)
|
|
IP Logged |
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Non-Decreasing Positive Integers
« Reply #6 on: Sep 7th, 2008, 2:15pm » |
Quote Modify
|
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.)
|
| « Last Edit: Sep 7th, 2008, 2:16pm by teekyman » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Non-Decreasing Positive Integers
« Reply #7 on: Sep 8th, 2008, 1:07am » |
Quote Modify
|
on Sep 7th, 2008, 6:51am, rmsgrey wrote:Which would include the number 0123456789X?
|
|
Oops! Right. 
Replace 10 by 8 (for no loading zeroes) and I align with rmsgrey.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Non-Decreasing Positive Integers
« Reply #8 on: Sep 8th, 2008, 2:23pm » |
Quote Modify
|
Didn't understand Grimbal's solution, so I looked at the problem slightly differently.
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).
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Non-Decreasing Positive Integers
« Reply #9 on: Sep 8th, 2008, 3:44pm » |
Quote Modify
|
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.
|
| « Last Edit: Sep 8th, 2008, 3:45pm by Grimbal » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Non-Decreasing Positive Integers
« Reply #10 on: Sep 8th, 2008, 5:22pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Non-Decreasing Positive Integers
« Reply #11 on: Sep 9th, 2008, 12:05am » |
Quote Modify
|
on Sep 8th, 2008, 5:22pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Non-Decreasing Positive Integers
« Reply #12 on: Sep 9th, 2008, 6:20pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Non-Decreasing Positive Integers
« Reply #13 on: Sep 10th, 2008, 12:04am » |
Quote Modify
|
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!.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Non-Decreasing Positive Integers
« Reply #14 on: Sep 10th, 2008, 1:27am » |
Quote Modify
|
on Sep 9th, 2008, 6:20pm, 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.
|
| « Last Edit: Sep 10th, 2008, 1:46am by Hippo » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Non-Decreasing Positive Integers
« Reply #15 on: Sep 10th, 2008, 8:50am » |
Quote Modify
|
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 ...").
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Non-Decreasing Positive Integers
« Reply #16 on: Sep 10th, 2008, 9:34am » |
Quote Modify
|
on Sep 10th, 2008, 8:50am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Non-Decreasing Positive Integers
« Reply #17 on: Sep 10th, 2008, 4:59pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Non-Decreasing Positive Integers
« Reply #18 on: Sep 11th, 2008, 2:51am » |
Quote Modify
|
on Sep 10th, 2008, 8:50am, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print