CODEWITHSUNDEEP
algorithmmathpermutation
anon-bee-01
anon-bee-01

Reputation: 68

calculate combinations of numbers where a specific digit occurs more than n number of times

how do we calculate combinations of numbers where a specific digit occurs more than n number of times ? eg : in 4 digit number 1112, 1 occurs 3 times. again 1211, 1121, 2111, 1111 would be such numbers. basically 1 more than 2 times(3,4 times) what would be the formula for calculating such permutations

Upvotes: 1

Views: 457

Answers (1)

Dave
Dave

Reputation: 9075

Let's say f(n, k) is the count of n digit numbers where a specific digit is repeated k times, for k <= n.

We can start by considering all n-k digit numbers that don't have the specified digit, then all ways of inserting that digit.

There are 9^(n-k) numbers with n-k digits that don't have the specified digit. This includes numbers with leading zeroes (comment if these are disallowed).

Now, for each of these, in how many ways can we insert k copies of the specified digit?

The answer is n! / (k! * (n-k)!), which is the number of permutations of n things, divided by the number of permutations of the non-specified digit (which we don't want to permute among themselves) and the number of permutations of the specified digit (ditto).

So f(n,k) = 9^(n-k) * n! / (k! * (n-k)!)

Now, what you asked for is the count of n digit numbers where a specific digit is repeated k OR MORE times, for k <= n. Let's call this g(n,k).

g(n,k) = sum(f(n,i)) for i in {k, k+1, ..., n}

Sample Code (Ruby): (fact is factorial)

def f(n,k)
  return 9**(n-k)*fact(n) / (fact(k)*fact(n-k))
end

def g(n,k)
  ans = 0
  k.upto(n) do |i|
    ans += f(n,i)
  end
  return ans
end

Sample output:

g(5,0) = 100,000 (as expected, all possible 5 digit numbers = 10**5)
g(5,1) =  40,951 (as expected, 10**5 - 9**5)
g(5,2) =   8,146
g(5,3) =     856
g(5,4) =      46
g(5,5) =       1

Upvotes: 1

Related Questions