Independently prescribable sets of n-letter words
type: Item
instance of: scholarly article
title: Independently prescribable sets of n-letter words
zbMATH Open document ID: 0595.05047
DOI: 10.1016/0012-365X(84)90048-7
author: Judith E. Dayhoff
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: 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.
reviewed by: Nikolai L. Manev
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 94C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3957155
zbMATH Keywords: n-letter words
zbMATH Keywords: de Bruijn sequences
zbMATH Keywords: sets of edges of Hamiltonian graphs
MaRDI profile type: Publication
cites work: Normal Recurring Decimals
cites work: Q5808057
description: scientific article; zbMATH DE number 3957155