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$.

  • $\begingroup$ 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$? $\endgroup$ – Ross Millikan Apr 19 '19 at 18:23
  • $\begingroup$ Do you mean integer digits or integers? The way the question is raised the answer is infinity. $\endgroup$ – Joker123 Apr 19 '19 at 18:27
  • 2
    $\begingroup$ @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. $\endgroup$ – Mike Earnest Apr 19 '19 at 18:28
  • $\begingroup$ $$\sum k^{n-k} \binom nk$$ $\endgroup$ – Matt Samuel Apr 19 '19 at 18:41
  • $\begingroup$ @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$ $\endgroup$ – Ross Millikan Apr 19 '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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.