Combinatorial Identities Using the Matrix Tree Theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918217710043136 |
|---|---|
| author | Deepthi, Nayana Shibu Kumar, Chanchal |
| author_facet | Deepthi, Nayana Shibu Kumar, Chanchal |
| contents | In this paper, we explore some interesting applications of the matrix tree theorem. In particular, we present a combinatorial interpretation of a distribution of $(n-1)^{n-1}$, in the context of uprooted spanning trees of the complete graph $K_{n}$, which was previously obtained by Chauve--Dulucq--Guibert. Additionally, we establish a combinatorial explanation for the distribution of $m^{n-1}n^{m-1}$, related to spanning trees of the complete bipartite graph $K_{m,n}$, which seems new. Furthermore, we extend this study to the graph $K_{n}\setminus \{e_{1,n}\}$, obtained by deleting an edge from $K_n$, and derive a new identity for the number of its uprooted spanning trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21319 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Combinatorial Identities Using the Matrix Tree Theorem Deepthi, Nayana Shibu Kumar, Chanchal Combinatorics 05C30, 05C50, 05C05 In this paper, we explore some interesting applications of the matrix tree theorem. In particular, we present a combinatorial interpretation of a distribution of $(n-1)^{n-1}$, in the context of uprooted spanning trees of the complete graph $K_{n}$, which was previously obtained by Chauve--Dulucq--Guibert. Additionally, we establish a combinatorial explanation for the distribution of $m^{n-1}n^{m-1}$, related to spanning trees of the complete bipartite graph $K_{m,n}$, which seems new. Furthermore, we extend this study to the graph $K_{n}\setminus \{e_{1,n}\}$, obtained by deleting an edge from $K_n$, and derive a new identity for the number of its uprooted spanning trees. |
| title | Combinatorial Identities Using the Matrix Tree Theorem |
| topic | Combinatorics 05C30, 05C50, 05C05 |
| url | https://arxiv.org/abs/2504.21319 |