Restricted partitions and q-Pell numbers

• Autorzy: Toufik Mansour , Mark Shattuck
• Języki publikacji: EN

Abstrakty

EN

In this paper, we provide new combinatorial interpretations for the Pell numbers p n in terms of finite set partitions. In particular, we identify six classes of partitions of size n, each avoiding a set of three classical patterns of length four, all of which have cardinality given by p n. By restricting the statistic recording the number of inversions to one of these classes, and taking it jointly with the statistic recording the number of blocks, we obtain a new polynomial generalization of p n. Similar considerations using the comajor index statistic yields a further generalization of the q-Pell number studied by Santos and Sills.

Słowa kluczowe

EN

Pattern avoidance; Inversion; Comajor index; Pell number; q-generalization

Kategorie tematyczne

• 05A18: Partitions of sets
• 05A15: Exact enumeration problems, generating functions

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2011
• Tom: 9
• Numer: 2
• Strony: 346-355

Daty

wydano

2011-04-01

online

2011-02-18

Twórcy

autor

Toufik Mansour

• University of Haifa

autor

Mark Shattuck

• University of Tennessee

Bibliografia

• [1] Andrews G.E., The Theory of Partitions, Encyclopedia Math. Appl., 2, Addison-Wesley, Reading, 1976
• [2] Benjamin AT., Plott S.P., Sellers J.A., Tiling proofs of recent sum identities involving Pell numbers, Ann. Comb., 2008, 12(3), 271–278 http://dx.doi.org/10.1007/s00026-008-0350-5
• [3] Briggs K.S., Little D.P., Sellers J.A., Tiling proofs of various g-Pell identities via tilings, Ann. Comb. (in press)
• [4] Falcón Santana S., Díaz-Barrero J.L, Some properties of sums involving Pell numbers, Missouri J. Math. Sci., 2006, 18(1), 33–40
• [5] Goyt A.M., Avoidance of partitions of a three element set, Adv. in Appl. Math., 2008, 41(1), 95–114 http://dx.doi.org/10.1016/j.aam.2006.07.006
• [6] Jelínek V, Mansour T, On pattern-avoiding partitions, Electron. J. Combin., 2008, 15(1), #R39
• [7] Klazar M., On abab-free and abba-free set partitions, European J. Combin., 1996, 17(1), 53–68 http://dx.doi.org/10.1006/eujc.1996.0005
• [8] Knuth D.E., The Art of Computer Programming, Vol. 1,3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, Reading, 1968, 1974
• [9] Sagan B.E., Pattern avoidance in set partitions, Ars Combin., 2010, 94(1), 79–96
• [10] Santos J.P.O., Sills A.V., g-Pell sequences and two identities of V. A. Lebesgue, Discrete Math., 2002, 257(1), 125–142 http://dx.doi.org/10.1016/S0012-365X(01)00475-7
• [11] Simion R., Schmidt F.W., Restricted permutations, European J. Combin., 1985, 6(4), 383–406
• [12] Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, http://oeis.org
• [13] Stanley R.P., Enumerative Combinatorics, Vol. I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole, Monterey, 1986
• [14] Stanton D., White D., Constructive Combinatorics, Undergrad. Texts Math., Springer, New York, 1986

Identyfikatory

DOI

10.2478/s11533-011-0002-6