How to get number of all unique permutations of lengh k out of string of length n?

Question

Suppose we are given string s = "aba" and k = 2. Then the permutations we can make using string characters are

aa ab ba So the answer is 3.

If s = "aabb" and k = 2 then possible permutations are

aa ab ba bb So answer is 4.

We can use a character only as many as times it is appeared in string or less than that but not more than that.

Is there any formula or some way to find it out quickly?

Note: K is not the number of unique charcters, for eg. s=aabbcdd the value of k may be k=3.

Answer 1

This isn't particularly useful for a pen-paper approach, but you can use generating functions. Look at the coefficient of $x^k$ in the expansion of $$k!(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots + \frac{x^a}{a!})(1+x+\frac{x^2}{2!}+\dots+\frac{x^b}{b!})\cdots (1+x+\dots+\frac{x^z}{z!})$$ where $a,b,\dots,z$ are the number of occurrences of the letters a,b,...,z respectively in your original string.

In your example of aabbcdd and $k=3$ this would be the coefficient of $x^3$ in the expansion of:

$3!(1+x+\frac{x^2}{2})(1+x+\frac{x^2}{2})(1+x)(1+x+\frac{x^2}{2})$

which comes out to be $51$ after plugging it into a calculator.

Somewhere buried in my answers from the past (on a possibly now deleted question which might be why I can't find it) I know I had taken the time to write out another expression for it using inclusion-exclusion, but that is even worse to try to implement in most scenarios and I do not recommend it.

---

For small scenarios, you could approach directly via breaking into cases. Looking at the aabbcdd and $k=3$ example again, you have the following two cases:

• All letters used are distinct: pick first, pick second, pick third for $4\cdot 3\cdot 2 = 24$ outcomes here
• A letter is used twice: pick which was used twice, pick remaining letter, pick location of remaining letter for $3\cdot 3\cdot 3 = 27$ outcomes here.

Adding gives $24+27=51$ outcomes, same as what was found earlier.

This will get very tedious to do very quickly as numbers get larger however and is not recommended beyond simple examples.