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

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

450 Combinatorics of Compositions and Words

Notation Deﬁnition

P (m; n) number of palindromic compositions of n with

m parts in N

(u) probability generating function

set of palindromic compositions of n with parts

in A

(n) |P

(x) gf for P

(n)

n,m

set of palindromic compositions of n with m

parts in A

(m; n) |P

n,m

(x, y) gf for P

(m; n)

(x, y, r, , d) gf for the number of palindromic compositions

of n with parts in A according to order and

statistic

→

(σ

···σ



|x, y, r, , d) gf for the number of palindromic compositions

of n with parts in A according to order and

statistic

→

that start with σ

···σ



par(σ) number of parts in σ

permutation

,i,r

set of primitive segmented tableaux of size

[] ×[i]withr diﬀerent entries

pr(, i, r)

|PR

,i,r

(x, y) gf for the number of compositions in C

n,m

that

quasi-avoid τ

(x, y) gf for the number of rises in the (palindromic)

compositions with parts in A

ris(σ)

number of rises in σ



region in C

R(τ),R(σ)

reverse of τ,σ

Res[f(z); z = z

] residue of f(z)atz = z

∗

smallest positive pole, with multiplicity one

composition

variance of random variable X

alphabet for automaton

set of permutations of [n]

n,k

number of k-element permutations of [n]

→

(par(σ), ris(σ), lev (σ), dro(σ))

pattern

τ = τ

–τ

– ···–τ

multi-pattern

Notation 451

Notation Deﬁnition

τ = τ

–a

– ···–a

–τ

shuﬄe-pattern

τ–nlap(σ)

maximum number of nonoverlapping

occurrences of τ in σ

partially ordered alphabet

tree

T (τ)

generating tree for permutations of [n] avoiding

the pattern τ

T (T )

generating tree for permutations of [n] avoiding

patterns in T

number of tilings of 1 × n board with squares

and dominoes

T (x)

gf for T

set of compositions with core κ and set of

values B

Var(X)

variance of random variable X

word

[k]

(τ; r) set of k-ary words of length n with r

occurrences of τ

[k]

(n, r) |W

[k]

(τ; r)|

[k]

(x, q) gf for W

[k]

(n, r)

random variable

lev

(n) number of levels in a random composition of n

par

(n) number of parts in a random composition of n

ris

(n) number of rises in a random composition of n

set of integers = {...,−3, −2, −1, 0, 1, 2, 3,...}

References

[1] M. Abramson. Enumeration of sequences by levels and rises. Discrete

Math., 12:101–112, 1975.

[2] M. Abramson. Restricted combinations and compositions. Fibonacci

Quart., 14(5):439–452, 1976.

[3] A.K. Agarwal. n-colour compositions. Indian J. Pure Appl. Math.,

31(11):1421–1427, 2000.

[4] A.K. Agarwal. An analogue of Euler’s identity and new combinatorial

properties of n-colour compositions. J. Comput. Appl. Math., 160:9–15,

2003.

[5] L.V. Ahlfors. Complex Analysis. McGraw-Hill Book Co., New York,

third edition, 1978.

[6] M.H. Albert, R.E.L. Aldred, M.D. Atkinson, C. Handley, and D. Holton.

Permutations of a multiset avoiding permutations of length 3. European

J. Combin., 22(8):1021–1031, 2001.

[7] K. Alladi and V.E. Hoggatt, Jr. Compositions with ones and twos.

Fibonacci Quart., 13(3):233–239, 1975.

[8] N. Alon and J.H. Spencer. The Probabilistic Method. Wiley-Interscience

Series in Discrete Mathematics and Optimization. Wiley-Interscience

[John Wiley & Sons], New York, second edition, 2000.

[9] G.E. Andrews. Ramanujan’s “lost” notebook. IV. Stacks and alternat-

ing parity in partitions. Adv. in Math., 53(1):55–74, 1984.

[10] G.E. Andrews. The Theory of Partitions. Cambridge Mathematical

Library. Cambridge University Press, Cambridge, 1998.

[11] E. Babson and E. Steingr´ımsson. Generalized permutation patterns

and a classiﬁcation of the Mahonian statistics. S´em. Lothar. Combin.,

44:Art. B44b, 2000.

[12] J. Baik, P. Deift, and K. Johansson. On the distribution of the length of

the longest increasing subsequence of random permutations. J. Amer.

Math. Soc., 12(4):1119–1178, 1999.

[13] C. Banderier, M. Bousquet-M´elou, A. Denise, P. Flajolet, D. Gardy,

