Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
Author Message
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})

http://mathworld.wolfram.com/YoungTableau.html
http://mathworld.wolfram.com/FerrersDiagram.html

--- Christopher Heckman
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
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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Sat Feb 16, 2019 4:57 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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