Count good sets with given conditions We need to find the numbers of good sets in a sequence. The good set is:

A good set is a sequence of $P$ positive integers which satisfies the following 2 condition :


If an integer $L$ appears in a sequence then $L-1$ should also appear in the sequence
The first occurrence of $L-1$ comes before the last occurrence of $L$


Example : Let $P=3$ then answer is $6$

Explanation : The total number of output sets are $6$

One of the solution set is: 

[1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,2], [1,2,3]


For [$1,2,3$]= The first occurrence of $1$ comes before the last occurrence of $2$ and the last occurrence of $3$.
Here's one way to attack it:

Let $P(n)$ denote the number of good tuples of length $n$. Claim: $P(n) = n!$. Here is a  proof sketch using induction on $n$.

$P(1) = 1$, OK. Suppose it's true up to and including $n-1$. You can map each of the $(n-1)!$ good tuples of length $n-1$ to a unique good $n$-tuple as follows:

Let $\mathbf{x} = (x_1, \ldots, x_{n-1})$ be a good tuple. For each $i=1,2,\ldots, n$ we augment $\mathbf{x}$ to $(x_1, \ldots, x_{i-1}, x*, x_i, \ldots, x_{n-1})$ by setting $x^*$ to be the largest value in $\{1,2,\ldots, n\}$ that keeps $(x_1, \ldots, x_{i-1}, x*, x_i, \ldots, x_{n-1})$ good.

For example:

$(1,1)$ gives 3 good tuples: $(\underline{1}, 1, 1), (1, \underline{2}, 1), (1,1,\underline{2}) $.

$(1,2)$ gives 3 good tuples: $(\underline{2}, 1, 2), (1, \underline{2}, 2), (1,2,\underline{3})$.

The extra bookkeeping is to: 


show that these mappings are indeed good
show that these mappings are unique
show that if an $n$-tuple is not produced by this mapping, then it is not good


Here are the 24 good $4$-tuples that I found:


  [1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 2, 1] [1, 1, 2, 2] [1, 1, 2, 3] [1,
  2, 1, 1] [1, 2, 1, 2] [1, 2, 1, 3] [1, 2, 2, 1] [1, 2, 2, 2] [1, 2, 2,
  3] [1, 2, 3, 1] [1, 2, 3, 2] [1, 2, 3, 3] [1, 2, 3, 4] [1, 3, 2, 3]
  [2, 1, 1, 2] [2, 1, 2, 1] [2, 1, 2, 2] [2, 1, 2, 3] [2, 1, 3, 2] [2,
  2, 1, 2] [2, 3, 1, 2] [3, 1, 2, 3]
When P=1, there is 1 good set.

[1]


When P=2, there are 2 good sets.

[1,1] and [1,2]


When P=3, there are 6 good sets.

[1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,2], [1,2,3]


This pattern looks like it might be P!

Check if there are 4! = 24 sets for P = 4.

[1,1,1,1] ... [1,2,3,4]