Number of unordered partitions of a given cardinality

Arrangements, combinations and permutations, probability, ...
Post Reply
Jack Tarantula
Posts: 1
Joined: Fri Nov 20, 2015 8:02 am

Number of unordered partitions of a given cardinality

Post by Jack Tarantula » Fri Nov 20, 2015 8:10 am

Dear all,
suppose that I have N distinct elements, I would like to count the number of ways that they can be arranged in subsets of cardinality m1,m2,...,mK such that m1+m2+...+mK = N.

Example: I have N=4 elements, and I want to count the number of partitions of cardinality [2,1,1], that is
{1,2}{3}{4}
{1,3}{2}{4}
{1,4}{2}{3}
{2,3}{1}{4}
{2,4}{1}{3}
{3,4}{1}{2}
=6

Is there any general formula to compute this number?
Many thanks.

MuthuVeerappanR
Posts: 352
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Number of unordered partitions of a given cardinality

Post by MuthuVeerappanR » Fri Nov 20, 2015 10:19 am

Stirling numbers of the first and second kind would help I suppose...
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Number of unordered partitions of a given cardinality

Post by mpiotte » Fri Nov 20, 2015 12:17 pm

If I understand correctly, what you are looking for is probably https://en.wikipedia.org/wiki/Multinomial_theorem.
Image

Post Reply