Re: Combinatoric question
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 12 May 2006 00:41:26 -0700
Jules wrote:
Larry Coon wrote:
Not homework or anything like that -- just curiosity.
Been too long since college math classes, and I didn't
turn up anything via Google.
What's the correct approach to problems like, "find
how many n-digit numbers have the digit d at least x
times." E.g., "find how many 10-digit numbers have
at least five sevens."
BTW, if numbers aren't allowed to start with zeros, this is a MUCH
harder problem.
Easy enough to write a program to iterate through the
numbers and count them, but that's cheating. (I
cheated anyway and got 16,349,374.)
I tried approaching it as 10,000,000,000 minus the
number of permutations of 10 items taken six at a time
where none of the digits is seven (i.e., eliminate the
permutations where at least six digits are not seven),
but that wasn't getting me anywhere.
In my judgement, the easiest way to do this is to count the number of
10 digit numbers that have exactly five sevens, then the number with
exactly 6 sevens, all the way up through 10. To count the number of 10
digit numbers with exactly five sevens, you take 10 choose 5, and
multiply by 9 ^ 5. That is, you choose which five of the digits are
sevens, then you pick which of the digits that are not seven fill in
each of the other 5 digits. You will have to make an adjustment,
though, because this method will count numbers with leading zeroes, and
these are not really ten-digit numbers.
There are also Generalized Inclusion-Exclusion formulas, which for sets
A(1), A(2), ..., A(n), count how many elements are in exactly k of
these sets, or which are in at least k sets. (The standard IE formula
counts how many elements are in at least 1 set.) In your case, A(i)
would be the numbers where the i-th digit is 7.
See http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html for
the basic IE formula. If it's written as
S(1) - S(2) + S(3) - ... + (-1)^(p-1) S(p),
(that is, S(1) is the sum of the sizes of the sets, etc.), then the
number of elements which are in exactly m sets is
C(m,m) S(m) - C(m+1,m) S(m+1) + C(m+2,m) S(m+2) - ...
+ (-1)^(p-m) C(p,m) S(p),
and the number of elements in at least m sets is
C(m-1,m-1) S(m) - C((m+1)-1,m-1) S(m+1) + C((m+2)-1, m-1) S(m+2) - ...
+ (-1)^(p-m) C(p-1,m-1) S(p).
For the problem you posted,
What's the correct approach to problems like, "find
how many n-digit numbers have the digit d at least x
times." E.g., "find how many 10-digit numbers have
at least five sevens."
S(1) = 10 * 10^(10-1)
S(2) = C(10,2) * 10^(10-2)
S(3) = C(10,3) * 10^(10-3)
....
S(10) = C(10,10) * 10^(10-10) = 1
Then you use the second general form above, to get
C(m-1,m-1) S(m) - C((m+1)-1,m-1) S(m+1) + C((m+2)-1, m-1) S(m+2) - ...
+ (-1)^(p-m) C(p-1,m-1) S(p).
= C(5-1,5-1) S(5) - C(6-1,5-1) S(6) + C(7-1,5-1) S(7) - C(8-1,5-1) S(8)
+ C(9-1,5-1) S(9) - C(10-1,5-1) S(10)
= C(4,4) * C(10,5) * 10^5 - C(5,4) * C(10,6) * 10^4 + C(6,4) * C(10,7)
* 10^3
- C(7,4) * C(10,8) * 10^2 + C(8,4) * C(10,9) * 10^1 + C(9,4)
= 16,349,626.
--- Christopher Heckman
.
- Follow-Ups:
- Re: Combinatoric question
- From: James Waldby
- Re: Combinatoric question
- References:
- Combinatoric question
- From: Larry Coon
- Re: Combinatoric question
- From: Jules
- Combinatoric question
- Prev by Date: Re: what does 'determinant ?' mean
- Next by Date: Re: It is not easy
- Previous by thread: Re: Combinatoric question
- Next by thread: Re: Combinatoric question
- Index(es):
Relevant Pages
|
