First, Willess, thanks for one of the best laughs I've had in a while. XD
I think I figured out your thought process. Let me know if this rings a bell:
First, I'm going to clean up the formula a bit, and remove some of the unnecessary brackets, while still keeping the "structure", so that it's easier to refer back to:
n^4 + 3n(n-1) - n - 4n(n-1) - 6n(n-1) - 12n(n(n-1)/2 - (n-1))
You start out by allowing anything, including repeated elements, i.e. strings like "1 1 1 1". That's the n^4. Then you need to subtract all the different ways you can make strings with such repetition.
The first case is easy. There are n ways to make strings where all 4 characters are the same. "1 1 1 1", "2 2 2 2", …, "n n n n". Hence, we have the "-n" in the formula above.
Then you subtract the number of ways you can make strings with exactly 3 repetitions, e.g. "7 7 5 7". This is the "-4n(n-1)"; n ways to choose the repeating element, n-1 ways to choose the single element, 4 ways to place the single element into the string.
Then, the number of ways to make exactly one pair. I.e. strings like "1 1 2 3", but not "1 1 2 2". There are choose(4,2)*n(n-1)(n-2) = 6n(n-1)(n-2) ways to do this, which ends up being equivalent to the 12n(n(n-1)/2 - (n-1)) in the formula. So, how did you come up with this 12n(…) form? My best guess is the following:
* You knew there were 6 ways to choose the location for the "pair" elements.
* 2 ways to order the remaining elements
* n ways to choose the repeated element
* choose(n-1,2) ways to pick the last element. How did choose(n-1,2) end up being n(n-1)/2 - (n-1)? My best guess: You pretended you had n elements, and chose 2 from those, then subtracted the (n-1) possible cases that would have been invalidated by picking the repeated element as one of your choices.
Anyway, subtract this 12n(…) thing you and you remove the cases with exactly 1 pair.
That leaves the last case of repetition: two pairs, e.g. "1 1 2 2". This is the guess I feel less comfortable about, since the two portions are so spread apart in your formula. But if you combine them, the 3n(n-1) - 6n(n-1) = -3n(n-1) represents removing the cases with exactly 2 pairs; n ways to pick the first element, n-1 for the second, and choose(4,2)/2 = 6/2 = 3 ways to order the elements.
Having removed all of the invalid cases, you have your pick(n,4). Let me know what you think.
If so, may I suggest the slight modification: "I think I'm hitting the supremum of what I can do here"