<abstract xmlns="http://www.w3.org/1999/xhtml">Let 𝒯(<italic>k</italic>)<italic>n</italic> denote the set of <italic>k</italic>-Stirling permutations having <italic>n</italic> distinct letters. Here, we consider the number of steps required (i.e., <italic>pushes</italic>) to rearrange the letters of a member of 𝒯(<italic>k</italic>)<italic>n</italic> so that they occur in non-decreasing order. We find recurrences for the joint distribution on 𝒯(<italic>k</italic>)<italic>n</italic> for the statistics recording the number of levels (i.e., occurrences of equal adjacent letters) and pushes. When <italic>k</italic> = 2, an explicit formula for the ordinary generating function of this distribution is also found. In order to do so, we determine the <italic>LU</italic>-decomposition of a certain infinite matrix having polynomial entries which enables one to compute explicitly the inverse matrix.</abstract>

Let 𝒯(k)n denote the set of k-Stirling permutations having n distinct letters. Here, we consider the number of steps required (i.e., pushes) to rearrange the letters of a member of 𝒯(k)n so that they occur in non-decreasing order. We find recurrences for the joint distribution on 𝒯(k)n for the statistics recording the number of levels (i.e., occurrences of equal adjacent letters) and pushes. When k = 2, an explicit formula for the ordinary generating function of this distribution is also found. In order to do so, we determine the LU-decomposition of a certain infinite matrix having polynomial entries which enables one to compute explicitly the inverse matrix.

Counting Stirling permutations by number of pushes

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Counting Stirling permutations by number of pushes"}

Let 𝒯(k)n denote the set of k-Stirling permutations having n distinct letters. Here, we consider the number of steps required (i.e., pushes) to rearrange the...

Counting Stirling permutations by number of pushes

Published Online: Dec 24, 2020

Page range: 17 - 27

Received: Jun 10, 2019

Accepted: Jun 13, 2020

DOI: https://doi.org/10.1515/puma-2015-0038

Keywords
-Stirling permutation, generating function, level, combinatorial statistic

© 2020 Toufik Mansour et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Counting Stirling permutations by number of pushes

Published Online: Dec 24, 2020

Page range: 17 - 27

Received: Jun 10, 2019

Accepted: Jun 13, 2020

DOI: https://doi.org/10.1515/puma-2015-0038

Keywords-Stirling permutation, generating function, level, combinatorial statistic

© 2020 Toufik Mansour et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Keywords
-Stirling permutation, generating function, level, combinatorial statistic