login
A108713
Number of possible canonical minimal transition-complete sequences over n objects.
1
1, 1, 3, 128, 162000, 10319560704, 50185433088000000, 26294650153960734720000000, 1991323677312505284928104038400000000, 28163375844474584946472694002483200000000000000000
OFFSET
1,3
COMMENTS
Definition of a canonical minimal transition-complete sequence, by example: If n=3, then 2123132312132312 is a transition-complete sequence because each element (1,2, or 3) is followed by each other element at least once.
3132123 is a minimal transition complete sequence, as each element is followed by each other element EXACTLY once.
1231321 is a canonical minimal transition-complete sequence because 1 appears before the first appearance of 2 and 2 appears before the first appearance of 3.
FORMULA
For n > 1, a(n) = n^(n-2) * (n-2)!^(n-1). This is the number of Eulerian circuits in the complete directed graph on the vertices 1,2,...,n (starting with an arc (1,2)) divided by (n-2)! (the number of relabelings of the vertices 3,4,...,n). - Max Alekseyev, Feb 06 2010
EXAMPLE
With n=1, there is only the possibility "1".
With n=2, there is only the possibility "121".
With n=3, there are the following 3 possibilities: "1213231", "1231321" and "1232131".
Here is one of the 128 possibilities with n=4: "1231342143241".
With n=5, I think there are over 120000 possibilities and at n=6 there may be a large number.
MATHEMATICA
Join[{1}, Table[n^(n-2) ((n-2)!)^(n-1), {n, 2, 10}]] (* Harvey P. Dale, Dec 29 2013 *)
CROSSREFS
Sequence in context: A258671 A243213 A264582 * A319222 A300543 A300970
KEYWORD
nonn,nice
AUTHOR
Philipp G. Blume (pgblu(AT)hotmail.com), Jun 20 2005
EXTENSIONS
Terms a(5) onwards from Max Alekseyev, Feb 06 2010
STATUS
approved