Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

References 461

[125] T. Koshy. Fibonacci and Lucas numbers with applications. Pure and

Applied Mathematics (New York). Wiley-Interscience, New York, 2001.

[126] C. Krattenthaler. Permutations with restricted patterns and Dyck

paths. Adv. in Appl. Math., 27(2-3):510–530, 2001.

[127] C. Krattenthaler. Growth diagrams, and increasing and decreasing

chains in ﬁllings of Ferrers shapes. Adv. in Appl. Math., 37(3):404–431,

2006.

[128] V. Lakshmibai and B. Sandhya. Criterion for smoothness of Schubert

varieties in Sl(n)/B. Proc. Indian Acad. Sci. Math. Sci., 100(1):45–52,

1990.

[129] L. Lipshitz. D-ﬁnite power series. J. Algebra, 122(2):353–373, 1989.

[130] M. Lothaire. Combinatorics on Words. Cambridge Mathematical Li-

brary. Cambridge University Press, Cambridge, 1997.

[131] M. Lothaire. Algebraic combinatorics on words,volume90ofEncyclo-

pedia of Mathematics and its Applications. Cambridge University Press,

Cambridge, 2002.

[132] M. Lothaire. Applied combinatorics on words, volume 105 of Encyclope-

dia of Mathematics and its Applications. Cambridge University Press,

Cambridge, 2005.

[133] G. Louchard. The number of distinct part sizes of some multiplicity

in compositions of an integer: A probabilistic analysis. In Random

Walks,volumeACofDMTCS Proceedings, pages 155–170. Discrete

Mathematics and Theoretical Computer Science, 2003.

[134] G. Louchard and H. Prodinger. Probabilistic analysis of Carlitz com-

positions. Discrete Math. Theor. Comput. Sci., 5(1):71–95, 2002.

[135] I.D. MacDonald. Some group elements deﬁned by commutators. Math.

Sci., 4(2):129–131, 1979.

[136] P.A. MacMahon. Memoir on the theory of the compositions of numbers.

Phil. Trans. Royal Society London. A, 184:835–901, 1893.

[137] P.A. MacMahon. The Indices of Permutations and the Derivation

Therefrom of Functions of a Single Variable Associated with the Permu-

tations of any Assemblage of Objects. Amer.J.Math., 35(3):281–322,

1913.

[138] P.A. MacMahon. Combinatory analysis. Vol. I, II (bound in one vol-

ume). Dover Phoenix Editions. Dover Publications Inc., Mineola, NY,

2004. Reprint of An introduction to combinatory analysis (1920) and

Combinatory analysis. Vol. I, II (1915, 1916).

462 References

[139] T. Mansour. http://math.haifa.ac.il/touﬁk/automaton01.html. Au-

tomaton program, 2003.

[140] T. Mansour. http://math.haifa.ac.il/touﬁk/table4auto.html. Table of

values computed with automaton program, 2003.

[141] T. Mansour. Restricted 132-avoiding k-ary words, Chebyshev polyno-

mials, and continued fractions. Adv. in Appl. Math., 36(2):175–193,

2006.

[142] T. Mansour. Longest alternating subsequences in pattern-restricted k-

ary words. Online J. Analytic Combin., 3:#5, 2008.

[143] T. Mansour. Longest alternating subsequences of k-ary words. Discrete

Appl. Math., 156(1):119–124, 2008.

[144] T. Mansour. Smooth partitions and Chebyshev polynomials. Preprint,

2008.

[145] T. Mansour and B.O. Sirhan. Counting l-letter subwords in composi-

tions. Discrete Math. Theor. Comput. Sci., 8(1):285–297, 2006.

[146] T. Mansour and A. Vainshtein. Avoiding maximal parabolic subgroups

of S

. Discrete Math. Theor. Comput. Sci., 4(1):67–75, 2000.

[147] T. Mansour and A. Vainshtein. Restricted 132-avoiding permutations.

Adv. in Appl. Math., 26(3):258–269, 2001.

[148] T. Mansour and A. Vainshtein. Restricted permutations and Chebyshev

polynomials. S´em. Lothar. Combin., 47:Art. B47c, 2001/02.

