HN Explorer

6 comments

[ 3.7 ms ] story [ 18.1 ms ] thread
wz1000
> Set(A) = ∑n A^n/n! = e^A since there are n! permutations to quotient by.

But this is wrong. The number of sets over A={0,1,2} is 2^3 = 8 /= e^3

The actual series should be

    Set(A) = ∑n (A*(A-1)*(A-2)..(A-n+1))/n! = 2^A
This is also consistent with the fact that Set(A) ~ A -> Bool
zawerf
How do you interpret the derivative of that? It's now log(2)*2^A.

What does "log(2)" mean as a type here? Do you expand it back out as a taylor series like in the circular list example?

danharaj
Right, that is the formula for multisets, or bags as they are also called.
wz1000
No, I believe the formula for multisets would be

    M(x) = ∑n (A*(A+1)*(A+2)..(A+n-1))/n!
since there are (n+k+1)c(k+1) possible unordered n-tuples over a set with cardinality k.
black_knight
∑Aⁿ/n! actually represents the multisets (aka bags) of elements from A. A multiset is a list, but we quotient out by permutations (hence n!)

The division here can be seen as an action of the permutation group (which has n! element).