Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets.What if there were duplicate elements in the set?That is,the set is a multiset?
Stirling numbers of the second kind on Multiset
7
$\begingroup$
combinatorics
discrete-mathematics
stirling-numbers
multisets
-
0It would be good to add the link to the definition of Stirling numbers: http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind – 2011-01-09
-
1The answer is likely to be somewhat complicated to express. For example, if the set consists of a single type of element, you get the partition numbers p_{n,k} : http://en.wikipedia.org/wiki/Partition_(number_theory) – 2011-01-09
-
2I think [math] is a pretty useless tag in this site; I've deleted it and added [counting] – 2011-01-10
4 Answers
2
There is no known formulation for a general multiset. However, a paper at JIS tackles the case where the element 1 occurs multiple times.
1
Here are two links to get you started:
Eulerian numbers of the second kind may be helpful (for counting ascents, descents, etc., though i think)
Additionally some more useful information may be found in Stanley's book
0
You divide the Stirling number by the possible permutations of identical elements as this is just changing order within the stars and bars example.