increasing numbers

[Gunnar G]

Here's a problem I've been struggling with.

An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.

First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.
Let f(n) = the number of increasing numbers with n digits (counting leading
zeros)
Then the sought answer is 2f(n)-10. -10 because to compensate for the 10
numbers that contains only one digit.
To calculate f(n) I use the following maple functions

f:=n->sum(a(x,n),x=0..9);
a:=(x,n)-> if n=1 then 1 else sum(a(i,n-1),i=x..9); fi;

where a(x,n) is the number of increasing n-digit numbers that starts with
the digit x.
f(6) gives 5005 which gives 10000.

Is this correct or have I missed something?

[Gunnar G]

Oh, never mind. I found the problem.

[m***@yahoo.co.uk]

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.
Let f(n) = the number of increasing numbers with n digits (counting leading
zeros)
Then the sought answer is 2f(n)-10. -10 because to compensate for the 10
numbers that contains only one digit.
To calculate f(n) I use the following maple functions
f:=n->sum(a(x,n),x=0..9);
a:=(x,n)-> if n=1 then 1 else sum(a(i,n-1),i=x..9); fi;
where a(x,n) is the number of increasing n-digit numbers that starts with
the digit x.
f(6) gives 5005 which gives 10000.
Is this correct or have I missed something?

I think your answer is correct, but there is a simple formula for f(n)
that eliminates the need to do the laborious summing, namely

f(n) = C(n + 9, n)

where C(a, b) ("a choose b") is equal to a! / ((a - b)! * b!).

More generally if you allow x different digits (or symbols) - where in
your case x = 10 - then

f(n, x) = C(n + x - 1, n)

You can obtain this result from Pascal's triangle.

[Arturo Magidin]

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.

This argument does not fly. The decreasing numbers 1, 10, 100, 1000,
10000, 100000, etc. all yield the same increasing number when
reversed: 1.

[m***@yahoo.co.uk]

Post by Arturo Magidin

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.

This argument does not fly. The decreasing numbers 1, 10, 100, 1000,
10000, 100000, etc. all yield the same increasing number when
reversed: 1.

He goes on to specify "numbers with n digits (counting leading zeros)",
which presumably means that all numbers are to be padded to n digits
with leading zeros as necessary.

[Arturo Magidin]

Post by m***@yahoo.co.uk

Post by Arturo Magidin

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.

This argument does not fly. The decreasing numbers 1, 10, 100, 1000,
10000, 100000, etc. all yield the same increasing number when
reversed: 1.

He goes on to specify "numbers with n digits (counting leading zeros)",

That's his definition for f(n). In that case, he is really counting
all increasing numbers that can be written with atmost n
digits. However, the argument that the number of increasing numbers of
at most n digits is equal to the number of decreasing numbers of at
most n digits doesn't work: the "reversal" function is not one-to-one.

Post by m***@yahoo.co.uk
which presumably means that all numbers are to be padded to n digits
with leading zeros as necessary.

Which doesn't work for decreasing numbers, since padding with zeroes
would make it a non-decreasing number.

Look, let's make it simple. How many nonnegative increasing and how
many nonnegative decreasing numbers of at most 2 digits are there?

Increasing:

10 numbers of 1 digit
9 numbers of 2 digits that start with 1
8 numbers of 2 digits that start with 2
7 numbers of 2 digitits that start with 3
6 that start with 4
5 that start with 5
4 that start with 6
3 that start with 7
2 that start with 8
1 that starts with 9
------
55 increasing numbers of at most 2 digits.

Are there really 55 decreasing numbers of at most 2 digits?

10 decreasing with one digit
2 decreasing with two digits, start with 1
3 decreasing with 3 digits, start with 2
4 start with 3
5 start with 4
6 start with 5
7 start with 6
8 start with 7
9 start with 8
10 start with 9 (namely, 90, 91, ..., 99)
---
64 decreasing numbers of at most two digits.

