Independently prescribable sets of n-letter words (Q1077431): Difference between revisions

The author considers sets of n-letter independently prescribed words. (A set of words \(\{A_ 1,A_ 2,...,A_ t\}\) is said to be independently prescribed if for every set of nonnegative integers \(v_ i\) \((i=1,2,...,t)\), there exists a word S containing exactly \(v_ i\) occurrences of \(A_ i\) \((i=1,...,t).)\) He shows that the maximum size for an independently prescribable n-letter set is \(q^ n-q^{n-1}\), where q is the number letters in the alphabet. Let F(n,q) denote a number of different independently prescribable n-letter sets of maximum cardinality \(q^ n-q^{n-1}\) on an alphabet of q letters. It is proved in this paper that \[ F(n,q)=B(n-1,q)\quad if\quad q>2\quad and\quad (n,q)\neq (2,3),\quad and\quad F(n,q)=7B(n-1,q)\quad if\quad q=2,\quad n\geq 5, \] where \(B(n-1,q)=\) the number of (n-1)-de Bruijn sequences. Some of the results are generalized in a theorem about independently prescribable sets of edges of Hamiltonian graphs.