FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Undergraduate
Can you count?
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
Author Message
Alexander Blessing
science forum beginner


Joined: 05 Feb 2005
Posts: 11

PostPosted: Tue Jul 18, 2006 4:03 pm    Post subject: Can you count? Reply with 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?

Any idea guys?
Back to top
Brian M. Scott
science forum Guru


Joined: 10 May 2005
Posts: 332

PostPosted: Tue Jul 18, 2006 5:22 pm    Post subject: Re: Can you count? Reply with quote

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?

Quote:
Any idea guys?

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, Cool * 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

PostPosted: Tue Jul 18, 2006 5:52 pm    Post subject: Re: Can you count? Reply with quote

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

PostPosted: Tue Jul 18, 2006 7:59 pm    Post subject: Re: Can you count? Reply with quote

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

PostPosted: Wed Jul 19, 2006 2:28 pm    Post subject: Re: Can you count? Reply with 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? 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

PostPosted: Wed Jul 19, 2006 8:50 pm    Post subject: Re: Can you count? Reply with quote

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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
The time now is Thu Oct 20, 2011 3:14 am | All times are GMT
Forum index » Science and Technology » Math » Undergraduate
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Why you can not count real number? cyclomethane@gmail.com Math 13 Mon Jul 10, 2006 11:59 am
No new posts HPLC/UV Effect of Flow rate on Area Count denise.pattavina@gmail.co Analytical 1 Thu Jul 06, 2006 3:43 pm
No new posts Effect of Flow Rate on Area Count denise.pattavina@gmail.co Analytical 3 Thu Jul 06, 2006 2:32 pm
No new posts IN THE U.S., STUDENTS COUNT ON VEDIC-HINDU MATHEMATICS Dr. Jai Maharaj Math 5 Wed Jun 28, 2006 7:03 am
No new posts Pls. help to count probabilities valery Math 2 Fri Jun 16, 2006 8:23 am

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
[ Time: 0.2031s ][ Queries: 16 (0.1540s) ][ GZIP on - Debug on ]