This kind of expansion is called a Lie series. I didn't check the author's derivation, but formulas of this type are well known. Unfortunately I don't know of a really good introductory reference.

You might also look at F. Harary, R. W. Robinson, and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc. 20 (Series A) (1975), 483-503. link

Also by Taylor's theorem, the polynomials $\phi_n(y)$ have the generating function $$\sum_{n=0}^\infty \phi_n(y) \frac{z^n}{n!} = \exp\left(-z\left(1-\frac{y^2}{1+yz}\right)\right). $$

Here is an explanation of $s_2\circ s_2$ in ‘simple terms‘. Here we have permutation representations: $s_2$ is the characteristic of $S_2$ acting on the single set $\{1,2\}$ by permutating 1 and 2. This is the trivial representation, since $S_2$ is acting on a single element. The plethysm $s_2\circ s_2$ is the characteristic of $S_4$ acting on partitions of $\{1,2,3,4\}$ into two blocks of size 2; i.e. acting on the three partitions $\{\{1,2\},\{3,4\}\},$ $\{\{1,3\},\{2,4\}\},$ and $\{\{1,4\},\{2,3\}\},$ by permuting 1, 2, 3, and 4.

Note that $g=e^f$ implies $g' = gf'$. This gives a recurrence for the coefficients of $g$ that's easy to use.

Alternatively, equate coefficients of $x^n$ in $$\frac{1}{1-x} = \exp\biggl(\sum_{a=1}^\infty \frac{x^a}{a}\biggr).$$

This result has also been attributed to Ramachandra (mathoverflow.net/questions/87048/…).

According to Dickson's History of the Theory of Numbers, Volume 1, p. 84 (archive.org/details/historyoftheoryo01dick) this generalization of Fermat's theorem is due to Gauss, at least when $a$ is a prime. On p. 82 Dickson gives a reference for the general case to Thue in 1910, though it may be older.

There's a proof of Pólya's theorem by Gian-Carlo Rota and David Smith using Möbius inversion along the lines that gowers suggests, but the usual proof of Burnside's lemma is much easier. See Rota, Gian-Carlo; Smith, David A. Enumeration under group action. Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Sér. 4, 4 no. 4 (1977), p. 637-646 numdam.org/item?id=ASNSP_1977_4_4_4_637_0

This is not a power series, so it doesn't have a radius of convergence.

If we change the upper limit of the sum to $n$ then the sum is the $n$th difference of a polynomial of degree $n-1$ and is therefore 0. The only nonzero term in the extended sum not in the restricted sum is $-1$, corresponding to $m=n$.