X-Nico

unusual facts about pseudoforest


Pseudoforest

André Joyal used this fact to provide a bijective proof of Cayley's formula, that the number of undirected trees on n nodes is nn − 2, by finding a bijection between maximal directed pseudoforests and undirected trees with two distinguished nodes.


Similar

pseudoforest |

Combinatorial proof

An alternative bijective proof, given by Aigner and Ziegler and credited by them to André Joyal, involves a bijection between, on the one hand, n-node trees with two designated nodes (that may be the same as each other), and on the other hand, n-node directed pseudoforests.


see also