|
|
| 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 10-adic 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 10-adic expansion?
|
And which don't start with 0, right?
I don't see any simpler way to count them than an
inclusion-exclusion argument. First, there are 9 possible
first digits. Once you've picked the first digit, you have
to pick an (n-1)-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^(n-1) ways to pick an (n-1)-digit number
without any restrictions at all. Now suppose that d is one
of the 9 digits that we must include; there are 9^(n-1) ways
to form an (n-1)-digit number that does not include d and
should therefore not be included in the total. Subtracting
these from the initial count leaves 10^(n-1) - 9^(n-1);
doing this for each of the 9 required digits leaves
10^(n-1) - 9 * 9^(n-1).
Unfortunately, we've subtracted too much: an (n-1)-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^(n-1) ways to form an (n-1)-digit number that
excludes a given pair of digits, so we must add back in
C(9, 2) * 8^(n-1) to get
10^(n-1) - 9^(n-1) + C(9, 2) * 8^(n-1).
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^(n-1) such numbers, so
the new partial total is
10^(n-1) - 9^(n-1) + C(9, 2) * 8^(n-1) - C(9, 3) * 7^(n-1).
In this context the inclusion-exclusion theorem essentially
says that continuing these alternating adjustments will
yield the correct result:
10^(n-1) - 9^(n-1) + C(9, 2) * 8^(n-1) - C(9, 3) * 7^(n-1)
+ C(9, 4) * 6^(n-1) - C(9, 5) * 5^(n-1) + C(9, 6) * 4^(n-1)
- C(9, 7) * 3^(n-1) + C(9,  * 2^(n-1) - C(9, 9) * 1^(n-1)
Of course this must be multiplied by 9, for the 9-way
choice of the first digit of the original n-digit number.
(That was your e-mail '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/Inclusion-exclusion_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 inclusion-exclusion. 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 inclusion-exclusion.
|
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^(n-1) 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 n-digit
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 n-digit numbers that use only
the digits 0, 1, ..., 8 (but not necessarily all of them):
there are 8 * 9^(n-1) of them. There are also 8 * 9^(n-1)
n-digit 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^(n-1) = 9^(n+1),
because every number that uses fewer than 9 different digits
gets counted at least twice. The n-digit number 111...111,
for instance, gets counted 9 times, while the n-digit number
12345678111...111 gets counted exactly twice. Thus, this
approach still leads to an inclusion-exclusion argument.
Brian |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Oct 20, 2011 3:14 am | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Undergraduate