The claim that the number of increasing numbers of at most n digits is
equal to the number of decreasing numbers of at most n digits is
simply false. The argument given is false. Pad it with zeros if you
want, it is still false. Because "reversing" a decreasing number gives
an increasing number, but the function is not one to one.

And he clearly wants to count the one digit numbers as decreasing, so
you can't place leading zeros on them (if you did, only 00 would be
decreasing). So the argument that the number of increasing and
decreasing numbers is the same is false.

The calculation of increasing numbers is fine, but it is not equal to
the number of decreasing numbers.

[Proginoskes]

Post by Arturo Magidin

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.

This argument does not fly. The decreasing numbers 1, 10, 100, 1000,
10000, 100000, etc. all yield the same increasing number when
reversed: 1.

When you pad 0's on the left, 1 does not become decreasing (00001), nor
10 (00010), etc.

matt271829-***@yahoo.co.uk has the right idea. The number of ways to
choose n digits where order doesn't matter, and where repetition is
allowed is

f(n) = C(n + 9, n)

There is only one way to order such a "set" of numbers to make an
increasing number, and only one way to order them to make a decreasing
number, so every "combination" of n digits will produce 2 monotonic
(increasing or decreasing) numbers ... UNLESS the same number is chosen
n times. So the number of n-digit monotonic numbers (where 0 counts as
a leading digit) is

2 * C(n + 9, n) - 9.

When n=6, this solves the OP's problem.

--- Christopher Heckman

[Arturo Magidin]

Post by Proginoskes

Post by Arturo Magidin

Post by Gunnar G
Here's a problem I've been struggling with.
An integer is called increasing if the no digit is smaller than the integer
to the left of it, i.e. 2449 is increasing.
The integer is said to be decreasing if no digit is larger than the integer
to the left of it.
Now, how many of the integers below one million is increasing or decreasing?
I'd say there are 10000.
First, the number of increasing numbers must be the same as the number of
decreasing since an increasing number is a decreasing number if the digits
are reversed, and vice versa.

This argument does not fly. The decreasing numbers 1, 10, 100, 1000,
10000, 100000, etc. all yield the same increasing number when
reversed: 1.

When you pad 0's on the left, 1 does not become decreasing (00001), nor
10 (00010), etc.

Oh, for crying out loud. Just do the computations for numbers with one
or two digits. There are 55 increasing numbers; there are 64
decreasing numbers with 1 or 2 digits. There is a total of 100 numbers
between 0 and 99 which are either increasing or decreasing or both: we
counted the 9 positive multiples of 11, and the 10 single digit
numbers twice each (hardly surprising, since there's not enough room
to "turn around"). Padding with zeros on the left was done so that the
function f(n) counted all increasing numbers with at most n
digits. But all of this was predicated on the claim that the number of
increasing and of decreasing numbers is equal.

If you pad with zeros on the left, and f(n) is the number of
increasing numbers with exactly n digits counting the leading zeros,
then f(n)-1 (dropping 00000000) is equal to the decreasing
numbers with EXACTLY n digits (which of course has no leading
zeros). The only exception is when n=1, in which case f(1) is both the
increasing and the decreasing numbers.

So there is an asymmetry between increasing and decreasing numbers:
while f(3) will tell you exactly how many increasing numbers there are
between 0 and 999, inclusively, it will only tell you how many
decreasing numbers there are between 100 and 999; if you want to know
whow many decreasing numbers there are between 0 and 999 you need to
take f(1)+f(2)+f(3) - 2.

And in general, if f(n) gives you the number of increasing numbers
between 0 and 10^n-1 (i.e., up to n digits), then the number of
decreasing numbers between 0 and 10^n - 1 is
f(1) + ... + f(n) - (n-1).
Yes. And his answer is correct for increasing numbers of up to n
digits; it is not, however, correct for either decreasing or
(increasing or decreasing or both). Neither is yours.

