| Author |
Message |
|
Rezek
Better Than You
Calc Guru
Joined: 24 Apr 2005
Posts: 1229
|
 Posted: 14 Aug 2006 06:44:03 pm Post subject: |
|
|
This is a question my dad asked me and I cannot for the life of me figure it out.
If you have X objects that can be in 4 different areas, what formula would you use to determine all the different combinations they can be in? Multiple objects can be in the same area at the same time. For example, You could have something like this:
Code:
Area 1 | Area 2 | Area 3 | Area 4
No. Obs | 2 | 1 | 0 | 1
No. Obs | 1 | 1 | 1 | 1
No. Obs | 4 | 0 | 0 | 0
No. Obs | 2 | 2 | 0 | 0
Where 'No Objs' is the number of objects in that area. This is just some sample data dto give you an idea of the end goal, note that you must use all objects, but you can have 0 in some areas.
What formula would I use to determine how many 'rows' are possible?
Last edited by Guest on 14 Aug 2006 06:48:52 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 15 Aug 2006 08:37:22 am Post subject: |
|
|
Add an object to each of the areas. Now we're solving a similar problem with X+4 objects, but there has to be at least one object in each area.
Think of it as putting 3 separators in between the objects to divide them into 4 groups. There are X+3 places to put a separator, so this is just (X+3)(X+2)(X+1)/6.
Last edited by Guest on 15 Aug 2006 08:39:44 am; edited 1 time in total |
|
| Back to top |
|
|
Rezek
Better Than You
Calc Guru
Joined: 24 Apr 2005
Posts: 1229
|
| Posted: 15 Aug 2006 10:03:11 am Post subject: |
|
|
| Alright, that works :biggrin: but I'd like to understand how it works... I understand where you're going until you whip out the formula, which describes all the possible places the seperators could go, right? And it looks like something to do with factorials...? |
|
| Back to top |
|
|
Tiberious726
Advanced Member
Joined: 07 Oct 2005
Posts: 284
|
| Posted: 15 Aug 2006 10:58:03 am Post subject: |
|
|
| it has been forever since i did this but you use either a permutation or a combination (the nPr and nCr buttons on your calculator) and just count so that 0 is one (like in programing) |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 15 Aug 2006 10:58:58 am Post subject: |
|
|
Once you add an object to each area, your examples above look like this:
Code:
o o o|o o|o|o o
o o|o o|o o|o o
o o o o o|o|o|o
o o o|o o o|o|o
In general, we have X+4 objects, so we have X+3 spaces in between them. Putting 3 separators there is equivalent to choosing 3 out of those X+3 spaces. We use the formula for the number of combinations, which is n!/(k!(n-k)!). In this case, it becomes (X+3)!/(3!X!) which is equivalent to (X+3)(X+2)(X+1)/3!, or (X+3)(X+2)(X+1)/6.
I suppose, in general, for N possible areas, the formula would be (X+1)(X+2)(...)(X+N-1)/(N-1)!
The question also becomes much harder when you can distinguish between the objects. In that case, it's equivalent to finding Stirling numbers of the first kind. There is a moderately complicated recursive formula for those, but any explicit formula is painful even to look at, let alone calculate or do any algebra with.
Last edited by Guest on 15 Aug 2006 02:25:50 pm; edited 1 time in total |
|
| Back to top |
|
|
Rezek
Better Than You
Calc Guru
Joined: 24 Apr 2005
Posts: 1229
|
| Posted: 15 Aug 2006 12:36:12 pm Post subject: |
|
|
I think I'm starting to understand you, although I'd never heard of the'n!/(k!(n-k)!)' formula before. Thanks for all of your help!
Last edited by Guest on 15 Aug 2006 12:36:41 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 15 Aug 2006 12:49:00 pm Post subject: |
|
|
That's the binomial coefficient, which can be utilized in TI-Basic with [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]N nCr K (MATH PRB).
You might also appreciate the Combinatorics articles listed here.
View EXPLORE THIS TOPIC IN MathWorld frequently.
Last edited by Guest on 15 Aug 2006 12:54:39 pm; edited 1 time in total |
|
| Back to top |
|
|
Rezek
Better Than You
Calc Guru
Joined: 24 Apr 2005
Posts: 1229
|
| Posted: 18 Aug 2006 07:32:55 pm Post subject: |
|
|
Alright, so if you hvae X number of objects and Y number of areas, the formula is:
Y!/(X!(Y-X)!)
Right? |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 19 Aug 2006 08:39:51 am Post subject: |
|
|
Rezek wrote: I think I'm starting to understand you, although I'd never heard of the'n!/(k!(n-k)!)' formula before. Thanks for all of your help!
 no offense, but isn't that basic probability stuff? our high school teaches that in its second year of math.
finally, Pascal's Triangle is a related articled you may wish to peruse. http://www.ilovemaths.com/3permcomb.htm is a nice page which explains about permutations, combinations, and the differences between them and is aimed at highschool age students.
Last edited by Guest on 19 Aug 2006 08:46:28 am; edited 1 time in total |
|
| Back to top |
|
|
Rezek
Better Than You
Calc Guru
Joined: 24 Apr 2005
Posts: 1229
|
| Posted: 19 Aug 2006 09:32:05 am Post subject: |
|
|
Quote: no offense, but isn't that basic probability stuff?
This isn't just a 'five people are in line, how many different orders can they be in' question. :roll:
Pascal's Triangle appears to have nothing to do with the problem at hand. And the closest problem on the 'Permutations and Combinations' page to what I'm trying to do was this one:
Quote: Three persons enter a railway carriage, where there are 5 vacant seats. In how many ways can they seat themselves?
Turn 'persons' into X, 'seats' into Y, and then assume that any number of people can be in one chair. How do you figure out all the ways they can sit?
Last edited by Guest on 19 Aug 2006 09:36:20 am; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 19 Aug 2006 09:42:28 am Post subject: |
|
|
First of all, I'd like to point out this isn't probability stuff at all. It's combinatorics stuff. Alright, so the two are, sometimes, connected, but they are quite distinct in that the answer to a probability question is always in the range of 0 to 1, whereas the answer to a combinatorics question almost never is.
I believe elfprince was calling the binomial coefficient formula 'basic probability' and not the original problem (which isn't that hard, but I'd say it's a step beyond anything I've been taught at school).
Last edited by Guest on 19 Aug 2006 09:43:45 am; edited 1 time in total |
|
| Back to top |
|
|
|
Math and Science => Technology & Calculator Open Topic