and D. Gouyou-Beauchamps. Generating functions for generating trees.

Discrete Math., 246(1-3):29–55, 2002.

453

454 References

[14] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. A construction

for enumerating k-coloured Motzkin paths. In Computing and combi-

natorics (Xi’an, 1995), volume 959 of Lecture Notes in Comput. Sci.,

pages 254–263. Springer, Berlin, 1995.

[15] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. A methodology

for plane tree enumeration. Discrete Math., 180:45–64, 1998.

[16] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani. ECO: a method-

ology for the enumeration of combinatorial objects. J. Diﬀer. Equations

Appl., 5(4-5):435–490, 1999.

[17] J.-L. Baril and P.-T. Do. ECO-generation for compositions and their

restrictions. Proceedings of PP’08, 2008.

[18] E.A. Bender. Central and local limit theorems applied to asymptotic

enumeration. J. Combin. Theory Ser. A, 15:91–111, 1973.

[19] E.A. Bender and E.R. Canﬁeld. Locally restricted compositions. I. Re-

stricted adjacent diﬀerences. Electron.J.Combin., 12:#R57, 2005.

[20] E.A. Bender, G.F. Lawler, R. Pemantle, and H.S. Wilf. Irreducible

compositions and the ﬁrst return to the origin of a random walk. S´em.

Lothar. Combin., 50:Art. B50h, 2003/04.

[21] E.A. Bender and L.B. Richmond. Central and local limit theorems ap-

plied to asymptotic enumeration. II. multivariate generating functions.

J. Combin. Theory Ser. A, 34(3):255–265, 1983.

[22] A.T. Benjamin and J.J. Quinn. Proofs that really count,volume27of

The Dolciani Mathematical Expositions. Mathematical Association of

America, Washington, DC, 2003.

[23] A. Bernini, L. Ferrari, and R. Pinzani. Enumeration of some cla-

sses of words avoiding two, generalized patterns of length three.

arXiv:0711.3387v1, 2007.

[24] P. Billingsley. Probability and Measure. Wiley Series in Probability

and Mathematical Statistics. John Wiley & Sons Inc., New York, third

edition, 1995. A Wiley-Interscience Publication.

[25] M. B´ona. Combinatorics of Permutations. Discrete Mathematics and

its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton,

FL, 2004.

[26] M. Bousquet-M´elou and A. Rechnitzer. The site-perimeter of bargraphs.

Adv. in Appl. Math., 31:86–112, 2003.

[27] P. Br¨and´en and T. Mansour. Finite automata and pattern avoidance

in words. J. Combin. Theory Ser. A, 110(1):127–145, 2005.

References 455

[28] C. Brennan and A. Knopfmacher. The distribution of ascents of size d or

more in compositions. Discrete Math. Theor. Comput. Sci., 11(1):1–10,

2009.

[29] R. Brigham, R. Caron, P. Chinn, and R.P. Grimaldi. A tiling scheme

for the Fibonacci numbers. J. Recreational Mathematics, 28(1):10–17,

1996.

[30] R.C. Brigham, P.Z. Chinn, L.M. Holt, and R.S. Wilson. Finding the

recurrence relation for tiling 2 ×n rectangles. Congr. Numer., 105:134–

138, 1994.

[31] A. Burstein. Enumeration of words with forbidden patterns.Ph.D.

thesis, University of Pennsylvania, 1998.

[32] A. Burstein, P. H¨ast¨o, and T. Mansour. Packing patterns into words.

Electron.J.Combin., 9(2):#R20, 2002/03.

[33] A. Burstein and T. Mansour. Words restricted by patterns with at most

2 distinct letters. Electron.J.Combin., 9(2):#R3, 2002/03.

[34] A. Burstein and T. Mansour. Counting occurrences of some subword

patterns. Discrete Math. Theor. Comput. Sci., 6(1):1–11, 2003.

[35] A. Burstein and T. Mansour. Words restricted by 3-letter generalized

multipermutation patterns. Ann. Comb., 7(1):1–14, 2003.

[36] L. Carlitz. Enumeration of sequences by rises and falls: a reﬁnement of

the Simon Newcomb problem. Duke Math. J., 39:267–280, 1972.

[37] L. Carlitz. Enumeration of up-down sequences. Discrete Math., 4:273–

286, 1973.

[38] L. Carlitz. Restricted compositions. Fibonacci Quart., 14(3):254–264,

1976.

