Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Are the sets of numbers which correspond to the symbols always $\lbrace 0, 1, ..., n\rbrace$? –  Douglas Zare Aug 5 '12 at 15:30
1  
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. –  Philippe Nadeau Aug 5 '12 at 15:59
    
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} –  Flavio Aug 5 '12 at 16:08
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
    
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 –  Gerhard Paseman Aug 5 '12 at 20:52
1  
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 –  Gerhard Paseman Aug 5 '12 at 23:10
    
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. –  Will Sawin Aug 6 '12 at 3:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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