Find the permutation of sequence? (not the usual counting problem)

Question

In given array [1, 2, 3], find the permutation of sequence for given size N, Here is condition each element from the array should be occurs at least one time in sequence.

For N = 3, [1, 2, 3] result = 6 {1, 2, 3}, {1, 3, 2}, {3, 2, 1}, {3, 1, 2}, {2, 3, 1}, {2, 1, 3}

For N = 4, Here length of sequence is 4, now as given condition {1, 2, 3} will occurs at least one time, {1, 2, 3, {1 or 2 or 3}} result will be 36. {1, 1, 2, 3}, {1, 2, 1, 3}, {1, 2, 3, 1}, {1, 2, 2, 3}, {1, 2, 3, 2}, {2, 1, 2, 3},.... till count 36.

Please tell me how to find the permutation of given size N >=3.

---

Edit by not the OP: If I understand the question, here's a statement in more standard mathematical terms.

Given an $N$-element set $S$ count the ordered sequences of elements of $S$ of length $M \ge N$ that contain each element of $S$ at least once. When $M=N$ these are just the permutations, and there are $N!$ of them.

Answer 1

Use inclusion/exclusion principle:

• Include the number of permutations containing at most $\color\red3$ values: $\binom{3}{\color\red3}\cdot\color\red3^N=3^N$
• Exclude the number of permutations containing at most $\color\red2$ values: $\binom{3}{\color\red2}\cdot\color\red2^N=3\cdot2^N$
• Include the number of permutations containing at most $\color\red1$ value: $\binom{3}{\color\red1}\cdot\color\red1^N=3$

The answer is therefore $3^N-3\cdot2^N+3$.