If I’m correct, the graph traversal solution is pretty straightforward: you may traverse the graph with recursive function memorizing only current “left” symbols and last used one.

1. let there be a function f of input (key-value pairs, where keys are 1..4; values are n1..n4) and p – last used number, and p is initially undefined
2. in a loop, if input[i] > 0 and i != p, where i is a key
   1. add 1 to result, because you found another solution, 1 symbol longer
   2. set inputUpd := input (copy for recursive call)
   3. decrement inputUpd[i], because we’ve just used symbol i and there is one such symbol less left
   4. set p := i, because we’ve just used i
   5. add the value of f(inputUpd, p) (recursive call with “smaller” input and last used symbol) to result

I couldn’t help myself, so here is the code in JS. Skip it if you want to figure out the solution yourself.

function f(input, prev) {
  var acc = 0;
  for (i in input) {
    if (i != prev && input[i] > 0) {
      var inputUpd = {};
      for (j in input) {
        inputUpd[j] = (j == i) ? (input[j] - 1) : input[j];
      }
      acc += 1 + f(inputUpd, i);
    }
  }
  return acc;
}

f({'1': 1, '2': 1}) // -> 4: [1], [2], [1,2], [2,1]
f({'1': 1, '2': 2}) // -> 5: [1], [2], [1,2], [2,1], [2,1,2]
f({'1': 1, '2': 3}) // -> 5: same as before, but single `2` is leftover
f({'1': 1, '2': 1, '3': 2, '4': 2}) // -> 288