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. Minimal Factorizatio ...
Conference paper

Minimal Factorizations of Permutations into Star Transpositions

J. Irving (1), A. Rattan (2)
(1) Department of Mathematics and Computing Science [Halifax]
(2) Department of Mathematics [Cambridge]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Proceedings
DOI
10.46298/dmtcs.3595
License
https://about.hal.science/hal-authorisation-v1
Natural Sciences and Engineering Research Council of Canada
Indicators
564
Views
1172
Downloads

Minimal Factorizations of Permutations into Star Transpositions

J. Irving (1), A. Rattan (2)
(1) Department of Mathematics and Computing Science [Halifax]
(2) Department of Mathematics [Cambridge]
Abstract
English
We give a compact expression for the number of factorizations of any permutation into a minimal number of transpositions of the form $(1 i)$. Our result generalizes earlier work of Pak ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) in which substantial restrictions were placed on the permutation being factored.
French
Nous présentons une expression compacte pour le nombre de factorisations minimales d'une permutation arbitraire de transposition de la forme $(1 i)$. Ce résultat généralise le travail passé de Pak ($\textit{Reduced decompositions of permutations in terms of star transpositions, generalized catalan numbers and k-ary trees}$, Discrete Math. $\textbf{204}$:329―335, 1999) dans lequel des restrictions substantielles sont imposées sur la permutation étant factorisée.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • factorizations
  • permutations
  • star transpositions
  • symmetric group
Cited by

Source: OpenCitations

  • Euler numbers and diametral paths in Fibonacci cubes, Lucas cubes and alternate Lucas cubes

    Discrete Mathematics Algorithms and Applications

    Authors : Ömer Eğeci̇oğlu ORCID, Elif Saygi ORCID, Zülfükar Saygi ORCID

    Journal reference : Volume 16, 2023, pp.

    DOI : 10.1142/s1793830923500271

  • Task swapping networks in distributed systems

    arXiv (Cornell University)

    Authors : Dohan Kim ORCID

    Journal reference : Volume 90, 2013, pp. 2221-2243

    DOI : 10.1080/00207160.2013.772985

  • A combinatorial proof of symmetry among minimal star factorizations

    Discrete Mathematics

    Authors : Bridget Eileen Tenner ORCID

    Journal reference : Volume 312, 2012, pp. 2482-2490

    DOI : 10.1016/j.disc.2012.04.021

  • The Number of Shortest Paths in the (n, k)-Star Graphs

    Lecture notes in computer science

    Authors : Eddie Cheng ORCID, Ke Qiu ORCID, Zhi Zhang Shen ORCID

    Journal reference : Volume , 2010, pp. 222-236

    DOI : 10.1007/978-3-642-17458-2_19

  • Partial Jucys–Murphy elements and star factorizations

    European Journal of Combinatorics

    Authors : Valentin Féray ORCID

    Journal reference : Volume 33, 2011, pp. 189-198

    DOI : 10.1016/j.ejc.2011.09.035

  • Centrality of star and monotone factorisations

    Bulletin of the London Mathematical Society

    Authors : Jesse Campion Loth, Amarpreet Rattan

    Journal reference : Volume 57, 2025, pp. 3567-3585

    DOI : 10.1112/blms.70170

  • On the Problem of Determining which (n, k)-Star Graphs are Cayley Graphs

    Graphs and Combinatorics

    Authors : Eddie Cheng ORCID, Li Li ORCID, László Lipták ORCID, Sangho Shim ORCID, Daniel E. Steffy ORCID

    Journal reference : Volume 33, 2016, pp. 85-102

    DOI : 10.1007/s00373-016-1741-8

  • Star factorizations and noncrossing partitions

    arXiv (Cornell University)

    Authors : Bridget Eileen Tenner ORCID

    Journal reference : Volume 344, 2021, pp. 112428

    DOI : 10.1016/j.disc.2021.112428

  • Combinatorial and Algebraic Enumeration: a survey of the work of Ian P. Goulden and David M. Jackson

    Algebraic Combinatorics

    Authors : Angèle M. Foley, Alejandro H. Morales ORCID, Amarpreet Rattan, Karen Yeats

    Journal reference : Volume 5, 2022, pp. 1205-1226

    DOI : 10.5802/alco.269

  • Distance formula and shortest paths for the (n,k)-star graphs

    Information Sciences

    Authors : Eddie Cheng ORCID, Jerrold W. Grossman, László Lipták ORCID, Ke Qiu ORCID, Zhizhang Shen ORCID

    Journal reference : Volume 180, 2010, pp. 1671-1680

    DOI : 10.1016/j.ins.2010.01.016

  • The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees

    Annales Henri Lebesgue

    Authors : Valentin Féray ORCID, Igor Kortchemski

    Journal reference : Volume 1, 2019, pp. 149-226

    DOI : 10.5802/ahl.5

  • Character-theoretic techniques for near-central enumerative problems

    Journal of Combinatorial Theory Series A

    Authors : David M. Jackson, Craig A. Sloss

    Journal reference : Volume 119, 2012, pp. 1665-1679

    DOI : 10.1016/j.jcta.2012.05.004

  • The number of shortest paths in the (n, k)-star graph

    Discrete Mathematics Algorithms and Applications

    Authors : Eddie Cheng ORCID, Ke Qiu ORCID, Zhizhang Shen ORCID

    Journal reference : Volume 06, 2014, pp. 1450051

    DOI : 10.1142/s1793830914500517

  • A Central Limit Theorem for Star-Generators of $${S}_{\infty }$$, Which Relates to the Law of a GUE Matrix

    Journal of Theoretical Probability

    Authors : Claus Köstler, Alexandru Nica

    Journal reference : Volume 34, 2020, pp. 1248-1278

    DOI : 10.1007/s10959-020-01029-6

  • Random induced subgraphs of Cayley graphs induced by transpositions

    Discrete Mathematics

    Authors : Emma Yu Jin ORCID, Christian M. Reidys ORCID

    Journal reference : Volume 311, 2011, pp. 2496-2511

    DOI : 10.1016/j.disc.2011.07.027

  • Bi-pruned Hurwitz numbers

    Journal of Combinatorial Theory Series A

    Authors : Marvin Anas Hahn ORCID

    Journal reference : Volume 174, 2020, pp. 105240

    DOI : 10.1016/j.jcta.2020.105240

  • A note on fully commutative elements in complex reflection groups

    Discrete Mathematics

    Authors : Jiayuan Wang ORCID

    Journal reference : Volume 346, 2023, pp. 113611

    DOI : 10.1016/j.disc.2023.113611

  • Random monotone factorisations of the cycle and their lamination process

    Electronic Journal of Probability

    Authors : Etienne Bellin ORCID

    Journal reference : Volume 30, 2025, pp.

    DOI : 10.1214/25-ejp1423

  • Sorting on graphs by adjacent swaps using permutation groups

    Computer Science Review

    Authors : Dohan Kim ORCID

    Journal reference : Volume 22, 2016, pp. 89-105

    DOI : 10.1016/j.cosrev.2016.09.003

  • The number of shortest paths in the arrangement graph

    Information Sciences

    Authors : Eddie Cheng ORCID, Jerrold W. Grossman, Ke Qiu ORCID, Zhizhang Shen ORCID

    Journal reference : Volume 240, 2013, pp. 191-204

    DOI : 10.1016/j.ins.2013.03.035
Preview
Loading PDF preview...