Post by Proginoskes
The number of ways to
choose n digits where order doesn't matter, and where repetition is
allowed is
f(n) = C(n + 9, n)
There is only one way to order such a "set" of numbers to make an
increasing number, and only one way to order them to make a decreasing
number, so every "combination" of n digits will produce 2 monotonic
(increasing or decreasing) numbers ... UNLESS the same number is chosen
n times. So the number of n-digit monotonic numbers (where 0 counts as
a leading digit) is
2 * C(n + 9, n) - 9.
When n=6, this solves the OP's problem.

Let's try your formula to calculate the number of increasing and
decreasing numbers between 0 and 99: here n = 2, so we have

2*C(11,2) - 9 = 11(10) - 9 = 101.

Apparently there are one hundred and one numbers between 0 and 99.

There is an asymmetry between increasing and decreasing numbers; the
original poster, matt27189, and you, seem to have missed it.

You'll note that C(11,2) = 55 gives the correct number of increasing
numbers. But 55 is the number of decreasing numbers with EXACTLY two
digits. If you want the number of decreasing numbers with 1 or 2
digits, you need C(11,2)+C(10,1)-(2-1) = 55 + 10 - 1 = 64.

How many repeats? You have 10 repeats for the 1 digit, and after that
you have 9 repeats for every extra digit. So you have 9n+1 repeats. So
the correct formula would be

[Sum_{i=1}^{n}C(n+9,n)] - (n-1) decreasing numbers
+ C(n+2,n) increasing numbers
- (9n + 1) repeats.

[Arturo Magidin]

In article <dugj4a$2foe$***@agate.berkeley.edu>,
Arturo Magidin <***@math.berkeley.edu> wrote:

[.snip.]

Post by Arturo Magidin

Post by Proginoskes
The number of ways to
choose n digits where order doesn't matter, and where repetition is
allowed is
f(n) = C(n + 9, n)
There is only one way to order such a "set" of numbers to make an
increasing number, and only one way to order them to make a decreasing
number, so every "combination" of n digits will produce 2 monotonic
(increasing or decreasing) numbers ... UNLESS the same number is chosen
n times. So the number of n-digit monotonic numbers (where 0 counts as
a leading digit) is
2 * C(n + 9, n) - 9.
When n=6, this solves the OP's problem.

Let's try your formula to calculate the number of increasing and
decreasing numbers between 0 and 99: here n = 2, so we have
2*C(11,2) - 9 = 11(10) - 9 = 101.
Apparently there are one hundred and one numbers between 0 and 99.
There is an asymmetry between increasing and decreasing numbers; the
original poster, matt27189, and you, seem to have missed it.
You'll note that C(11,2) = 55 gives the correct number of increasing
numbers. But 55 is the number of decreasing numbers with EXACTLY two
digits. If you want the number of decreasing numbers with 1 or 2
digits, you need C(11,2)+C(10,1)-(2-1) = 55 + 10 - 1 = 64.
How many repeats? You have 10 repeats for the 1 digit, and after that
you have 9 repeats for every extra digit. So you have 9n+1 repeats. So
the correct formula would be
[Sum_{i=1}^{n}C(n+9,n)] - (n-1) decreasing numbers
+ C(n+2,n) increasing numbers
- (9n + 1) repeats.

Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.

In fact, I think your mistake is that you subtracted 9 instead of 10:
forgot all about choosing 0, I think. If you subtract 10, then it
gives the correct answer for numbers with EXACTLY n digits (counting
any possible leading zero), counting both increasing and decreasing
numbers.

[m***@yahoo.co.uk]

Post by Arturo Magidin
[.snip.]

Post by Arturo Magidin

