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$.
 A: 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]

A: 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]
