"We have k distinct poscards and want to send them all to our n friends (a friend can get any number of postcards, including 0). How many ways can this be done? What happens if we want to send at least 1 card to each friend?"
"We have k distinct postcards and want to send them all to our n friends (a friend can get any number of postcards, including 0). How many ways can this be done?" -> C(n+k-1,k) (n+k-1 chooses k)
"What happens if we want to send at least 1 card to each friend?" -> C(k-1,n-1) (k-1 chooses n-1)
"I think, for the second one, we may use the second-order Stirling numbers." -> Yes, we can. But now I'm confused: does it mean that my above answer is not correct? If yes, then why?
Obviously, the answer should be zero for n>k. Is it reflected in the second-kind Stirling numbers?
It might be too complicated (or too trivial) to be discussed here. We can talk off-line about it.
I just found the table summarizing the number of ways putting k balls into n boxes in twelve scenarios. More explanation about this table can be found in the book "Enumerative Combinatorics,Volume 1" by Richard P. Stanley.
Yes,S(k,n) = 0 when n > k. It is the number of ways of partitioning a set of k elements into m nonempty sets. From MathWorld , you can see it is not simple to compute S(k,n) at all.
8 comments:
"We have k distinct postcards and want to send them all to our n friends (a friend can get any number of postcards, including 0). How many ways can this be done?"
-> C(n+k-1,k) (n+k-1 chooses k)
"What happens if we want to send at least 1 card to each friend?"
-> C(k-1,n-1) (k-1 chooses n-1)
Hi Loc, I think your solution is true if k postcards are the same. But, in this case, they are distinct.
Oh yeah, that's right. Then the first answer should be n^k, and the second answer is n^(k-n)*n! for n <= k and 0 for n > k.
Hi Loc, the first answer is true. I think, for the second one, we may use the second-order Stirling numbers.
"I think, for the second one, we may use the second-order Stirling numbers."
-> Yes, we can. But now I'm confused: does it mean that my above answer is not correct? If yes, then why?
Obviously, the answer should be zero for n>k. Is it reflected in the second-kind Stirling numbers?
It might be too complicated (or too trivial) to be discussed here. We can talk off-line about it.
Well, after thinking a while, I found that my answer is incorrect :D. But I still wonder whether the Stirling numbers give the answer zero if n>k.
I just found the table summarizing the number of ways putting k balls into n boxes in twelve scenarios. More explanation about this table can be found in the book "Enumerative Combinatorics,Volume 1" by Richard P. Stanley.
Yes,S(k,n) = 0 when n > k. It is the number of ways of partitioning a set of k elements into m nonempty sets. From MathWorld , you can see it is not simple to compute S(k,n) at all.
Post a Comment