String possible combinations

Question

Assume a string of four symbols, for example s=abcd. Consider only those strings with exactly one instance of each symbol, such that s=bacd and s=dacb are both valid strings but s=aabc is not. This gives 4! possible combinations.

Now, each symbol can take a value among

a = [0, 1] b = [0, 1, 2, 3] c = [0, 1] d = [0, 1, 2]

Consequently I may end up having s=cdab=0112 or s=abcd=0000 or s=abdc=1320 etc..

I wish to compute how many combinations (no repetitions) can string s take.

I have written an algorithm that probes all different combinations and discards duplicates, but I would like to understand if a formula can be constructed that returs the same result (not the list of all valid combinatins, but only the number of them).

Here is a practical example: If I have 3 symbols a=[0] b=[0,1] c=[0,1,2] and s=abc, then possible combinations for s are (000,001,002,010,011,012). For s=acb you have (000,001,010,011,020,021) and so forth. You discard the duplicates and (in this example) are left with 16 combinations (000,001,002,010,011,012,020,021,100,101,102,110,120,200,201,210). I have found an algorithm that runs in O(n!) (in this example 3!), but I was wondering whether O(n) or O(1) is feasible.

Thank you

Answer 1

Here is a recursive algorithm of complexity $O(n^2 m)$ where there are $n$ symbols and the largest set of values replacing a symbol is $\lbrace 0, 1, ..., m-1 \rbrace$.

Let $m_i$ be the number of values replacing the $i$th symbol, $0\le i \lt n$. Without loss of generality, assume the $m_i$ are nondecreasing.

Define $f(a,b)$ be the number of distinct ways of ordering and replacing the last $a$ symbols so that each value is at least $b$. We want to compute $f(n,0)$.

If $m_0 = 0$ then $f(n,0)=0$ since there are no possible replacements. Otherwise, if we choose the number of $0$s to be z, then there are $n \choose z$ ways to place the $0$s, and there are $f(n-z,1)$ ways to choose the other symbols. So, $f(n,0) = \sum_z {n \choose z} f(n-z,1)$. More generally, if $m_{n-a} \le b$ then $f(a,b)=0$, otherwise

$$f(a,b) = \sum_{z=0}^a {a\choose z} f(a-z,b+1).$$

At the base of the recursion, $f(0,b)=1$.

Here is some Mathematica code which implements this with some examples.

Clear[rec];
rec[a_, b_, mVec_] := rec[a, b, mVec] = 
   If[a == 0, 1, 
      If[mVec[[Length[mVec] - a + 1]] <= b, 0, 
         Sum[Binomial[a, z] rec[a - z, b + 1, mVec], {z, 0, a}]
        ]
     ]
rec[3, 0, {3, 3, 3}]
   27
rec[3, 0, {1, 2, 3}]
   16
rec[4, 0, {1, 2, 3, 4}]
   125
Timing[rec[20, 0, {12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50}]]
{0.031, 4822195074448408017997909570093056}

That last value is $2^{40}\times 3 \times 13^{19} = 12\times(52)^{19}$. There is a nice factorization when the $m_i$ are in an arithmetic progression which follows from the recursion.

---

Edit: The pattern above is in Stanley, Enumerative Combinatorics Volume 2, see Ex. 5.49.

Yuan, "On the Enumeration of Generalized Parking Functions" considered the OP's problem and proved some more general formulas where the maximums $m_i$ are a join of two linear functions, either $\lbrace a, a+b, a+2b, ... a+kb, m, m, m, ...m\rbrace$ or $\lbrace a, a+b, a+2b , ... a+kb, a+kb+c, a+kb+2c , ... \rbrace$ in my notation. These counts are single sums. It looks like the same techniques would express joins of more linear functions at the expense of iterated summation.

Answer 2

If there is a lot of overlap, it may be possible to get a faster algorithm, but I doubt it. If each set has one symbol that is not in the other sets, that alone will get you n! possibilities itself. If you can tell us more about the sets, we might be able to improve upon your implementation.

Gerhard "Ask Me About System Design" Paseman, 2012.08.05