Partition of Set

Page 1 of 1

14 Replies - 1897 Views - Last Post: 30 September 2013 - 11:08 AM

#1 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Partition of Set

Posted 30 September 2013 - 09:20 AM

Let S be the set {Maine, New Hampshire, Vermont, Massachusetts, Connecticut, Rhode Island} and let R(x, y) be the relation "state x and state y begin with the same letter". How many (non-empty) sets are in the partition of S corresponding to this equivalence relation?

I don't understand that it's asking me number of sets in a partition. Lets say A = {a,b,c,d,e,f}
a, b, c, d , e, f are the elements of A. Would this be a partition,
A = {{a,b,c},{d,e,f}} ? Would {a,b,c} be a partition of A? If so, what am I answer to how many sets are in the first partition of A? In the partition, there are 3 elements, and its asking me sets.

Is This A Good Question/Topic? 0

Replies To: Partition of Set

#2 mostyfriedman

• The Algorithmi

Reputation: 728
• Posts: 4,473
• Joined: 24-October 08

Re: Partition of Set

Posted 30 September 2013 - 09:27 AM

yes, {{a, b, c}, {d, e, f}} is a partition of {a, b, c, d, e, f}. What you need to do is just make a partition according to the relation defined and compute its length.

This post has been edited by mostyfriedman: 30 September 2013 - 09:27 AM

#3 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 09:32 AM

A partition of a set S is a disjoint collection P of nonempty and distinct subsets of S such that each member of S is member of some (and this exactly one) member of P.

Or in more formal terms: For all s in S, there exists some p in P s.t. s in p. (feel free to replace "For all" with "upside down A" and so forth)

#4 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 09:36 AM

is {a,b,c} a partition of {a,b,c,d,e,f}?
So will the original question hold this partition:
{{Maine, Massachusetts}, {New Hampshire}, {Vermont}, {Rhode Island}, {Connecticut}}, giving me the answer 5?

#5 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 09:40 AM

deprosun, on 30 September 2013 - 11:36 AM, said:

is {a,b,c} a partition of {a,b,c,d,e,f}?

Consider e. Is there a set p in your partition s.t. e is in p?
(hint: a partition is a collection of sets)

Quote

So will the original question hold this partition:
{{Maine, Massachusetts}, {New Hampshire}, {Vermont}, {Rhode Island}, {Connecticut}}, giving me the answer 5?

Yes, this is a correct partition according to the specified relation.

#6 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 09:42 AM

Oh!! there isn't. So the correct partition would be {{a,b,c}, {d}, {e}, {f}}...well one possible way of displaying partition.

This post has been edited by deprosun: 30 September 2013 - 09:43 AM

#7 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 09:45 AM

That's a correct partition. You can come up with others - a bit of math will tell you how many to look for. This is a good exercise: how many partitions are there of a set with cardinality N?

#8 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 09:47 AM

2^N.....learned that last semester. Wow,everything just falls into place

#9 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 09:59 AM

Really? Please list the 8 partitions of {a, b, c}

(actually, this is a little harder than I made it sound, but it's fun to think about)

#10 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 10:24 AM

ab, bc, ba, ca, abc, a, b, c. Isn't this just calculating total subsets of {a,b,c}?

This post has been edited by deprosun: 30 September 2013 - 10:25 AM

#11 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 10:29 AM

You're right, the power set of S has cardinality |S|^N. That's a different question, though.

I get five partitions. (using the definition above, which is the standard one)

#12 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 10:52 AM

How did you get five partitions, again? What formula did you use?

#13 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 11:03 AM

Exhaustive list:

{{1,2,3}}
{{1,2},{3}}
{{1,3},{2}}
{{3,2},{1}}
{{1},{2},{3}}

There can be no others. Proof by assertion for the moment, since a real proof is more tedious than informative, but you may feel free to prove it if you like. Use the definition of a partition. (no non-empty members, represents each element of S exactly once)

The math for the general case is found under the heading of "Bell's Number".

#14 deprosun

• D.I.C Regular

Reputation: 0
• Posts: 306
• Joined: 16-November 10

Re: Partition of Set

Posted 30 September 2013 - 11:07 AM

Oh i see. Gotchya. Thanks for taking time!

#15 jon.kiparsky

• Pancakes!

Reputation: 8829
• Posts: 15,238
• Joined: 19-March 11

Re: Partition of Set

Posted 30 September 2013 - 11:08 AM

No bother. Nice to review.