On a recurrence related to 321–avoiding permutations

Toufik Mansour and Mark Shattuck
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 20, 2014, Number 2, Pages 74–78
Full paper (PDF, 166 Kb)

Details

Authors and affiliations

Toufik Mansour
Department of Mathematics, University of Haifa
31905 Haifa, Israel

Mark Shattuck
Department of Mathematics, University of Haifa
31905 Haifa, Israel

Abstract

Dokos et al. recently conjectured that the distribution polynomial f_n(q) on the set of permutations of size n avoiding the pattern 321 for the number of inversions is given by:

    \[f_n(q) = f_{n-1}(q) + \sum_{k=0}^{n-2} q^{k+1} f_k(q) f_{n-1-k}(q), \quad n \ge 1,\]

with f_0(q) = 1, which was later proven in the affirmative, see [1]. In this note, we provide a new proof of this conjecture, based on the scanning-elements algorithm described in [3], and present an identity obtained by equating two explicit formulas for the generating function \sum_{n \ge 0} a_n(q)x^n.

Keywords

  • Avoidance
  • Inversion number
  • q-analogue
  • Continued fractions
  • Permutations

AMS Classification

  • 11B37
  • 11B65
  • 05A15

References

  1. Cheng, S.-E., S. Elizalde, A. Kasraoui, B. E. Sagan. Inversion and major index polynomials, Preprint, http://arxiv.org/pdf/1112.6014.pdf.
  2. Dokos, T., T. Dwyer, B. P. Johnson, B. E. Sagan, K. Selsor. Permutation patterns and statistics, Discrete Math., Vol. 312, 2012, 2760–2775.
  3. Firro, G., T. Mansour. Three-letter-pattern-avoiding permutations and functional equations, Electron. J. Combin., Vol. 13, 2006, #R51.
  4. Fürlinger, J., J. Hofbauer, q-Catalan numbers, J. Combin. Theory Ser. A, Vol. 40, 1985, No. 2, 248–264.

Related papers

Cite this paper

Mansour, T. & Shattuck, M. (2014). On a recurrence related to 321-avoiding permutations. Notes on Number Theory and Discrete Mathematics, 20(2), 74-78.

Comments are closed.