Let a be the number of objects.
Let b be the number of objects in a group.
Let A[a] is the number of permutations of a objects ( A[2] = 2, A[3] = 2*3, A[4] = 2*3*4...)

So:
f[a][b] is the number of groups with b objects.
You have the formula:
f[a][b] = f[a-1][b] * b + f[a-1][b-1];
And the result = f[n][1] * A[1] + f[n][2] * A[2] + ... + f[n][3] * A[3]

A group is formed by equal objects in a relation.
For example:
a = b < c = d (2 groups ab and cd)
a = b < c < d (3 groups ab, c and d)
...

I think when N is increased to 1000, everyone will solve it by DP or maths, not cheat :-)