Efficient recurrence for the enumeration of permutations with fixed pinnacle set
Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative study of pinnacle sets of permutations has attracted a fair amount of attention recently. In this article, we provide a recurrence that can be used to compute efficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2022-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/8321/pdf |
| _version_ | 1797270022545997824 |
|---|---|
| author | Wenjie Fang |
| author_facet | Wenjie Fang |
| author_sort | Wenjie Fang |
| collection | DOAJ |
| description | Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative study
of pinnacle sets of permutations has attracted a fair amount of attention
recently. In this article, we provide a recurrence that can be used to compute
efficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with a
given pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$
of size $k$. A symbolic expression can also be computed in this way for
pinnacle sets of fixed size. A weighted sum $q_n(P)$ of $|\mathfrak{S}_n(P)|$
proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simple
form, and a conjectural form is given recently by Flaque, Novelli and Thibon
(2021+). We settle the problem by providing and proving an alternative form of
$q_n(P)$, which has a strong combinatorial flavor. We also study admissible
orderings of a given pinnacle set, first considered by Rusu (2020) and
characterized by Rusu and Tenner (2021), and we give an efficient algorithm for
their counting. |
| first_indexed | 2024-03-11T21:32:00Z |
| format | Article |
| id | doaj.art-a3ecc139fb99447aa75dbdaf984e15ac |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:40Z |
| publishDate | 2022-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-a3ecc139fb99447aa75dbdaf984e15ac2024-03-07T15:46:22ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502022-03-01vol. 24, no. 1Combinatorics10.46298/dmtcs.83218321Efficient recurrence for the enumeration of permutations with fixed pinnacle setWenjie Fanghttps://orcid.org/0000-0001-9148-2807Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative study of pinnacle sets of permutations has attracted a fair amount of attention recently. In this article, we provide a recurrence that can be used to compute efficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with a given pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$ of size $k$. A symbolic expression can also be computed in this way for pinnacle sets of fixed size. A weighted sum $q_n(P)$ of $|\mathfrak{S}_n(P)|$ proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simple form, and a conjectural form is given recently by Flaque, Novelli and Thibon (2021+). We settle the problem by providing and proving an alternative form of $q_n(P)$, which has a strong combinatorial flavor. We also study admissible orderings of a given pinnacle set, first considered by Rusu (2020) and characterized by Rusu and Tenner (2021), and we give an efficient algorithm for their counting.https://dmtcs.episciences.org/8321/pdfmathematics - combinatorics |
| spellingShingle | Wenjie Fang Efficient recurrence for the enumeration of permutations with fixed pinnacle set Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| title_full | Efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| title_fullStr | Efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| title_full_unstemmed | Efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| title_short | Efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| title_sort | efficient recurrence for the enumeration of permutations with fixed pinnacle set |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/8321/pdf |
| work_keys_str_mv | AT wenjiefang efficientrecurrencefortheenumerationofpermutationswithfixedpinnacleset |