context: trying to solve a problem where I want to know how many possibilities there are in a registration plate.
I know that if I want to calculate every possible scenario I'd do: (number of places)^(letters+digits)
but how can I calculate this if there are restrictions such as "character B and character 8 aren't allowed to be next to each other"
to elaborate upon the rules:
[XXB8X] - isn't allowed
[BB8BX] - isn't allowed
[X8XBX] - is allowed
Suppose our alphabet has $T$ characters, among them $X,Y$ (distinct), and our constraint is that our registration plates cannot contain the sequence $XY$. Define $N(T,n)$ to be the number of viable registration plates of length $n$. We will derive a close form for these numbers:
$$N(T,n) = \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor} (-1)^i {{n-i}\choose{i}} T^{n-2i}$$
One way to do this comes from algebraic combinatorics: we think of the registration plates as words which we can feed to a finite automaton one letter at a time. We will create a finite automaton which is able to understand exactly the valid registration plates, and then use a standard technique to produce a generating function encoding the number of such plates as its coefficients.
This will allow us to generalize the problem to any length of registration plate and any size alphabet with no additional work.
It will also give you a good starting point if you want to examine more complicated constraints on registration plates, which can be attacked by updating the automaton accordingly.
We build an automaton that has two states, which we'll call the $X$ state and the Free state.
The $X$ state is where we have the restriction that we can't place a $Y$, and the free state is such that we can place anything.
There are $T-2$ ways to get from the $X$ state to the Free state (all but $Y$ or $X$), and exactly $1$ way to get from the $X$ state to itself (put down another $X$).
Similarly there are $T-1$ ways to get from the Free state to itself, and $1$ way to get to the $X$ state.
If you start in the Free state, then the number of acceptable registration plates of length $n$ is the number of different paths of length $n$ that you can take by traversing the arrows one at a time.
Here's a schematic:
I will not attempt to explain the whole theory here, but rather point you to the wonderful book of Flajolet if you want to learn more about algebraic combinatorics (and in particular search for 'finite automata' in chapter I).
For our problem let us denote the generating function for the free state by $L_F(z)$, and that for the $X$ state by $L_X(z)$.
We have the system of equation
$$L_F(z) = zL_X(z) + (T-1)zL_F(z) + 1$$ $$L_X(z) = zL_X(z) + (T-2)zL_F(z) + 1$$
We solve for $L_F$, since we begin in the free state.
Subtracting the equations we find $$L_X(z) = (1-z)L_F(z)$$ and substituting into the first equation we have
$$L_F(z) - z(1-z)L_F(z) - (T-1)zL_F(z) = 1 \implies$$
$$L_F(z) = \frac{1}{z^2 - Tz + 1}$$
Now the coefficient of $z^n$ in the power series $L_F(z)$ counts $N(T,n)$, the number length $n$ registration plates in $T$ characters that don't contain a particular string $XY$ for some distinct characters $X,Y$.
We can now make use of a variety of techniques to fashion explicit formulas for these numbers. In fact they are given by evaluating Chebyshev polynomials of the second kind (the world of combinatorics is small!!) and an explicit formula is given by
$$N(T,n) = \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor} (-1)^i {{n-i}\choose{i}} T^{n-2i}$$