Search   Memberlist   Usergroups
 Page 1 of 1 [6 Posts]
Author Message
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

 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
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?
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

 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
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.
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?

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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [6 Posts]
 The time now is Fri Mar 22, 2019 4:23 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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