Inversion sequences and signed permutations

Toufik Mansour; Amir Safadi

doi:10.47443/dml.2024.060

Author(s)

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

Amir Safadi Department of Mathematics, University of Haifa,3103301 Haifa,Israel

Abstract

A signed inversion sequence of length n is a sequence of integers e = e1 en, where ei+1 2 f0; 0; 1; 1; : : : ; i; i g for every i 2 f0; 1; : : : ; n 1g. For a set of signed patterns B, let In(B) be the set of signed inversion sequences of length n that avoid all the signed patterns from B. We say that two sets of signed patterns B and C are Wilf-equivalent if jIn(B)j = jIn(C)j for every n 0. In this paper, by generating trees, we show that the number of Wilf-equivalences among singles of a length-2 signed pattern is 3 and the number of Wilf-equivalences among pairs of a length-2 signed patterns is 30.

Publication Details

Page(s) 13-20

DOI 10.47443/dml.2024.060

Published Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords

inversion sequences, generating trees, signed inversion sequences, Wilf-equivalences

References

Corteel S.,Martinez M. A.,Savage C. D.,Weselcouch M. .2016 .. Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci, 18(2) : 2.

Knuth D. E. .1973 .. , : .

Kotsireas I.,Mansour T.,G. Yıldırım, T. .2024 .An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences. J. Symbolic Comput, 120 : 102231.

Mansour T. .2001 .Pattern avoidance in coloured permutations. Se´min. Lothar. Combin, 46 : B46g.

Mansour T.,Shattuck M. .2015 .Pattern avoidance in inversion sequences. PuMA, 25(2) : 157-176.

Simion R. .2000 .Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations. Electron. J. Combin, 7 : R9.

West J. .1996 .Generating trees. , 157 : 363-374.