FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
Number of set partitions with maximum k-element subsets
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Jan Ellenbeck
science forum beginner


Joined: 04 Mar 2006
Posts: 2

PostPosted: Sat Mar 04, 2006 10:42 pm    Post subject: Number of set partitions with maximum k-element subsets Reply with 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!

Thanks in advance

Jan
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Mar 05, 2006 5:52 am    Post subject: Re: Number of set partitions with maximum k-element subsets Reply with quote

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

PostPosted: Sun Mar 05, 2006 8:31 pm    Post subject: Re: Number of set partitions with maximum k-element subsets Reply with quote

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

PostPosted: Mon Mar 06, 2006 5:34 am    Post subject: Re: Number of set partitions with maximum k-element subsets Reply with quote

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
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Mon Jun 26, 2017 10:29 pm | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts a subset of natural number levine121323@yahoo.com Math 1 Fri Jul 21, 2006 6:17 am
No new posts Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm
No new posts Hofstadter's _GEB_ -- Help with number theory Daniel al-Autistiqui Math 3 Tue Jul 18, 2006 5:33 pm
No new posts Number Theory Danilo num-analysis 1 Sat Jul 15, 2006 2:57 am

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
[ Time: 0.1997s ][ Queries: 16 (0.1821s) ][ GZIP on - Debug on ]