# Lexicographically k-th small string

The origin problem is here. Now it is deleted.

Suppose I have 3 'available' copies of a, 2 of b, 3 of c, and 4 of d.

1. I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
2. Is there an efficient (i.e. $o(k)$) algorithm for computing the $k$-th smallest string of length $l$ in lexicographic order?

For example, The first string of length 1 is a, the second string of length 3 is aab, the 5th string of length 5 is aaacc (following aaabb, aaabc, aaabd, and aaacb), etc.

What kind of algorithm or math can I use to calculate?

• Please do not cross-post. If you have decided to move your question from Math it should be migrated or doing so manually you should delete the previous one. – Evil Oct 25 '16 at 16:26
• It's midnight in China, I will close the origin problem at math tomorrow. By the way, k=1 the answer is 4, k=2 the answer is 16, k=3 the answer is 63(except bbb). – mickeyandkaka Oct 25 '16 at 16:38
• @Evil It certainly shouldn't be $k-th$, since that denotes the difference between $k$ and the product of $t$ and $h$. To be honest, I'd typeset it as just $k$th -- one doesn't use a hyphen in "4th", for example. – David Richerby Oct 25 '16 at 20:26
• Cross-posted: cs.stackexchange.com/q/65110/755, math.stackexchange.com/q/1984522/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Oct 25 '16 at 21:50
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Oct 25 '16 at 22:24

You are asking two questions. The first is an enumeration question, and the second is about generation or encoding/decoding. The enumeration question is a standard combinatorial exercise, which can be solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your example is $\ell!$ times the coefficient of $x^\ell$ in the exponential generating function $$\left(1 + x + \frac{x^2}{2!}\right) \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)^2 \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right).$$

For the generation problem, the idea is as follows. Suppose that we want the $k$th lexciographically smallest string of length $\ell$. We will uncover the letters one by one. To find the first letter, we count how many strings of length $\ell$ start with each letter—an instance of the enumeration problem mentioned above—and use this information to determine the first letter. We find the subsequent letters in a very similar way.