[149] T. Mansour and A. Vainshtein. Counting occurrences of 132 in a per-

mutation. Adv. in Appl. Math., 28(2):185–195, 2002.

[150] J.E. Marsden and M.J. Hoﬀman. Basic complex analysis. W. H. Free-

man and Company, New York, second edition, 1987.

[151] R.B. McQuistan and S.J. Lichtman. Exact recursion relation for 2 x n

arrays of dumbbells. J. Math. Phy., 11(10):3095–3099, 1970.

[152] D. Merlini, R. Sprugnoli, and M.C. Verri. Strip tiling and regular gram-

mars. Theoret. Comput. Sci., 242(1-2):109–124, 2000.

[153] D. Merlini, R. Sprugnoli, and M.C. Verri. A strip-like tiling algorithm.

Theoret. Comput. Sci., 282(2):337–352, 2002.

[154] D. Merlini, F. Uncini, and M.C. Verri. A uniﬁed approach to the study

of general and palindromic compositions. Integers, 4:A23, 2004.

[155] S.G. Mohanty. Some properties of compositions and their application

to the ballot problem. Canad. Math. Bull., 8:359–372, 1965.

[156] S.G. Mohanty. Restricted compositions. Fibonacci Quart., 5:223–234,

1967.

References 463

[157] A.N. Myers. Pattern avoidance in multiset permutations: bijective

proof. Ann. Comb., 11(3-4):507–517, 2007.

[158] A.N. Myers and H.S. Wilf. Left-to-right maxima in words and multiset

permutations. Israel J. Math., 166:167–183, 2008.

[159] G. Narang and A.K. Agarwal. n-colour self-inverse compositions. Proc.

Indian Acad. Sci. Math. Sci., 116(3):257–266, 2006.

[160] G. Narang and A.K. Agarwal. Lattice paths and n-colour compositions.

Discrete Math., 308(9):1732–1740, 2008.

[161] T.V. Narayana. Sur les treillis form´es par les partitions d’un entier et

