×

Scattered subwords and composition of natural numbers. (English) Zbl 1307.68061

Summary: Special scattered subwords in which the length of the gaps are bounded by two natural numbers are considered. For rainbow words the number of such scattered subwords is equal to the number of special restricted compositions of natural numbers in which the components are natural numbers from a given interval. Linear algorithms to compute such numbers are given. We also introduce the concepts of generalized scattered subword (duplex-subword) and generalized composition.

MSC:

68R15 Combinatorics on words
05A17 Combinatorial aspects of partitions of integers
05A05 Permutations, words, matrices
PDFBibTeX XMLCite

Online Encyclopedia of Integer Sequences:

a(n) = n(a(n-1) + 1), a(0) = 0.