1
$\begingroup$

The sequence $36278$ contains the sequence $327$ because $3$, $2$, and $7$ all occur in order in $36278$, regardless of other numbers in between. $543$ would not contain $45$ as $4$ and $5$ are in the wrong order.

How many ways are there to arrange the numbers $1-9$ so that the resulting sequence contains $123$, $456$, $789$, $147$, $258$, and $369$?

What is the smallest number of 3-digit sequences needed such that there is only exactly 1 permutation of 9 that contains all of them? Exactly 2 permutations? 4-digit sequences instead of 3?(Ex. If the permutation contains $123$, $345$, $567$, and $789$, it must be $123456789$)

$\endgroup$
  • $\begingroup$ Hard to see a general mode of attack. With the triples you give, unless I am being too hasty, it looks like the string must start with $1$ and must end with $89$. So...we're just down to six digits which need placement. The digit next to the $1$ can only be $2$ or $4$, and so on. That kind of reasoning should lead to an enumeration. As I say, it looks a bit unstructured. $\endgroup$ – lulu Feb 21 '18 at 1:49
2
$\begingroup$

For a sequence consisting of the numbers $1$ through $9$ each exactly once containing another sequence is equivalent to ordering constraints. For example, containing $123$ is equivalent to "$1 \prec 2$ and $2 \prec 3$". Such constraints can be visualized with a directed graph. (In cases where the constraints can all be satisfied, the graph must be acyclic.)

For the quoted question, the graph looks like this:

Graph with edges (1,2), (2,3), (4,5), (5,6), (7,8), (8,9), (1,4), (4,7), (2,5), (5,8), (3,6), and (6,9)

Counting the number of arrangements that satisfy the constraints is equivalent to counting topological orderings of the graph. The process of choosing such an ordering can be described by choosing a node that has no incoming edges, deleting it, and then repeating until the graph is empty. In general, however, counting the number of ways can be hard.

In this case, it is not too bad to count by hand and exploit some symmetry. (Maybe there is a more clever way, but I didn't see it yet.) We start with $1$, then go to either $2$ or $4$. Due to symmetry, the number of sequences that start with $12$ is that same as the number that start with $14$, so consider only $12$.

The next choice must be $3$ or $4$. There are only $5$ sequences that start with $123$: $$ \begin{array}{c} 123456789 \\ 123457689 \\ 123457869 \\ 123475689 \\ 123475869 \\ \end{array} $$

For sequences that start with $124$, the next choice must be either $3$, $5$, or $7$. For $1243$: $$ \begin{array}{c} 124356789 \\ 124357689 \\ 124357869 \\ 124375689 \\ 124375869 \\ \end{array} $$

$1247$ also has $5$ by symmetry. For $1245$: $$ \begin{array}{c} 124536789 \\ 124537689 \\ 124537869 \\ 124573689 \\ 124573869 \\ 124578369 \\ \end{array} $$

Thus the total is $2\cdot(5 + 2 \cdot 5 + 6) = 42$.

What is the smallest number of 3-digit sequences needed such that there is exactly 1 permutation of 9 that contains all of them?

If the graph has fewer than $8$ edges, then it must have at least two connected components, and each connected component has at least one digit that can start the permutation. So, to have only $1$ permutation, there must be at least $8$ edges. Each 3-digit sequence gives no more than $2$ edges, so $4$ sequences are required. (You have already given an example of this.)

Exactly 2 permutations?

Given a permutation, if there is not a constraint between two consecutive digits, those digits can be swapped, and no constraints will be violated. So if exactly two permutations are allowed, they must differ only by a swap of consecutive elements, as any other missing constraint between consecutive elements would admit another permutation.

We can still mostly argue by counting edges. (Note that none of the needed edges can come only from transitivity, as a transitive relation cannot describe directly adjacent elements of the permutation.) If the swap is at the beginning or end, only $8$ edges are needed, but overlapping prevents a solution with only $4$ 3-digit sequences. Otherwise, $9$ edges are needed, so still there must be $5$.

Examples: $$ \begin{array}{c} 134, 234, 456, 678, 789 \\ 124, 134, 456, 678, 789 \\ 123, 235, 245, 567, 789 \\ \end{array} $$

4-digit sequences instead of 3?

We can follow the same outlines as the previous arguments, but each 4-digit sequence can introduce $3$ edges instead of $2$. To specify exactly one permutation, we need $8$ edges, so at least $3$ 4-digits sequences. For example: $1234, 4567, 6789$.

To specify exactly two permutations, at least $3$ sequences are needed, and indeed $3$ suffice (but not for all swap positions): $1235, 2456, 6789$.

| cite | improve this answer | |
$\endgroup$

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