

A259553


Number of distinct (n!)tuples, with integer entries between 0 and n, inclusive, where entries measure the length of the longest prefix of each of the n! permutations of 123...n that is a subsequence of some string over the alphabet {1,2,3,...n}.


0




OFFSET

1,1


COMMENTS

This sequence is an upper bound on A259482. (It is only an upper bound because two such ntuples might be "equivalent" in the sense of the MyhillNerode theorem.) The length of the shortest string corresponding to (n,n,...,n) is given by A062714.


LINKS

Table of n, a(n) for n=1..4.


EXAMPLE

For n = 2, where the permutations are 12 and 21, the six possible 2tuples are (0,0) (corresponding to the empty string); (1,0) (corresponding to 1); (0,1) (corresponding to 2); (2,1) (corresponding to 12); (1,2) (corresponding to 21); (2,2) (corresponding to 121).


CROSSREFS

Cf. A062714, A259482.
Sequence in context: A277477 A277363 A156340 * A327425 A262046 A280982
Adjacent sequences: A259550 A259551 A259552 * A259554 A259555 A259556


KEYWORD

nonn,more


AUTHOR

Jeffrey Shallit, Jun 30 2015


STATUS

approved



