4
$\begingroup$

I was wondering what algorithm would compute

S(n, k {occurences of each element})  

Where

S(6, 3, {1, 2, 3} )

would give the total number of ways a set with 6 elements in which 3 are the same element and a different 2 are another element (and 1 is its unique element) could be split into 3 non-empty sets, ignoring permutations.

This is basically the extension of Stirling numbers of the second kind to deal with multisets.

$\endgroup$

migrated from scicomp.stackexchange.com Dec 31 '14 at 15:57

This question came from our site for scientists using computers to solve scientific problems.

  • $\begingroup$ What is the problem that you are trying to solve? $\endgroup$ – Kirill Dec 30 '14 at 7:24
  • $\begingroup$ How to compute number of unique ways to split a multiset into a given number of non-empty subsets. Ignore permutations, and treat all repeated elements as identical. $\endgroup$ – robertkin Dec 30 '14 at 21:18
  • $\begingroup$ No, that's not my question. What is the actual problem that gave rise to this question? Why is this particular combinatorics question of interest? $\endgroup$ – Kirill Dec 30 '14 at 22:02
  • $\begingroup$ I was simply learning about stirling numbers and was thinking about how to expand it to deal with repeated elements. There's no general formula for it, so I was looking for an algorithm to do so $\endgroup$ – robertkin Dec 31 '14 at 1:38
  • $\begingroup$ Interesting question, but probably better suited for the math stackexchange. $\endgroup$ – Nick Alger Dec 31 '14 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.