count permutations that do not contain repeated combinations I am trying to count the number of permutations that do not contain order specific groupings that have occurred in permutations that have already been counted.
Example: For the set {A B C D E}; if you count the first permutation as ABCDE, then no other counted permutations could include "AB", "BC", "CD", or "DE". However, they could include "BA", "CB", "DC", or "ED". So EDCBA would be counted, while CEABD would not be counted.
I apologize if I explained that poorly. Beyond knowing what a permutation is and knowing the counting principle, I have essentially no background in the formalized math that is applicable to my question.
My goal is to find the number of possible ways 16 objects can be arranged that satisfies the stated restriction. Doing this count by hand would be tedious and prone to errors, so i am hoping there is some sort of formula.
 A: Let's say the set $S$ consists of $n$ elements.  
In each permutation, there are $n-1$ consecutive pairs of elements. On the other hand, ordered pairs can be chosen from $S$ in $P^n_2=\frac{n!}{(n-2)!}=n(n-1)$ ways.
Hence, there are at most $\frac{n(n-1)}{n-1}=n$ possible permutations with no consecutive pairs repeated. To prove this maximal number can be realised (or not) is more difficult.
I have a suspicion that it is easier to achieve the full number of permutations if $n$ is even (e.g. $n=16$) as opposed to odd (e.g. $n=5$), as one can then pair one permutation with its reverse.
For example, with $n=4$:
$$\begin{array}{cc}
A & B & C & D \\ 
D & C & B & A \\ 
B & D & A & C \\ 
C & A & D & B  
\end{array}$$
gives the full four permutations with no adjacent pairs repeated.
It can be shown fairly easily that it is not possible for form the full three permutations when $n=3$.  
A: This is equivalent to the maximum number of edge-disjoint Hamilton paths in a complete graph with n vertices, since a Hamilton path gives a permutation of graph vertices and also the paths are edge-disjoint so there are no repeated pairs.
For cyclic permutations the answer is this:
Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.
https://mathoverflow.net/questions/197781/how-many-hamiltonian-paths-can-be-removed-from-a-complete-directed-graph-before
An algorithm to find it:
http://arxiv.org/abs/1202.6219
