My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 10th, 2007, 08:38 AM   #1
Newbie
 
Joined: May 2007

Posts: 2
Thanks: 0

Possible exhaustive groupings of N objects?

I have a question:
If you have N objects, what is the possible number of ways that you can exhaustively group them (i.e. group them without having any objects left over?) For example:

for N = 2; there are 2 possible groupings:
[AB]
[A] + [B]

for N = 3; there are 5 possible groupings:
[ABC]
[AB] + [C]
[AC] + [B]
[BC] + [A]
[A] + [B] + [C]

for N=4, there are (I think) 15:
[ABCD]
[ABC]+[D]
[ABD]+[C]
[ACD]+[B]
[BCD]+[A]
[AB]+[CD]
[AB]+[C]+[D]
[A]+[B]+[CD]
[BC]+[AD]
[BC]+[A]+[D]
[B]+[C]+[AD]
[AC]+[BD]
[A]+[C]+[BD]
[AC]+[B]+[D]
[A]+[B]+[C]+[D]

Any help would be greatly appreciated.
Thanks,
Ed
edbeaty is offline  
 
May 10th, 2007, 10:45 AM   #2
Senior Member
 
Joined: Dec 2006

Posts: 1,111
Thanks: 0

Hmm... Is this related to the problem of putting n labeled balls into n indistinguishable boxes? See sequence A000110.
Infinity is offline  
May 10th, 2007, 11:38 AM   #3
Newbie
 
Joined: May 2007

Posts: 2
Thanks: 0

I think you're right. I saw this before, but was thrown by the main title. Looking lower, it does say:
Quote:
Number of partitions of an n-element set.
which is what I'm looking for. (Slaps forehead) D'oh! Of course it's the same: any empty "boxes" in the answer don't matter:

[ABC] + [] + []
[AB] + [C] + []
[AC] + [B] + []
[BC] + [A] + []
[A] + [B] + [C]

is equivalent to

[ABC]
[AB] + [C]
[AC] + [B]
[BC] + [A]
[A] + [B] + [C]

...at least for calculating the number of possible solutions. I found a nice description is on the WikiPedia: http://en.wikipedia.org/wiki/Partition_of_a_set

Thanks a lot for your help!
-Ed
edbeaty is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
exhaustive, groupings, objects



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
what is definition of Exhaustive? r-soy Algebra 1 November 17th, 2013 02:23 PM
How to compare two objects? Natalia Abstract Algebra 1 July 6th, 2013 03:27 PM
Motion of objects Mathforum1000 Physics 2 July 14th, 2012 07:04 AM
Objects in set Khalid Mahmood Applied Math 4 April 19th, 2008 03:30 PM
Motion of objects Mathforum1000 Applied Math 0 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.