zbMATH — the first resource for mathematics

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.
68R15 Combinatorics on words
05A17 Combinatorial aspects of partitions of integers
05A05 Permutations, words, matrices