Euler was a master of generating functions. Here is a little taste. Start with a Haskell data type:

   data Tree x = Leaf | Node x (Tree x) (Tree x)

The question is how many different Trees of size n are there, where n is the number of x values in the tree.

  Size 0: Leaf
  Size 1: Node x Leaf Leaf
  Size 2: Node x (Node x Leaf Leaf) Leaf, Node Leaf (Node x Leaf Leaf)

It turns out this sequence goes 1,1,2,5,14,42,...

Now we do black magic: we take the Tree x = Leaf | Node x (Tree x) (Tree x) equation and replace Tree x with a function T(x), replace each constructor (Leaf or Node) with the number 1, and replace | with +. We get:

  T(x) = 1 + 1*x*T(x)*T(x)

Simplifying:

  T(x) = 1 + xT(x)^2

We can solve that:

  T(x) = (1 - sqrt(1 - 4x))/2x

Now we do a series expansion of T:

  T(x) = 1 + 1x + 2x^2 + 5x^3 + 14x^4 + 42x^5 + ...

https://www.wolframalpha.com/input/?i=series+(1+-+sqrt(1+-+4...

Magic!

You can try it yourself with:

    data List x = Leaf | Node x (List x)
    data Tree2 x = Leaf | Single x | Node x (Tree2 x) (Tree2 x)

And if you're really adventurous, try:

    data Tree3 x = Node x (List (Tree3 x))
    data Tree4 x y = Leaf y | Node x (Tree4 x y) (Tree4 x y)
    data Tree5 x = Tree2 (Tree2 x)
    data Foo x = Leaf x | Node (Foo x)