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. What is the origin of this problem?