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. Permutation-based St ...
Article

Permutation-based Strategies for Labeled Chip-Firing on $k$-ary Trees

Ryota Inagaki ORCID (1), Tanya Khovanova (1), Austin Luo ORCID (2)
(1) Massachusetts Institute of Technology [MIT]
(2) Morgantown High School
Download article
Open on arXiv
Submitted on
July 24, 2025
Accepted on
December 19, 2025
Published on
January 9, 2026
Last modified on
January 9, 2026
Volume 28
vol. 28:2
Combinatorics
DOI
10.46298/dmtcs.16108
License
Attribution 4.0 International (CC BY 4.0)
Indicators
803
Views
435
Downloads

Permutation-based Strategies for Labeled Chip-Firing on $k$-ary Trees

Ryota Inagaki ORCID (1), Tanya Khovanova (1), Austin Luo ORCID (2)
(1) Massachusetts Institute of Technology [MIT]
(2) Morgantown High School
Abstract
Chip-firing is a combinatorial game on a graph, in which chips are placed and dispersed among its vertices until a stable configuration is achieved. We specifically study a chip-firing variant on an infinite, rooted, directed $k$-ary tree where we place $k^n$ chips labeled $0,1,\dots, k^n-1$ on the root for some nonnegative integer $n$, and we say a vertex $v$ can fire if it has at least $k$ chips. When a vertex fires, we select $k$ labeled chips and send the $i$th smallest chip among them to its $i$th leftmost child. A stable configuration is reached when no vertex can fire. In this paper, we focus on stable configurations resulting from specific firing strategies based on permutations of $1, 2, \dots, n$. We then express the stable configuration as a permutation of $0,1, 2, \dots, k^n-1$ and explore its properties, such as the number of inversions and descents. 20 pages, 4 figures, 1 table, v4: final version
Keywords
  • Combinatorics
  • 05C57, 05C63, 05A05, 05A15
Mathematics Subject Classification 2020
  • 05A05 - Permutations, words, matrices
  • 05A15 - Exact enumeration problems, generating functions
  • 05C57 - Games on graphs (graph-theoretic aspects)
  • 05C63 - Infinite graphs
  • 91A43 - Games involving graphs
Preview
Loading PDF preview...