Introduction to Graph Theory · Problem 5.23

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · n-potent-maps-cayley

Problem

Let nn be a positive integer. Let N={1,2,…,n}N = \{1, 2, \ldots, n\}. A map f:N→Nf : N \to N is said to be nn-potent if each i∈Ni \in N satisfies fn−1(i)=nf^{n-1}(i) = n. (As usual, fkf^k denotes the kk-fold composition f∘f∘⋯∘ff \circ f \circ \cdots \circ f.) Prove that the #\# of nn-potent maps f:N→Nf : N \to N is nn−2n^{n-2}. [Hint: What do these nn-potent maps have to do with trees?]

Related theory

Browse the problem library