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.
@article{bwmeta1.element.doi-10_2478_s11533-011-0002-6,
author = {Toufik Mansour and Mark Shattuck},
title = {Restricted partitions and q-Pell numbers},
journal = {Open Mathematics},
volume = {9},
year = {2011},
pages = {346-355},
zbl = {1238.05021},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0002-6}
}
Toufik Mansour; Mark Shattuck. Restricted partitions and q-Pell numbers. Open Mathematics, Tome 9 (2011) pp. 346-355. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0002-6/
[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 | Zbl 1169.05305
[3] Briggs K.S., Little D.P., Sellers J.A., Tiling proofs of various g-Pell identities via tilings, Ann. Comb. (in press) | Zbl 1233.05037
[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 | Zbl 1137.05009
[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 | Zbl 1179.05014
[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 | Zbl 0191.17903
[9] Sagan B.E., Pattern avoidance in set partitions, Ars Combin., 2010, 94(1), 79–96 | Zbl 1240.05018
[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 | Zbl 1007.05017
[11] Simion R., Schmidt F.W., Restricted permutations, European J. Combin., 1985, 6(4), 383–406 | Zbl 0615.05002
[12] Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, http://oeis.org | Zbl 1274.11001
[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