2
$\begingroup$

Consider the set, $S$, of $n$-tuples defined inductively as follows:

  • $(1, 2, \ldots, n) \in S$
  • if $(x_1, x_2, \ldots, x_i, x_{i+1}, \ldots, x_n) \in S$, then $(x_{i+1}, \ldots, x_{n}, x_1, x_2, \ldots, x_{i}) \in S$

What is the name of these types of $n$-tuples?

Note, the $n$-tuple $(2, 4, 1, 3)$ demonstrates that $S$ is a strict subset of all permutations.

  • 0
    "Note the sequence ... subset of all permutations." consider the singleton, or the pair. Then $S$ is exactly all the permutations.2011-05-28
  • 0
    @zulon -- I am using parenthesis to express a sequence, so $(1, 2) \neq (2, 1)$.2011-05-28
  • 0
    @Asaf Karagila -- You are correct for $n = 1, 2, 3$ it is true that $S$ is the set of all permutations. But when $n \geq 4$, I believe it is a subset.2011-05-28
  • 0
    Some confusion seems to have arisen because the question uses the notation for permutations and originally said "permutations"; this has now been changed to "sequences" (except for one instance; this seems to be an oversight). Note that all comments above were made before this change. Also, in zulon's comment, $(3,4,2,1)$ should be $(3,4,1,2)$.2011-05-28
  • 1
    @dsg: You're using notation that's usually used for permutations and $n$-tuples; I think it would be clearer to refer to these things as $n$-tuples. Also, "inductively" is slightly misleading, since all elements of $S$ can be generated by a single application of the second rule with suitable $i$; subsequent applications just generate the same tuples again. I would call the tuples in $S$ the cyclic permutations of the tuple $(1,2,\dotsc,n)$.2011-05-28
  • 0
    @joriki -- Thank you, you're right. This is indeed a cyclic permutation. I think I am confused. I meant to ask about a different set, I tried to formalize it, but I think I lost something along the way.2011-05-28

1 Answers 1

4

These are cyclic permutations of the tuple $(1, 2, \ldots, n)$.

Thanks, @joriki.