Labeled trees, functions, and an algebraic identity

zbMATH Open1337.05056arXiv1106.3221MaRDI QIDQ640448FDOQ640448

Stephan Wagner

Publication date: 18 October 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We give a short and direct proof of a remarkable identity that arises in the enumeration of labeled trees with respect to their indegree sequence, where all edges are oriented from the vertex with lower label towards the vertex with higher label. This solves a problem posed by Shin and Zeng in a recent article. We also provide a generalization of this identity that translates to a formula for the number of rooted spanning forests with given indegree sequence.

Full work available at URL: https://arxiv.org/abs/1106.3221

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 3926929
• A bijective enumeration of labeled trees with given indegree sequence
• A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
• Counting labelled trees with given indegree sequence
• A combinatorial identity for rooted labeled forests

zbMATH Keywords

rooted spanning forests

Mathematics Subject Classification ID

Trees (05C05) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

Cited In (5)

• A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
• On an identity for the cycle indices of rooted tree automorphism groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locally oriented noncrossing trees

This page was built for publication: Labeled trees, functions, and an algebraic identity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640448)