Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On $k$-crossings and ...
Conference paper

On $k$-crossings and $k$-nestings of permutations

Sophie Burrill (1), Marni Mishna (1), Jacob Post (2)
(1) Department of Mathematics [Burnaby]
(2) Department of Computer Science
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Proceedings
DOI
10.46298/dmtcs.2873
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
621
Views
916
Downloads

On $k$-crossings and $k$-nestings of permutations

Sophie Burrill (1), Marni Mishna (1), Jacob Post (2)
(1) Department of Mathematics [Burnaby]
(2) Department of Computer Science
Abstract
English
We introduce $k$-crossings and $k$-nestings of permutations. We show that the crossing number and the nesting number of permutations have a symmetric joint distribution. As a corollary, the number of $k$-noncrossing permutations is equal to the number of $k$-nonnesting permutations. We also provide some enumerative results for $k$-noncrossing permutations for some values of $k$.
French
Nous introduisons les $k$-chevauchement d'arcs et les $k$-empilements d'arcs de permutations. Nous montrons que l'index de chevauchement et l'index de empilement ont une distribution conjointe symétrique pour les permutations de taille $n$. Comme corollaire, nous obtenons que le nombre de permutations n'ayant pas un $k$-chevauchement est égal au nombre de permutations n'ayant un $k$-empilement. Nous fournissons également quelques résultats énumératifs.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • crossing
  • nesting
  • permutation
  • enumeration
Cited by

Source: OpenCitations

  • Restricted permutations refined by number of crossings and nestings

    arXiv (Cornell University)

    Authors : Paul M. Rakotomamonjy ORCID

    Journal reference : Volume 343, 2020, pp. 111950

    DOI : 10.1016/j.disc.2020.111950
  • Arc-Coloured Permutations

    Discrete Mathematics & Theoretical Computer Science

    Authors : Lily Yen ORCID

    Journal reference : Volume DMTCS Proceedings vol. AS,..., 2013, pp.

    DOI : 10.46298/dmtcs.2339
  • A Generating Tree Approach to k-Nonnesting Partitions and Permutations

    Annals of Combinatorics

    Authors : Sophie Burrill, Sergi Elizalde ORCID, Marni Mishna ORCID, Lily Yen ORCID

    Journal reference : Volume 20, 2016, pp. 453-485

    DOI : 10.1007/s00026-016-0321-1
  • Symmetric Distribution of Crossings and Nestings in Permutations of Type $B$

    The Electronic Journal of Combinatorics

    Authors : Adel Hamdi ORCID

    Journal reference : Volume 18, 2011, pp.

    DOI : 10.37236/687
Preview
Loading PDF preview...