[39] L. Carlitz. Enumeration of compositions by rises, falls and levels. Math.

Nachr., 77:361–371, 1977.

[40] L. Carlitz. Up-down and down-up partitions. In Studies in foundations

and combinatorics, volume 1 of Adv. in Math. Suppl. Stud., pages 101–

129. Academic Press, New York, 1978.

[41] L. Carlitz and R. Scoville. Up-down sequences. Duke Math. J., 39:583–

598, 1972.

[42] L. Carlitz, R. Scoville, and T. Vaughan. Enumeration of pairs of se-

quences by rises, falls and levels. Manuscripta Math., 19(3):211–243,

1976.

[43] L. Carlitz and T. Vaughan. Enumeration of sequences of given speciﬁ-

cation according to rises, falls and maxima. Discrete Math., 8:147–167,

1974.

456 References

[44] F. Cazals. Monomer-dimer tilings. On INRIA web page, 1997.

[45] M. Cerasoli. Enumeration of compositions with prescribed parts. J.

Math. Anal. Appl., 89(2):351–358, 1982.

[46] Ch.A. Charalambides. On the enumeration of certain compositions and

related sequences of numbers. Fibonacci Quart., 20(2):132–146, 1982.

[47] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley, and C.H. Yan.

Crossings and nestings of matchings and partitions. Trans. Amer. Math.

Soc., 359(4):1555–1575 (electronic), 2007.

[48] P. Chinn, R.P. Grimaldi, and S. Heubach. The frequency of summands

of a particular size in palindromic compositions. Ars Combin., 69:65–78,

2003.

[49] P. Chinn, R.P. Grimaldi, and S. Heubach. Tilings with ls and squares.

J. Integer Seq., 10(2):Art. 07.2.8, 2007.

[50] P. Chinn and S. Heubach. (1,k)-compositions. Congr. Numer., 164:183–

194, 2003.

[51] P. Chinn and S. Heubach. Compositions of n with no occurrence of k.

Congr. Numer., 164:33–51, 2003.

[52] P. Chinn and S. Heubach. Integer sequences related to compositions

without 2’s. J. Integer Seq., 6(2):Art. 03.2.3, 2003.

[53] T. Chow and J. West. Forbidden subsequences and Chebyshev polyno-

mials. Discrete Math., 204(1-3):119–128, 1999.

[54] F.R.K. Chung, R.L. Graham, V.E. Hoggatt, Jr., and M. Kleiman. The

number of Baxter permutations. J. Combin. Theory Ser. A, 24(3):382–

394, 1978.

[55] A. Claesson. Generalized pattern avoidance. European J. Combin.,

22(7):961–971, 2001.

[56] S. Corteel and C.D. Savage. Partitions and compositions deﬁned by

inequalities. Ramanujan J., 8(3):357–381, 2004.

[57] S. Corteel, C.D. Savage, and H.S. Wilf. A note on partitions and com-

positions deﬁned by inequalities. Integers, 5(1):A24, 2005.

[58] A. de Mier. k-noncrossing and k-nonnesting graphs and ﬁllings of Fer-

rers diagrams. Electron. Notes Discrete Math., 28:3–10, 2007.

[59] R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics.

Springer-Verlag, Berlin, third edition, 2005.

[60] J.F. Dillon and D.P. Roselle. Simon Newcomb’s problem. SIAM J.

Appl. Math., 17:1086–1093, 1969.

References 457

[61] J. Dollhopf, I. Goulden, and C. Greene. Words avoiding a reﬂexive

acyclic relation. Electron. J. Combin., 11(2):#R28, 2004/06.

[62] A.A. Evdokimov and V. Nyu. The length of a supersequence for a set

of binary words with a given number of units. Metody Diskret. Anal.,

52:49–58, 1992.

[63] L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi. An algebraic charac-

terization of the set of succession rules. Theoret. Comput. Sci., 281(1-

2):351–367, 2002.

[64] G. Firro and T. Mansour. Three-letter-pattern-avoiding permutations

and functional equations. Electron.J.Combin., 13(1):#R51, 2006.

[65] G. Firro and T. Mansour. Restricted k-ary words and functional equa-

tions. Discrete Appl. Math., 157(4):602–616, 2009.

[66] M.E. Fisher. Statistical mechanics of dimers on a plane lattice. Phys.

Rev. (2), 124:1664–1672, 1961.

[67] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymp-

totics: harmonic sums. Theoret. Comput. Sci., 144(1-2):3–58, 1995.

