Journal of Combinatorics

Volume 8 (2017)

Number 4

The number of permutations with the same peak set for signed permutations

Pages: 631 – 652

DOI: https://dx.doi.org/10.4310/JOC.2017.v8.n4.a4

Authors

Francis Castro-Velez (Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Alexander Diaz-Lopez (Department of Mathematics and Statistics, Swarthmore College, Swarthmore, Pennsylvania, U.S.A.)

Rosa Orellana (epartment of Mathematics, Dartmouth College, Hanover, New Hampshire, U.S.A.)

José Pastrana (Department of Mathematics, University of Notre Dame, Indiana, U.S.A.)

Rita Zevallos (Department of Mathematics and Statistics, Swarthmore College, Swarthmore, Pennsylvania, U.S.A.)

Abstract

A signed permutation $\pi = \pi_1 \pi_2 \dotsc \pi_n$ in the hyperoctahedral group $B_n$ is a word such that each $\pi_i \in \lbrace \bar{n}, \dotsc , \bar{1}, 1, \dotsc , n \rbrace$ where $i = \bar{i}$, and $\lbrace \lvert \pi_1 \rvert , \lvert \pi_2 \rvert , \dotsc , \lvert \pi n \rvert \rbrace = \lbrace 1, 2, \dotsc , n \rbrace$. An index $i$ is a peak of $\pi$ if $\pi_{i-1} \lt \pi_i \gt \pi_{i+1}$ and $P_B(\pi)$ denotes the set of all peaks of $\pi$. Given any set $S$, we define $P_B(S, n)$ to be the set of signed permutations $\pi \in B_n$ with $P_B(\pi) = S$. In this paper we show that $\lvert P_B(S, n) \rvert = p(n)2^{2n - \lvert S \rvert - 1}$ where $p(n)$ is a polynomial that takes integral values when evaluated at integers. In addition, we have partially extended these results to the more complicated case where we add $\pi_0 = 0$ at the beginning of the permutations, which gives rise to the possibility of a peak at position $1$, for both the symmetric and the hyperoctahedral groups. In both cases we establish recursive formulae to compute the number of permutations (signed permutations in the case of $B_n$) with a given peak set.

Keywords

peak sets, permutations, signed permutations

Received 17 August 2015

Published 17 July 2017