CODEWITHSUNDEEP
combinationspermutationdynamic-programmingcombinatoricscounting
Hitesh Dholaria
Hitesh Dholaria

Reputation: 157

Counting the passwords of length N using an alphabet containing M characters

Say, there are M characters in our alphabet. We want to form the passwords (or character strings) of length N. Constraint is that all the passwords must contain every character from the input alphabet at least once. So, how many such passwords are possible?

Also, M <= N

Example-1: M = 4, N = 4, Answer = 24

Answer = M! or N! (all permutations of length 4)

Example-2: M = 2, N = 3, Answer = 6

Let M = {a, b}
Possible passwords are {aab, aba, baa, bba, bab, abb}

So, can we derive the general formula of counting such passwords for the given values of M and N?

Upvotes: 0

Views: 406

Answers (1)

Hitesh Dholaria
Hitesh Dholaria

Reputation: 157

Finally, I got the answer:

Answer = m! * S(n, m)

where, S(n, m) = Stirling number of second kind

Upvotes: 1

Related Questions