[68] P. Flajolet and R. Sedwick. Analytic Combinatorics. Cambridge Uni-

versity Press, 2009.

[69] I. Flores. Direct calculation of k-generalized Fibonacci numbers. Fi-

bonacci Quart., 5:259–266, 1967.

[70] D. Foata and G.-N. Han. Inverses of words. S´em. Lothar. Combin.,

39:Art. B39d, 1997.

[71] D. Foata and G.-N. Han. Transformations on words. J. Algorithms,

28(1):172–191, 1998.

[72] T. Fort. Finite Diﬀerences and Diﬀerence Equations in the Real Do-

main. Oxford, at the Clarendon Press, 1948.

[73] W.M.Y. Goh and P. Hitczenko. Average number of distinct part sizes

in a random Carlitz composition. European J. Combin., 23(6):647–657,

2002.

[74] H.W. Gould. Binomial coeﬃcients, the bracket function, and compo-

sitions with relatively prime summands. Fibonacci Quart., 2:241–260,

1964.

[75] I.P. Goulden and D.M. Jackson. Combinatorial enumeration.Dover

Publications Inc., Mineola, NY, 2004.

[76] R.P. Grimaldi. Compositions with odd summands. Congr. Numer.,

142:113–127, 2000.

458 References

[77] R.P. Grimaldi. Compositions without the summand 1. Congr. Numer.,

152:33–43, 2001.

[78] R.P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied

Introduction. Addison Wesley, 2003.

[79] R.P. Grimaldi. Compositions and the alternate Fibonacci numbers.

Congr. Numer., 186:81–96, 2007.

[80] G.R. Grimmett and D.R. Stirzaker. Probability and random processes.

Oxford University Press, New York, third edition, 2001.

[81] E.O. Hare and P. Chinn. Tiling with Cuisenaire rods. In Applications

of Fibonacci numbers, Vol. 6 (Pullman, WA, 1994), pages 165–171.

Kluwer Acad. Publ., Dordrecht, 1996.

[82] H.A. Helfgott and I.M. Gessel. Enumeration of tilings of diamonds and

hexagons with defects. Electron.J.Combin., 6:#R16, 1999.

[83] P. Henrici. Applied and Computational Complex Analysis. John Wiley

& Sons Inc., New York, 1974-1977.

[84] S. Heubach. Tiling an m-by-n area with squares of size up to k-by-

k (m ≤ 5). Congr. Numer., 140:43–64, 1999.

[85] S. Heubach and P. Chinn. Patterns arising from tiling rectangles with

1-by-1 and 2-by-2 squares. Congr. Numer., 150:173–192, 2001.

[86] S. Heubach, P. Chinn, and P. Callahan. Tiling with trominoes. Congr.

Numer., 177:33–44, 2005.

[87] S. Heubach, P. Chinn, and R.P. Grimaldi. Rises, levels, drops and “+”

signs in compositions: extensions of a paper by Alladi and Hoggatt.

Fibonacci Quart., 41(3):229–239, 2003.

[88] S. Heubach, S. Kitaev, and T. Mansour. Partially ordered patterns in

compositions. Pure Math. Appl., 17(1-2):123–134, 2006.

[89] S. Heubach and T. Mansour. Compositions of n with parts in a set.

Congr. Numer., 168:127–143, 2004.

[90] S. Heubach and T. Mansour. Counting rises, levels, and drops in com-

positions. Integers, 5(1):A11, 2005.

[91] S. Heubach and T. Mansour. Avoiding patterns of length three in com-

positions and multiset permutations. Adv. in Appl. Math., 36(2):156–

174, 2006.

[92] S. Heubach and T. Mansour. Enumeration of 3-letter patterns in com-

positions. In Combinatorial Number Theory, pages 243–264. deGruyter,

2007.

References 459

[93] P. Hitczenko and G. Louchard. Distinctness of compositions of an in-

teger: a probabilistic analysis. Random Structures Algorithms, 19(3-

4):407–437, 2001.

[94] P. Hitczenko, C. Rousseau, and C.D. Savage. A generatingfunctionology

approach to a problem of Wilf. J. Comput. Appl. Math., 142:107–114,

2002.

[95] P. Hitczenko and C.D. Savage. On the probability that a randomly

chosen part size in a random composition is unrepeated. In Paul Erd˝os

and his mathematics (Budapest, 1999), pages 108–111. J´anos Bolyai

Math. Soc., Budapest, 1999.

[96] P. Hitczenko and C.D. Savage. On the multiplicity of parts in a random

