2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Are the sets of numbers which correspond to the symbols always $\lbrace 0, 1, ..., n\rbrace$? $\endgroup$ Aug 5, 2012 at 15:30
  • 1
    $\begingroup$ To add on the previous comment, in this case you would obtain parking functions counted by $n^{n-2}$ (for $n+1$ symbols) if I'm not mistaken. $\endgroup$ Aug 5, 2012 at 15:59
  • $\begingroup$ Yes they are. Each symbol is a set of the first n non-negative integers, where n can be any natural number and is independent from any set. For instance a={0,1,...,12} b={0,1,...,153} c={0,1,...,43} $\endgroup$
    – Flavio
    Aug 5, 2012 at 16:08

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Now that I have read the comments, I believe the question to be a near duplicate of similar questions asked on MathOverflow. I will post a link later if noone else does. My hazy recollection suggests time still exponential or superexponential. Gerhard "Ask Me About System Design" Paseman, 2012.08.05 $\endgroup$ Aug 5, 2012 at 20:52
  • 1
    $\begingroup$ Found it. mathoverflow.net/questions/83714/combination-and-probability . Not quite a duplicate, but you might find it and the links mentioned therein worth pursuing. Gerhard "Ask Me About System Design" Paseman, 2012.08.05 $\endgroup$ Aug 5, 2012 at 23:10
  • $\begingroup$ Computing it is significantly easier than listing. For instance, if there is no overlap, the time is $n!$ times the product of the number of values of each symbol. That's not that hard to compute. $\endgroup$
    – Will Sawin
    Aug 6, 2012 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.