Sum[P(0)>=0,P(1)>=0...P(2^n1)>=0,
such that Sum(0<=i<=2^n1,P(i)=n)]n!/(P(1)!P(2)!...P(2^n1)!)
Sum[0<=b<=2^n1]2^{P(2^n1b)}Prod[0<=d<=2^n1]
(1+KroneckerDelta[0,S(d,b)](KroneckerDelta[P(d),0]1) ,
where S(d,b)=0 iff d and b as written in binary digits have two identical pairs of different value. For example b=5 (101) and d=4 (100) have this property because the third digits and the second digits are the same in both of them, but they are of different value.
Bounded by 2^{n^2+n} < a(n) < 2^{2n^2+n}.