composition of a large integer. SIAM J. Discrete Math., 18(2):418–435

(electronic), 2004.

[97] P. Hitczenko and G. Stengle. Expected number of distinct part sizes in a

random integer composition. Combin. Probab. Comput., 9(6):519–527,

2000.

[98] V.E. Hoggatt, Jr. and M. Bicknell. Palindromic compositions. Fibonacci

Quart., 13(4):350–356, 1975.

[99] V.E. Hoggatt, Jr. and D.A. Lind. Fibonacci and binomial properties of

weighted compositions. J. Combin. Theory Ser. A, 4:121–124, 1968.

[100] V.E. Hoggatt, Jr. and D.A. Lind. Compositions and Fibonacci numbers.

Fibonacci Quart., 7(3):253–266, 1969.

[101] J.E. Hopcroft, R. Motwani, and J.D. Ullman. Introduction to automata

theory, languages and computation. Addison Wesley, 2001.

[102] H.-K. Hwang and Y.-N. Yeh. Measures of distinctness for random par-

titions and compositions of an integer. Adv. in Appl. Math., 19(3):378–

414, 1997.

[103] B. Jackson and F. Ruskey. Meta-Fibonacci sequences, binary trees and

extremal compact codes. Electron.J.Combin., 13(1):#R26, 2006.

[104] V. Jel´ınek and T. Mansour. On pattern-avoiding partitions. Electron.

J. Combin., 15(1):#R39, 2008.

[105] V. Jel´ınek and T. Mansour. Wilf-equivalence on k-ary words, composi-

tions, and parking functions. Electron.J.Combin., 16(1):#R58, 2009.

[106] C. Kenyon, D. Randall, and A. Sinclair. Approximating the number of

monomer-dimer coverings of a lattice. J. Statist. Phys., 83(3-4):637–659,

1996.

[107] R. Kenyon. Local statistics of lattice dimers. Ann. Inst. H. Poincar´e

Probab. Statist., 33(5):591–618, 1997.

460 References

[108] S. Kitaev. Partially ordered generalized patterns. Discrete Math., 298(1-

3):212–229, 2005.

[109] S. Kitaev and T. Mansour. Partially ordered generalized patterns and

k-ary words. Ann. Comb., 7(2):191–200, 2003.

[110] S. Kitaev, T. Mansour, and J.B. Remmel. Counting descents, rises, and

levels, with prescribed ﬁrst element, in words. Discrete Math. Theor.

Comput. Sci., 10(3):1–22, 2008.

[111] S. Kitaev, T.B. McAllister, and T.K. Petersen. Enumerating segmented

patterns in compositions and encoding by restricted permutations. In-

tegers, 6:A34, 2006.

[112] M. Klazar. On abab-free and abba-free set partitions. European J.

Combin., 17(1):53–68, 1996.

[113] M. Klazar. On trees and noncrossing partitions. Discrete Appl. Math.,

82(1-3):263–269, 1998.

[114] M. Kline. Mathematical Thought from Ancient to Modern Times.Ox-

ford University Press, 1972.

[115] A. Knopfmacher and T. Mansour. Record statistics in a random com-

position. Preprint, 2009.

[116] A. Knopfmacher, T. Mansour, A. Munagi, and H. Prodinger. Smooth

words and Chebyshev polynomials. Preprint, 2008.

[117] A. Knopfmacher and M.E. Mays. Compositions with m distinct parts.

Ars Combin., 53:111–128, 1999.

[118] A. Knopfmacher and M.E. Mays. The sum of distinct parts in compo-

sitions and partitions. Bull.Inst.Combin.Appl., 25:66–78, 1999.

[119] A. Knopfmacher and H. Prodinger. On Carlitz compositions. European

J. Combin., 19(5):579–589, 1998.

[120] A. Knopfmacher and N. Robbins. On binary and Fibonacci composi-

tions. Ann. Univ. Sci. Budapest. Sect. Comput., 22:193–206, 2003.

[121] A. Knopfmacher and N. Robbins. Compositions with parts constrained

by the leading summand. Ars Combin., 76:287–295, 2005.

[122] D.E. Knuth. The art of computer programming. Volume 3. Addison-

Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973.

[123] D.E. Knuth. The art of computer programming. Volume 1. Addison-

Wesley Publishing Co., Reading, Mass.-London-Amsterdam, second

edition, 1975.

[124] D.E. Knuth. The average time for carry propagation. Nederl. Akad.

Wetensch. Indag. Math., 40(2):238–242, 1978.