Pattern 1^j+10^j Avoiding Binary Words

• Autorzy: Bilotta S. , Merlini D. , Pergola E. , Pinzani R.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^j=10^j By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.

Słowa kluczowe

EN

binary words; pattern avoidance; succession rule; generating trees

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 35--55
• Opis fizyczny: Bibliogr. 18 poz., tab., wykr.

Twórcy

autor

Bilotta S.

autor

Merlini D.

autor

Pergola E.

autor

Pinzani R.

• Dipartimento di Sistemi e Informatica, Universita degli Studi di Firenze, Viale G.B. Morgagni 65, 50134 Firenze, Italy,

Bibliografia

• [1] S. Bacchelli, L. Ferrari, R. Pinzani, R. Sprugnoli.Mixed succession rules: The commutative case. Journal of Combinatorial Theory, Series A, 117:568-582, 2010.
• [2] D. Baccherini, D. Merlini, and R. Sprugnoli. Binary words excluding a pattern and proper Riordan arrays. Discrete Mathematics, 307:1021-1037, 2007.
• [3] D. Baccherini, D. Merlini, and R. Sprugnoli. Level Generating Trees and proprer Riordan arrays. Applicable Analysis and Discrete Mathematics, 2(1):69-91, 2008.
• [4] E. Barcucci, A. Del Lungo, E. Pergola, R. Pinzani. ECO: a methodology for the Enumeration of Combinatorial Objects. Journal of Difference Equations and Applications, Vol.5 435-490, 1999.
• [5] E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Permutations avoiding an increasing number of lengthincreasing forbidden subsequences. Discrete Mathematics and Theoretical Computer Science 4:31-44, 2000.
• [6] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, M. Kleimann. The number of Baxter permutations. Journal of Combinatorial Theory, Series A, 24:382-394, 1978.
• [7] S. Corteel. Séries génératrices exponentielles pour les ECO-syst`emes signés. Proceedings of the 12-th International Conference on Formal Power Series and Algebraic Combinatorics, Moscow, 2000.
• [8] L. Ferrari, E. Pergola, R. Pinzani, S. Rinaldi. Jumping succession rules and their generating functions. Discrete Mathematics, 271 29-50, 2003.
• [9] L. J. Guibas and M. Odlyzko. Long repetitive patterns in random sequences. Zeitschrift fur Wahrscheinlichkeitstheorie, 53:241-262, 1980.
• [10] L. J. Guibas and M. Odlyzko. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory, Series A, 30:183-208, 1981.
• [11] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri. On some alternative characterizations of Riordan arrays. Canadian Journal of Mathematics, 49(2):301-320, 1997.
• [12] D. Merlini and R. Sprugnoli, Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern, Theoretical Computer Science, 412 (27), 2988-3001, 2011.
• [13] D. Merlini, R. Sprugnoli,M. C. Verri. An Algebra for proper generating tree. In Algorithms, trees, combinatorics and probabilities. Trends in Mathematics, Mathematics and Computer Science 127-139, 2000.
• [14] D. Merlini, M. C. Verri. Generating trees and proper Riordan Arrays. Discrete Mathematics, 218:167-183, 2003.
• [15] R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading, MA, 1996.
• [16] L. W. Shapiro, S. Getu, W. J. Woan and L. Woodson. The Riordan group. Discrete Applied Mathematics, 34:229-239, 1991.
• [17] R. P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, Cambridge, 1999.
• [18] J. West, Generating trees and the Catalan and Schröder numbers, Discrete Mathematics, 146:247-262, 1995.