Author 
Message 
Alexander Blessing science forum beginner
Joined: 05 Feb 2005
Posts: 11

Posted: Tue Jul 18, 2006 4:03 pm Post subject:
Can you count?



Let n denote the number of digits of a natural number.
Now, how many natural numbers with n digits are there which contain all
digits from 0 to 9 in their 10adic expansion?
Any idea guys? 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Tue Jul 18, 2006 5:22 pm Post subject:
Re: Can you count?



On 18 Jul 2006 09:03:03 0700, <Whatever5k@web.de> wrote in <news:1153238583.888319.193780@s13g2000cwa.googlegroups.com> in alt.math.undergrad:
Quote:  Let n denote the number of digits of a natural number.
Now, how many natural numbers with n digits are there which contain all
digits from 0 to 9 in their 10adic expansion?

And which don't start with 0, right?
I don't see any simpler way to count them than an
inclusionexclusion argument. First, there are 9 possible
first digits. Once you've picked the first digit, you have
to pick an (n1)digit number that contains all of the other
9 digits and is allowed to start with 0. How many ways are
there to do this?
There are 10^(n1) ways to pick an (n1)digit number
without any restrictions at all. Now suppose that d is one
of the 9 digits that we must include; there are 9^(n1) ways
to form an (n1)digit number that does not include d and
should therefore not be included in the total. Subtracting
these from the initial count leaves 10^(n1)  9^(n1);
doing this for each of the 9 required digits leaves
10^(n1)  9 * 9^(n1).
Unfortunately, we've subtracted too much: an (n1)digit
number that is missing two of the required digits will have
been subtracted twice and therefore has to be added back in.
There are C(9, 2) possible pairs of the required digits, and
there are 8^(n1) ways to form an (n1)digit number that
excludes a given pair of digits, so we must add back in
C(9, 2) * 8^(n1) to get
10^(n1)  9^(n1) + C(9, 2) * 8^(n1).
But this also turns out to be an overcompensation: numbers
that are missing three of the required digits are now being
overcounted. There are C(9, 3) * 7^(n1) such numbers, so
the new partial total is
10^(n1)  9^(n1) + C(9, 2) * 8^(n1)  C(9, 3) * 7^(n1).
In this context the inclusionexclusion theorem essentially
says that continuing these alternating adjustments will
yield the correct result:
10^(n1)  9^(n1) + C(9, 2) * 8^(n1)  C(9, 3) * 7^(n1)
+ C(9, 4) * 6^(n1)  C(9, 5) * 5^(n1) + C(9, 6) * 4^(n1)
 C(9, 7) * 3^(n1) + C(9, * 2^(n1)  C(9, 9) * 1^(n1)
Of course this must be multiplied by 9, for the 9way
choice of the first digit of the original ndigit number.
(That was your email 'Kombinatorik', yes? I was going to
answer it today, but it takes me a while to put something
like this into German, and I was also hoping to think of
a simpler solution for you. These might be of some use:
<http://de.wikipedia.org/wiki/Siebformel>
<http://en.wikipedia.org/wiki/Inclusionexclusion_principle>)
Brian 

Back to top 


Alexander Blessing science forum beginner
Joined: 05 Feb 2005
Posts: 11

Posted: Tue Jul 18, 2006 5:52 pm Post subject:
Re: Can you count?



Thanks Brian.
So there seems to be no other argument than inclusionexclusion. I
mean, the formula seems pretty weird for a rather simple(sounding)
problem. 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Tue Jul 18, 2006 7:59 pm Post subject:
Re: Can you count?



On 18 Jul 2006 10:52:42 0700, <Whatever5k@web.de> wrote in
<news:1153245162.775151.143430@m73g2000cwd.googlegroups.com>
in alt.math.undergrad:
Quote:  Thanks Brian.
So there seems to be no other argument than inclusionexclusion.

It's the most elementary one that I can find. There's
probably also an argument by setting up a recurrence and
using generating functions, but the recurrence isn't
immediately obvious.
Quote:  I mean, the formula seems pretty weird for a rather
simple(sounding) problem.

My experience is that counting problems are frequently
harder than they 'ought' to be.
Brian 

Back to top 


Alexander Blessing science forum beginner
Joined: 05 Feb 2005
Posts: 11

Posted: Wed Jul 19, 2006 2:28 pm Post subject:
Re: Can you count?



Ok, thank you.
So, if I wanted to find out how many numbers with n digits exist which
have _at most_ 9 digits, this could be written as 10^n  your answer,
right? Isn"t there a simpler formula for at least that problem?
What do you think? 

Back to top 


Brian M. Scott science forum Guru
Joined: 10 May 2005
Posts: 332

Posted: Wed Jul 19, 2006 8:50 pm Post subject:
Re: Can you count?



On 19 Jul 2006 07:28:02 0700, <Whatever5k@web.de> wrote in
<news:1153319281.471231.225100@i3g2000cwc.googlegroups.com>
in alt.math.undergrad:
Quote:  Ok, thank you.
So, if I wanted to find out how many numbers with n digits exist which
have _at most_ 9 digits, this could be written as 10^n  your answer,
right?

Not quite, since that includes numbers with leading zeroes.
It would be 9 * 10^(n1) minus my answer.
Quote:  Isn"t there a simpler formula for at least that problem?

I don't think so. It's easy enough to count the ndigit
numbers that use only the digits 1, 2, ..., 9 (but not
necessarily all of them): there are 9^n such numbers. It's
not much harder to count the ndigit numbers that use only
the digits 0, 1, ..., 8 (but not necessarily all of them):
there are 8 * 9^(n1) of them. There are also 8 * 9^(n1)
ndigit numbers that use only the digits 0, 1, 2, 3, 4, 5,
6, 7, 9, and so on. But you can't simply add up these
partial totals to get 9^n + 9 * 8 * 9^(n1) = 9^(n+1),
because every number that uses fewer than 9 different digits
gets counted at least twice. The ndigit number 111...111,
for instance, gets counted 9 times, while the ndigit number
12345678111...111 gets counted exactly twice. Thus, this
approach still leads to an inclusionexclusion argument.
Brian 

Back to top 


Google


Back to top 



The time now is Fri Nov 16, 2018 3:35 pm  All times are GMT

