Computation of k-ary Lyndon Words Using Generating Functions and Their Differential Equations


Creative Commons License

Kucukoglu I., ŞİMŞEK Y.

FILOMAT, vol.32, no.10, pp.3455-3463, 2018 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 32 Issue: 10
  • Publication Date: 2018
  • Doi Number: 10.2298/fil1810455k
  • Journal Name: FILOMAT
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.3455-3463
  • Keywords: Lyndon words, Generating functions, Ordinary differential equations, Apostol-Bernoulli numbers and polynomials, Stirling numbers, Algorithm, EULER POLYNOMIALS, Q-EXTENSIONS, BERNOULLI, NECKLACES, BEADS
  • Akdeniz University Affiliated: Yes

Abstract

By using generating functions technique, we investigate some properties of the k-ary Lyndon words. We give an explicit formula for the generating functions including not only combinatorial sums, but also hypergeometric function. We also derive higher-order differential equations and some formulas related to the k-ary Lyndon words. By applying these equations and formulas, we also derive some novel identities including the Stirling numbers of the second kind, the Apostol-Bernoulli numbers and combinatorial sums. Moreover, in order to compute numerical values of the higher-order derivative for the generating functions enumerating k-ary Lyndon words with prime number length, we construct an efficient algorithm. By applying this algorithm, we give some numerical values for these derivative equations for selected different prime numbers.