Please use this identifier to cite or link to this item:
|Title:||Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier-Szpankowski method|
Frequency of pattern occurrences
Goulden-Jackson cluster method
|Citation:||Kong, Y. (2005-12). Extension of Goulden-Jackson cluster method on pattern occurrences in random sequences and comparison with Régnier-Szpankowski method. Journal of Difference Equations and Applications 11 (15) : 1265-1271. ScholarBank@NUS Repository. https://doi.org/10.1080/10236190500376326|
|Abstract:||The Goulden-Jackson cluster method is a powerful method to find generating functions of pattern occurrences in random sequences . The method is clearly explained, extended and implemented by Noonan and Zeilberger . In this paper, we elaborate on one of the several extensions in , namely the extension from symmetrical Bernoulli sequences where the occurrences of each symbol have equal probability, to asymmetrical Bernoulli sequences with different probabilities of symbol generations. An explicit formula is derived for the extension, which is implicitly embedded in the treatment of . The extended result is then compared with the method of Régnier-Szpankowski , a method which was developed independently to tackle the same problem. By manipulating some matrix inversions, we show that the Régnier-Szpankowski method can be simplified to the extended Goulden-Jackson method.|
|Source Title:||Journal of Difference Equations and Applications|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Aug 17, 2018
WEB OF SCIENCETM
checked on Jul 9, 2018
checked on Jun 8, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.