How many legal permutations are there of D&D ability score results?

Question

In Dungeons and Dragons 3.5 edition, ability score generation results in 6 values, each of which is between 3 and 18 (inclusive). They can repeat. Each score is accompanied by an ability score modifier, which is equal to 0.5*(ability score-10), rounded down. (Note: if using a spreadsheet program, rounding down negative numbers gets tricky; I instead use ((score-IF(ISODD(score),11,10))/2)).

The number of permutations of these scores is not difficult to calculate: there are 16 valid scores, they can repeat, and 6 items selected, so that yields 16^6 permutations. However, D&D 3.5e puts two additional limits on what constitutes a legal score set for a playable character.

1) At least one score must be 13 or higher, before any adjustments from other aspects of character creation are applied.

2) The sum of the ability modifiers must be +1 or better, again before any adjustments from other aspects of character creation are applied.

Again, 1) is easy enough to solve: subtract all permutations where no score is 13 or higher (10^6) from the initial result. It's 2) that's giving me problems, because I can't see how to solve it without brute-forcing it, and that's a LOT of permutations to brute-force.

Answer 1

Note that the ability score modifiers are symmetric around $0$ – they range from $-4$ to $+4$, with each value occurring twice except $\pm4$ each only occurring once. You want the sum to be positive, so we can take half the total $16^6$ and subtract half the number of score sets with ability score modifier sum $0$.

These would be straightforward to count if every ability score modifier occurred the same number of times. Since $-4$ and $+4$ occur only once, we need to treat them separately. Denote the number of $-4$s by $k$ and the number of $+4$s by $l$. There can be at most $3$ of each. Shift all modifiers up by $4$, so they now range from $0$ to $8$ and need to sum to $24$. Then we have $24-8l$ points to distribute over $6-k-l$ bins with capacity $1$ to $7$, or equivalently $(24-8l)-(6-k-l)=18-7l+k$ points over $6-k-l$ bins with capacity $0$ to $6$.

As discussed at Balls In Bins With Limited Capacity, this can be done in

$$ \sum_{t=0}^{6-k-l}(-1)^t\binom{6-k-l}t\binom{6-k-l+18-7l+k-7t-1}{6-k-l-1} $$

ways (where, contrary to the usual convention, the binomial coefficients are taken to be zero if the upper index is negative while the lower index is positive). This we have to multiply by $2^{6-k-l}$ (since each modifier except $-4$ and $+4$ can occur in two different ways) and $\binom6{6-k-l,k,l}$ (the number of choices for the $k$ and $l$ special bins), and sum over $k$ and $l$.

Thus, the number of score sets whose ability score modifiers sum to $0$ is

\begin{eqnarray} && \sum_{k=0}^3\sum_{l=0}^32^{6-k-l}\binom6{6-k-l,k,l}\sum_{t=0}^{6-k-l}(-1)^t\binom{6-k-l}t\binom{6-k-l+18-7l+k-7t-1}{6-k-l-1} \\ &=& 2^6\binom6{6,0,0}\left(\binom60\binom{23}5-\binom61\binom{16}5+\binom62\binom95\right)\\ &&+2^5\binom6{5,1,0}\left(\binom50\binom{23}4-\binom51\binom{16}4+\binom52\binom94\right)\\ &&+2^4\binom6{4,2,0}\left(\binom40\binom{23}3-\binom41\binom{16}3+\binom42\binom93\right)\\ &&+2^3\binom6{3,3,0}\left(\binom30\binom{23}2-\binom31\binom{16}2+\binom32\binom92-\binom33\binom22\right)\\ &&+2^5\binom6{5,0,1}\left(\binom50\binom{15}4-\binom51\binom84\right)+2^4\binom6{4,1,1}\left(\binom40\binom{15}3-\binom41\binom83\right)\\ &&+2^3\binom6{3,2,1}\left(\binom30\binom{15}2-\binom31\binom82\right)+2^2\binom6{2,3,1}\left(\binom20\binom{15}1-\binom21\binom81+\binom22\binom11\right)\\ &&+2^4\binom6{4,0,2}\binom40\binom73+2^3\binom6{3,1,2}\binom30\binom72\\ &&+2^2\binom6{2,2,2}\binom20\binom71+2^1\binom6{1,3,2}\left(\binom10\binom70-\binom11\binom00\right)\\ &&+2^0\binom6{0,3,3}\binom{-1}{-1} \\ &=& 1137324\;, \end{eqnarray}

so the number of score sets whose ability score modifiers sum to more than $0$ is

$$ \frac{16^6-1137324}2=7819946\;. $$

We’ve already subtracted most of the $10^6$ score sets that have no score of $13$ or higher, since they typically have negative modifiers; we just have to count the few that have a positive modifier sum. This can only arise from $12$s, so we have to sum over the number $m$ of $12$s. Then we can distribute up to $m-1$ negative modifier points to the $6-m$ remaining bins. Distributing up to $n$ (rather than exactly $n$) balls to $b$ bins can be achieved by introducing an extra bin that receives the unused balls, so there are $\binom{n+b}b=\binom{m-1+6-m}{6-m}=\binom{6-1}{m-1}$ such distributions. Let’s first ignore the fact that $-4$ only corresponds to one score, so we include a factor $2^{6-m}$ for two scores per modifier value. Then the count is

$$ \sum_{m=1}^62^{6-m}\binom6m\binom{6-1}{m-1}=3653\;. $$

Now we need to subtract from that the number of cases that were double-counted because they include a $-4$. There are just $6$ of those, since a $-4$ can only occur together with five $+1$s.

Thus, in total there are

$$ 7819946-(3653-6)=7816299 $$

different admissible score sets, in agreement with Alex S' result. (I also wrote Java code to check the results; it runs in about a second on my laptop.)

Answer 2

Partial Answer.

Here ia python script which runs fairly quickly to brute-force an answer of $7,816,299$.

from math import floor
from time import time

count=0
t1=time();
for a1 in range(3,19):
    for a2 in range(3,19):
        for a3 in range(3,19):
            for a4 in range(3,19):
                for a5 in range(3,19):
                    for a6 in range(3,19):
                        stats=[a1,a2,a3,a4,a5,a6]
                        max_stat=max(stats)
                        net_bonus=sum([floor((score-10)/2) for score in stats])
                        if max_stat>=13 and net_bonus>=1:
                            count+=1
t2=time()
print('allowed stat permutations: '+str(count))
print('computation time: '+str(t2-t1))