Post by Proginoskes
The number of ways to
choose n digits where order doesn't matter, and where repetition is
allowed is
f(n) = C(n + 9, n)
There is only one way to order such a "set" of numbers to make an
increasing number, and only one way to order them to make a decreasing
number, so every "combination" of n digits will produce 2 monotonic
(increasing or decreasing) numbers ... UNLESS the same number is chosen
n times. So the number of n-digit monotonic numbers (where 0 counts as
a leading digit) is
2 * C(n + 9, n) - 9.
When n=6, this solves the OP's problem.

Let's try your formula to calculate the number of increasing and
decreasing numbers between 0 and 99: here n = 2, so we have
2*C(11,2) - 9 = 11(10) - 9 = 101.
Apparently there are one hundred and one numbers between 0 and 99.
There is an asymmetry between increasing and decreasing numbers; the
original poster, matt27189, and you, seem to have missed it.
You'll note that C(11,2) = 55 gives the correct number of increasing
numbers. But 55 is the number of decreasing numbers with EXACTLY two
digits. If you want the number of decreasing numbers with 1 or 2
digits, you need C(11,2)+C(10,1)-(2-1) = 55 + 10 - 1 = 64.
How many repeats? You have 10 repeats for the 1 digit, and after that
you have 9 repeats for every extra digit. So you have 9n+1 repeats. So
the correct formula would be
[Sum_{i=1}^{n}C(n+9,n)] - (n-1) decreasing numbers
+ C(n+2,n) increasing numbers
- (9n + 1) repeats.

Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.
forgot all about choosing 0, I think. If you subtract 10, then it
gives the correct answer for numbers with EXACTLY n digits (counting
any possible leading zero), counting both increasing and decreasing
numbers.
--

Yes. The original question could possibly have been more clearly
worded, but I interpreted it to mean that all numbers are padded with
leading zeros as necessary, to make the length up to n. This indeed
means, for example, that 1 as a two-digit number (01) is not
decreasing. This is not terribly intuitive, but it seemed to me at the
time to be what the OP intended. Maybe it was, maybe it wasn't, maybe
we shall never know ... but it agrees with his answer. Other
interpretations will give different answers.

BTW, I think Proginoskes' 2 * C(n + 9, n) - 9 is a typo for 2 * C(n +
9, n) - 10.

[Arturo Magidin]

Post by m***@yahoo.co.uk

Post by Arturo Magidin

Post by Arturo Magidin
[Sum_{i=1}^{n}C(n+9,n)] - (n-1) decreasing numbers
+ C(n+2,n) increasing numbers
- (9n + 1) repeats.

Should be:

[Sum_{i=1}^{n} C(i+9,i)] - (n-1) + C(n+2,n) - (9n+1).

Post by m***@yahoo.co.uk

Post by Arturo Magidin
Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.
forgot all about choosing 0, I think. If you subtract 10, then it
gives the correct answer for numbers with EXACTLY n digits (counting
any possible leading zero), counting both increasing and decreasing
numbers.

Yes. The original question could possibly have been more clearly
worded, but I interpreted it to mean that all numbers are padded with
leading zeros as necessary, to make the length up to n. This indeed
means, for example, that 1 as a two-digit number (01) is not
decreasing. This is not terribly intuitive, but it seemed to me at the
time to be what the OP intended.

See, I don't think so, because the poster said "How many increasing
and decreasing numbers are there less than a million?" He didn't say
"with six digits" or "with up to six digits". And his examples did not
have leading zeros.

Post by m***@yahoo.co.uk
Maybe it was, maybe it wasn't, maybe
we shall never know ... but it agrees with his answer.

Yes, but his answer was predicated on asserting several things: e.g.,
that there is an equal amount of increasing and decreasing numbers in
a given range. This only holds if you truly pad with zeros, which
makes the first question of "how many less than a million" not just
badly phrased, but point blank incorrectly phrased. As you can see
with "How many increasing and decreasing numbers are there less than
100?", the amount of increasing and decreasing numbers are not equal.

[Arturo Magidin]

In article <***@j52g2000cwj.googlegroups.com>,
<matt271829-***@yahoo.co.uk> wrote:

