|
|
| 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 k-element subsets
|
|
|
Hello,
I want to calculate the number of partitions of an n-element 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 n-element 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 k-element subsets
|
|
|
Jan Ellenbeck wrote:
| Quote: | Hello,
I want to calculate the number of partitions of an n-element 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 n-element 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 k-element subsets
|
|
|
Proginoskes wrote:
| Quote: | Jan Ellenbeck wrote:
I want to calculate the number of partitions of an n-element 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 k-element subsets
|
|
|
Jan Ellenbeck wrote:
| Quote: | Proginoskes wrote:
Jan Ellenbeck wrote:
I want to calculate the number of partitions of an n-element 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 Fri Sep 21, 2018 11:36 am | All times are GMT
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums |
send newsletters
|
| |
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
