# Counting number of combinatorial sequences.

Let $$n$$ be a positive natural number. A sequence of $$n$$ positive positive integers (not necessarily distinct) is called a ”four-group” sequence if it satisfies the following requirements: for any natural $$k \geq 2$$, if $$k$$ occurs in this sequence, then $$k − 1$$ occurs, and the first position at which the number $$k − 1$$ occurs, is earlier than the last position where the number $$k$$ occurs. Find the number of ”four-group” sequences of length $$n$$.

• What have you tried? Have you listed them for small $n$? What is the greatest number that can occur in a sequence of length $n$? – Ross Millikan Apr 19 at 18:23
• Do you mean integer digits or integers? The way the question is raised the answer is infinity. – Joker123 Apr 19 at 18:27
• @Joker123 The rules imply that only integers between $1$ and $n$ can occur in the the sequence (if $n+1$ appeared, then so would $n$, and therefore also $n-1$, and so on down to $1$, which is too many numbers). Therefore, there are at most $n^n$ sequences. – Mike Earnest Apr 19 at 18:28
• $$\sum k^{n-k} \binom nk$$ – Matt Samuel Apr 19 at 18:41
• @MattSamuel: I don't see why it should be that. Presumably $k$ is the highest number in the sequence. If $k=2$ we count all strings of $1$s and $2$s except those where all the $2$s precede all the $1$s (and those with just one number present), so there are $2^n-n-1$ – Ross Millikan Apr 19 at 19:03

There are $$n!$$ four-group sequences of length $$n$$.
Here is a bijection between FGS's and permutations. Given a permutation of length $$n$$, partition it into maximal decreasing consecutive subsequences. For example, with $$\pi=[\pi_1,\pi_2,\dots,\pi_{n}]$$ in one-line notation, and $$n=10$$, $$[7,5,2,1, 3,10,6,9,8,4]\implies 7,5,2,1\def\div{\;\Big|\;}\div3\div10,6\div9,8,4$$ To make the FGS corresponding to this permutation, we place a $$1$$ at each index in the first subsequence (at spots $$7,5,2$$ and $$1$$), we place a $$2$$ at each index in the second decreasing subsequence (at spot $$3$$), and in general place the number $$k$$ at each position appearing in the $$k^{th}$$ block. The result in this example is $$1, 1, 2, 4, 1, 3, 1, 4, 4, 3$$ Note that the set of numbers appearing will always be a consecutive interval of integers containing $$1$$. Furthermore, the maximality of the decreasing subsequences implies that the first instance of $$k-1$$ is before the last instance of $$k$$, for each $$k$$.
The inverse map is as follows. Given an FGS, arrange the indices of the appearances of $$1$$ in decreasing order, then append the indices of the appearances of $$2$$ in decreasing order, and so on. I leave it to you to verify these maps are inverse to each other.