Author 
Message 
Jan Ellenbeck science forum beginner
Joined: 04 Mar 2006
Posts: 2

Posted: Sat Mar 04, 2006 10:42 pm Post subject:
Number of set partitions with maximum kelement subsets



Hello,
I want to calculate the number of partitions of an nelement set into
disjoint subsets of cardinality <= k.
The problem looks easy but studying my textbooks and searching the
Internet, I only found the Stirling numbers of the second kind (number
of partitions of an nelement set into k subsets) and the Bell numbers
(total number of set partitions).
Both formulas do not describe what I am looking for: On the one hand,
I do not want to limit the number of subsets, but their
cardinalities. On the other hand, the number of subsets doesn't matter
but the subsets should contain no more than k elements.
Unfortunately, I could not find a solution myself so that I would
appreciate any hints!
Thanks in advance
Jan 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Sun Mar 05, 2006 5:52 am Post subject:
Re: Number of set partitions with maximum kelement subsets



Jan Ellenbeck wrote:
Quote:  Hello,
I want to calculate the number of partitions of an nelement set into
disjoint subsets of cardinality <= k.
The problem looks easy but studying my textbooks and searching the
Internet, I only found the Stirling numbers of the second kind (number
of partitions of an nelement set into k subsets) and the Bell numbers
(total number of set partitions).
Both formulas do not describe what I am looking for: On the one hand,
I do not want to limit the number of subsets, but their
cardinalities. On the other hand, the number of subsets doesn't matter
but the subsets should contain no more than k elements.
Unfortunately, I could not find a solution myself so that I would
appreciate any hints!

The answers to the two problems:
(1) number of partitions of n elements into sets of size <= k
(2) number of partitions of n elements into at most k sets
are the same! The proof is via "Young tableaus".
Let's suppose you have a permutation of 10 elements into any number of
sets with at most 4 elements. Let's take the partition (4,4,2). Write
out a row of 4 *'s, a row of 4 *'s, and a row of 2 *'s:
****
****
**
Now read the diagram via columns: 3 *'s, 3*'s, 2 *'s, and 2 *"s. This
is the partition (3,3,2,2), a partition of 10 elements into at most 4
sets with any number of elements in any set.
 Christopher Heckman 

Back to top 


Jan Ellenbeck science forum beginner
Joined: 04 Mar 2006
Posts: 2

Posted: Sun Mar 05, 2006 8:31 pm Post subject:
Re: Number of set partitions with maximum kelement subsets



Proginoskes wrote:
Quote:  Jan Ellenbeck wrote:
I want to calculate the number of partitions of an nelement set into
disjoint subsets of cardinality <= k.
The answers to the two problems:
(1) number of partitions of n elements into sets of size <= k
(2) number of partitions of n elements into at most k sets
are the same! The proof is via "Young tableaus".
Let's suppose you have a permutation of 10 elements into any number of
sets with at most 4 elements. Let's take the partition (4,4,2). Write
out a row of 4 *'s, a row of 4 *'s, and a row of 2 *'s:
****
****
**
Now read the diagram via columns: 3 *'s, 3*'s, 2 *'s, and 2 *"s. This
is the partition (3,3,2,2), a partition of 10 elements into at most 4
sets with any number of elements in any set.

First of all, thanks a lot for your help!
I see that with the Young Tableaux I get a bijection between the sets
holding {4,4,2} and {3,3,2,2} so that it is clear that they have the
same size. But my question was about partitioning a set of n
distinguishable objects into subsets of size <= k.
In your example, there should be
(10 \choose 4) * (6 \choose 4) * (2 \choose 2)
such partitions with set sizes {4,4,2} and
(10 \choose 3) * (7 \choose 3) * (4 \choose 2) * (2 \choose 2)
partitions with set sizes {3,3,2,2}.
So, the number of set partitions for problems 1) and 2) should not be
equal? Or does this somehow balance out when summing over all
partitions?
Thanks again,
Jan 

Back to top 


Proginoskes science forum Guru
Joined: 29 Apr 2005
Posts: 2593

Posted: Mon Mar 06, 2006 5:34 am Post subject:
Re: Number of set partitions with maximum kelement subsets



Jan Ellenbeck wrote:
Quote:  Proginoskes wrote:
Jan Ellenbeck wrote:
I want to calculate the number of partitions of an nelement set into
disjoint subsets of cardinality <= k.
The answers to the two problems:
(1) number of partitions of n elements into sets of size <= k
(2) number of partitions of n elements into at most k sets
are the same! The proof is via "Young tableaus".
Let's suppose you have a permutation of 10 elements into any number of
sets with at most 4 elements. Let's take the partition (4,4,2). Write
out a row of 4 *'s, a row of 4 *'s, and a row of 2 *'s:
****
****
**
Now read the diagram via columns: 3 *'s, 3*'s, 2 *'s, and 2 *"s. This
is the partition (3,3,2,2), a partition of 10 elements into at most 4
sets with any number of elements in any set.
First of all, thanks a lot for your help!
I see that with the Young Tableaux I get a bijection between the sets
holding {4,4,2} and {3,3,2,2} so that it is clear that they have the
same size. But my question was about partitioning a set of n
distinguishable objects into subsets of size <= k.
In your example, there should be
(10 \choose 4) * (6 \choose 4) * (2 \choose 2)
such partitions with set sizes {4,4,2} and
(10 \choose 3) * (7 \choose 3) * (4 \choose 2) * (2 \choose 2)
partitions with set sizes {3,3,2,2}.
So, the number of set partitions for problems 1) and 2) should not be
equal? Or does this somehow balance out when summing over all
partitions?

Whoops ... the argument only seems to work if all n objects are
considered identical. Otherwise you can get duplication, and the
picture is called a Ferrers Diagram.
For instance, the partition ({1,2,3,4},{5,6,7,8},{9,0}) (as a {4,4,2}
partition) has at least two Young tableaus (tableaux):
1234
5678
90
1243 since {1,2,3,4} = {1,2,4,3}.
5678
90
but the "transposes" turn out to be the partitions
({1,5,9},{2,6,0},{3,7},{4,8}) and ({1,5,9},{2,6,0},{4,7},{3,8})
Check out the links:
http://mathworld.wolfram.com/YoungTableau.html
http://mathworld.wolfram.com/FerrersDiagram.html
 Christopher Heckman 

Back to top 


Google


Back to top 



The time now is Sat Nov 25, 2017 1:46 am  All times are GMT

