my answer

來源: 2009-01-19 14:43:59 [博客] [舊帖] [給我悄悄話] 本文已被閱讀:

If both balls and boxes are distinguishable, there are 3^n ways to put balls.

Let assume
for no box is empty, there are m ways to put balls.
for only one box is empty, there are l ways to put balls.
for 2 boxes are empty, 3 ways to put balls
Here m+l+3=3^n

then think of boxes are distinguishable,and boxes can be empty.
m/3!+l/(3*2!)+3/3=(m+l+3+3)/6=(3^n+3)/6=(3^(n-1)+1)/2

for非空子集:
(3^(n-1)+1)/2-2^n/2=(3^(n-1)-2^n+1)/2