[.snip.]

Post by m***@yahoo.co.uk
Yes. The original question could possibly have been more clearly
worded, but I interpreted it to mean that all numbers are padded with
leading zeros as necessary, to make the length up to n. This indeed
means, for example, that 1 as a two-digit number (01) is not
decreasing. This is not terribly intuitive, but it seemed to me at the
time to be what the OP intended. Maybe it was, maybe it wasn't, maybe
we shall never know ... but it agrees with his answer.

Also note that the assertion that there were an equal number of increasing
and of decreasing numbers was made before the device of padding with
zeros.

Anyway, if the original poster will clarify his question, then we'll
know.

[Proginoskes]

Post by m***@yahoo.co.uk

Post by Arturo Magidin
[.snip.]

Post by Arturo Magidin

Post by Proginoskes
The number of ways to
choose n digits where order doesn't matter, and where repetition is
allowed is
f(n) = C(n + 9, n)
There is only one way to order such a "set" of numbers to make an
increasing number, and only one way to order them to make a decreasing
number, so every "combination" of n digits will produce 2 monotonic
(increasing or decreasing) numbers ... UNLESS the same number is chosen
n times. So the number of n-digit monotonic numbers (where 0 counts as
a leading digit) is
2 * C(n + 9, n) - 9.
When n=6, this solves the OP's problem.

Let's try your formula to calculate the number of increasing and
decreasing numbers between 0 and 99: here n = 2, so we have
2*C(11,2) - 9 = 11(10) - 9 = 101.
Apparently there are one hundred and one numbers between 0 and 99.
There is an asymmetry between increasing and decreasing numbers; the
original poster, matt27189, and you, seem to have missed it.
You'll note that C(11,2) = 55 gives the correct number of increasing
numbers. But 55 is the number of decreasing numbers with EXACTLY two
digits. If you want the number of decreasing numbers with 1 or 2
digits, you need C(11,2)+C(10,1)-(2-1) = 55 + 10 - 1 = 64.
How many repeats? You have 10 repeats for the 1 digit, and after that
you have 9 repeats for every extra digit. So you have 9n+1 repeats. So
the correct formula would be
[Sum_{i=1}^{n}C(n+9,n)] - (n-1) decreasing numbers
+ C(n+2,n) increasing numbers
- (9n + 1) repeats.

Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.
forgot all about choosing 0, I think. If you subtract 10, then it
gives the correct answer for numbers with EXACTLY n digits (counting
any possible leading zero), counting both increasing and decreasing
numbers.
--

Yes. The original question could possibly have been more clearly
worded, but I interpreted it to mean that all numbers are padded with
leading zeros as necessary, to make the length up to n. This indeed
means, for example, that 1 as a two-digit number (01) is not
decreasing. This is not terribly intuitive, but it seemed to me at the
time to be what the OP intended. Maybe it was, maybe it wasn't, maybe
we shall never know ... but it agrees with his answer. Other
interpretations will give different answers.
BTW, I think Proginoskes' 2 * C(n + 9, n) - 9 is a typo for 2 * C(n +
9, n) - 10.

Yes. I forgot 0000...0.

--- Christopher Heckman

[Frederick Williams]

Post by Arturo Magidin
...
Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.

Far better to call the padded creatures "numerals" not "numbers". 2 and
02 are surely the same number but different numerals.

[Arturo Magidin]

Post by Frederick Williams

Post by Arturo Magidin
...
Now, if you insist on putting leading zeroes, so that 1 does not count
as a decreasing number of more than 1 digit, etc., then clearly your
formula is also incorrect, since it still gives the wrong answer when
n=2.

Far better to call the padded creatures "numerals" not "numbers". 2 and
02 are surely the same number but different numerals.

Hey, I happen to agree. Which is why I said reversal wasn't a
bijection between increasing and decreasing, and why the formula was
more complicated than the other posters.