leurs applications `alath´eorie des probabilit´es. C. R. Acad. Sci. Paris,

240:1188–1189, 1955.

[162] T.V. Narayana and G.E. Fulton. A note on the compositions of an

integer. Canad. Math. Bull., 1:169–173, 1958.

[163] J. Noonan and D. Zeilberger. The enumeration of permutations with

a prescribed number of “forbidden” patterns. Adv. in Appl. Math.,

17(4):381–407, 1996.

[164] A.M. Odlyzko. Asymptotic enumeration methods. In Handbook of com-

binatorics, Vol. 1, 2, pages 1063–1229. Elsevier, Amsterdam, 1995.

[165] H. Prodinger. Combinatorics of geometrically distributed random vari-

ables: left-to-right maxima. Discrete Math., 153:253–270, 1996.

[166] H. Prodinger. Records in geometrically distributed words: sum of po-

sitions. Appl. Anal. Discrete Math., 2(2):234–240, 2008.

[167] J. Propp. Enumeration of matchings: problems and progress. In L. J.

Billera, A. Bj¨orner, C. Greene, R. E. Simion, and R. P. Stanley, editors,

New perspectives in algebraic combinatorics,volume38ofMathemati-

cal Sciences Research Institute Publications, pages 255–291. Cambridge

University Press, 1999.

[168] D. Rawlings. Restricted words by adjacencies. Discrete Math., 220:183–

200, 2000.

[169] A. Regev. Asymptotics of the number of k-words with an l-descent.

Electron.J.Combin., 5:#R15, 1998.

[170] M. R´egnier and W. Szpankowski. On the approximate pattern occur-

rences in a text, in Compression and Complexity of Sequences 1997.

IEEE Computer Society, pages 253–264, 1998.

[171] B. Richmond and A. Knopfmacher. Compositions with distinct parts.

Aequationes Math., 49:86–97, 1995.

[172] A. Riese. qMultiSum—a package for proving q-hypergeometric multiple

summation identities. J. Symbolic Comput., 35(3):349–376, 2003.

464 References

[173] Th. Rivlin. Chebyshev polynomials. Pure and Applied Mathematics

(New York). John Wiley & Sons Inc., New York, second edition, 1990.

[174] A. Robertson, H.S. Wilf, and D. Zeilberger. Permutation patterns and

continued fractions. Electron.J.Combin., 6:#R38, 1999.

[175] B.E. Sagan. Proper partitions of a polygon and k-Catalan numbers.

Ars Combin., 88:109–124, 2008.

[176] C.D. Savage and H.S. Wilf. Pattern avoidance in compositions and

multiset permutations. Adv. in Appl. Math., 36(2):194–201, 2006.

[177] C. Schensted. Longest increasing and decreasing subsequences. Canad.

J. Math., 13:179–191, 1961.

[178] R. Servedio and Y.-N. Yeh. A bijective proof on circular compositions.

Bull. Inst. Math. Acad. Sinica, 23(4):283–293, 1995.

[179] R. Simion and F.W. Schmidt. Restricted permutations. European J.

Combin., 6:383–406, 1985.

[180] N.J.A. Sloane. The on-line encyclopedia of integer sequences. published

electronically at http://www.research.att.com/∼njas/sequences/, 2009.

[181] K. Srinivase Rao and A.K. Agarwal. On a generalized composition

function. J. Indian Math. Soc. (N.S.), 67(1-4):99–106, 2000.

[182] R.P. Stanley. Enumerative combinatorics. Vol. 1,volume49ofCam-

bridge Studies in Advanced Mathematics. Cambridge University Press,

Cambridge, 1997.

[183] R.P. Stanley. Enumerative combinatorics. Vol. 2,volume62ofCam-

bridge Studies in Advanced Mathematics. Cambridge University Press,

Cambridge, 1999.

[184] Axel Thue.

Uber unendliche Zahlenreihen. In Trygve Nagell, Atle Sel-

berg, Sigmund Selberg, and Knut Thalberg, editors, Selected Mathe-

matical papers of Axel Thue, pages 139–158. Universitetsforlaget, 1977.

Originally published in Kra. Vidensk. Selsl. Skrifter. I. Mat. Nat. Kl.

1906. No. 7. Kra. 1906.

[185] Axel Thue.

Uber die gegenseitige Lage gleicher Teile gewisser Zeichen-

reihen. In Trygve Nagell, Atle Selberg, Sigmund Selberg, and Knut

Thalberg, editors, Selected Mathematical papers of Axel Thue, pages

413–478. Universitetsforlaget, 1977. Originally published in Kra. Vi-

densk. Selsl. Skrifter. I. Mat. Nat. Kl. 1912. No. 1. Kra. 1912.

[186] Axel Thue. Probleme ¨uber Ver¨anderungen von Zeichenreihen nach

gegebenen Regeln. In Trygve Nagell, Atle Selberg, Sigmund Selberg,

and Knut Thalberg, editors, Selected Mathematical papers of Axel Thue,

pages 493–524. Universitetsforlaget, 1977. Originally published in Kra.

Vidensk. Selsl. Skrifter. I. Mat. Nat. Kl. 1914. No. 10. Kra. 1914.

References 465

[187] C.A. Tracy and H. Widom. On the distributions of the lengths of the

longest monotone subsequences in random words. Probab. Theory Re-

lated Fields, 119(3):350–380, 2001.

[188] A.J. van Zanten. The ranking problem of a Gray code for compositions.

Ars Combin., 41:257–268, 1995.

[189] N.Y. Vilenkin. Combinatorics. Academic Press, New York-London,

1971.

[190] M. Wachs and D. White. p, q-Stirling numbers and set partition statis-

tics. J. Combin. Theory Ser. A, 56(1):27–46, 1991.

[191] J. West. Permutations with forbidden subsequences and stack sortable

permutations. Ph.D. thesis, M.I.T., 1990.

[192] J. West. Generating trees and forbidden subsequences. In Proceedings

of the 6th Conference on Formal Power Series and Algebraic Combina-

torics (New Brunswick, NJ, 1994), volume 157, pages 363–374, 1996.

[193] H.S. Wilf. Generatingfunctionology, 2nd Edition. Academic Press, Inc.,

San Diego, 1994.

[194] J. Wimp and D. Zeilberger. Resurrecting the asymptotics of linear

recurrences. J. Math. Anal. Appl., 111(1):162–176, 1985.