Title: A new approach for counting patterns in language theory, matchings, and set partitions

Authors: Fatima Hessas; Mouloud Goubi; Noria Benkhemmou

Addresses: Department of Mathematics, Faculty of Sciences, University Mouloud Mammeri of Tizi-Ouzou, Tizi Ouzou, Algeria; Laboratory of Pure and Applied Mathematics (LMPA), Algeria ' Department of Mathematics, Faculty of Sciences, University Mouloud Mammeri of Tizi-Ouzou, Tizi Ouzou, Algeria; Laboratory of Algebra and Number Theory (LATN), USTHB Algiers, Bab Ezzouar, Algeria; Laboratory of Pure and Applied Mathematics (LMPA), Algeria ' Department of Mathematics, Faculty of Sciences, University Mouloud Mammeri of Tizi-Ouzou, Tizi Ouzou, Algeria; Laboratory of Pure and Applied Mathematics (LMPA), Algeria

Abstract: The notion of pattern is widely studied in the literature. We focus our attention on patterns appearing in language theory, matchings, and set partitions. We start with some main tools of algebraic generating functions of sequences of numbers. We explain how the Bell, Fibonacci and generalised Fibonacci numbers can be used in the theory of patterns. In particular, we are interested in words containing patterns that are related to arbitrary length so as to provide enumeration formulae, and extract satisfying recurrence relations. Moreover, we revisit the work of Bloom and Elizalde concerning pattern avoidance in matchings and partitions in order to fulfil it with some enumeration formulae.

Keywords: language theory; patterns; generating functions; matchings; set partitions.

DOI: 10.1504/IJMOR.2025.149922

International Journal of Mathematics in Operational Research, 2025 Vol.32 No.3, pp.426 - 442

Received: 20 Dec 2023
Accepted: 28 Dec 2023
Published online: 18 Nov 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article