Re: Combinatoric question


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

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.

.

Relevant Pages

  • Combinatoric question
    ... Been too long since college math classes, ... turn up anything via Google. ... number of permutations of 10 items taken six at a time ... where none of the digits is seven (i.e., ...
    (sci.math)
  • VBA: count sevens
    ... determines and prints how many of the digits are sevens. ... A textbox ...
    (microsoft.public.excel.programming)
  • =?windows-1252?B?UmU6IFRoZXJlIGlzIH6TZXZpZGVuY2WUfiBvZiB+k0dvZJR+IGluIHRoZQ==?=
    ... experience of the existence of God in 2002. ... Take the digits of 11; add them, ... Two sevens are 7/7, the exact date of the London ...
    (talk.origins)
  • [SUMMARY] Getting to 100 (#119)
    ... puts "#possible equations tested" ... they can come up in and Dennis chose to just hardcode those in the OPS constant. ... Dennis just counts off some number of digits from the front of the ... works by recursively combining smaller and smaller permutations until it has ...
    (comp.lang.ruby)
  • Solving the Google "prime number in e" challenge
    ... JOB HUNTERS, GOOGLE THIS ... Here you'll find a RosAsm assembly program that computes the decimal digits ... have one multi-kilobyte number to deal with, E, that you divide by N, ... the Woz algorithm runs through a long memory array one byte ...
    (alt.lang.asm)