Combinatorial proofs on the joint distribution of descents and inverse descents

arXiv2212.05307MaRDI QIDQ6420138FDOQ6420138

Authors: Frank Z. K. Li, Edward Y. S. Liu, Jane Y. X. Yang

Publication date: 10 December 2022

Abstract: Let

A_{n, i, j}

be the number of permutations on

[n]

with

i - 1

descents and

j - 1

inverse descents. Carlitz, Roselle and Scoville in 1966 first revealed some combinatorial and arithmetic properties of

A_{n, i, j}

, which contain a recurrence of

A_{n, i, j}

. Using the idea of balls in boxes, Petersen gave a combinatorial interpretation for the generating function of

A_{n, i, j}

, and obtained the same recurrence of

A_{n, i, j}

from its generating function. Subsequently, Petersen asked whether there is a visual way to understand this recurrence. In this paper, after observing the internal structures of permutation grids, we present a combinatorial proof of the recurrence of

A_{n, i, j}

. Let

I_{n, k}

and

J_{n, k}

count the number of involutions and fixed-point free involutions on

[n]

with

k

descents, respectively. With the help of generating functions, Guo and Zeng derived two recurrences of

I_{n, k}

and

J_{2 n, k}

that play an essential role in the proof of their unimodal properties. Unexpectedly, the constructive approach to the recurrence of

A_{n, i, j}

is found to fuel the combinatorial interpretations of these two recurrences of

I_{n, k}

and

J_{2 n, k}

.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

This page was built for publication: Combinatorial proofs on the joint distribution of descents and inverse descents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420138)