User talk:Geoffrey Critzer

a(n) = the number of functions f:[n]->[n] such that f(1)=1, for all n>=1,f(n+1)<=f(n)+1. a(n) = the Catalan numbers.

A very nice bijection between this set and the set of length 2n Dyck words is on page 333 at http://www.jjj.de/fxt/#fxtbook

Here is a generating function in 4 variables that counts functions f:{1,2,...,n}->{1,2,...,n} .

 (1- z exp( w T(x)))^-y  where T(x) = Sum_{n>=1} n^(n-1)x^n/n!

The coefficient (after multiplying by n!) of y^k z^j w^m x^n is the number of functions on [n] that have k cycles, j recurrent elements, and m nonrecurrent elements mapped to a recurrent element.

Here are 3 generating functions for the number of integer partitions of n into distinct parts.

G.f.: Product_{m >= 1} (1 + x^m) = 1/Product_{m >= 0} (1-x^(2m+1)) = Sum_{k>=0} Product_{i=1..k} x^i/(1-x^i).

The number of partitions into distinct parts = the number of partitions into odd parts. The number of partitions of n into exactly k distinct parts = the number of partitions with at least one 1, one 2, ... one k.

Here is a generating function in 4 variables that counts simple labeled graphs.

exp(z*x)^y * exp(x)^-y * (Sum_{n>=0} (1 + w) ^ binomial(n,2) x^n/n! )^y