Needs help with math (possible combinations)

[MacFall]

I'm trying to figure out a formula for the number of possible combinations for a group of 20 objects. This is NOT a question about permutations. Each object can only occur once, but also, they can only occur in a particular order.

There would be no reorganizing them to produce different combinations.
So that means that if all the objects are present, there's only one possible combination. If they were represented by letters:

ABCDEFGHIJKLMNOPQRST

(obviously)

With only one possible object, there are 20 different versions.

A B C D E F G H I J K L M N O P Q R S T

(again, obviously)

With two possible objects:

AB AC AD AE AF AG AH AI AJ AK AL AM AN AO AP AQ AR AS AT
   BC BD BE BF BG BH BI BJ BK BL BM BN BO BP BQ BR BS BT
      CD CE CF CG CH CI CJ CK CL CM CN CO CP CQ CR CS CT
         DE DF DG DH DI DJ DK DL DM DN DO DP DQ DR DS DT
            EF EG EH EI EJ EK EL EM EN EO EP EQ ER ES ET
               FG FH FI FJ FK FL FM FN FO FP FQ FR FS FT
                  GH GI GJ GK GL GM GN GO GP GQ GR GS GT
                     HI HJ HK HL HM HN HO HP HQ HR HS HT
                        IJ IK IL IM IN IO IP IQ IR IS IT
                           JK JL JM JN JO JP JQ JR JS JT
                              KL KM KN KO KP KQ KR KS KT
                                 LM LN LO LP LQ LR LS LT
                                    MN MO MP MQ MR MS MT
                                       NO NP NQ NR NS NT
                                          OP OQ OR OS OT
                                             PQ PR PS PT
                                                QR QS QT
                                                   RS RT
                                                      ST

Now, once we get to three objects, that's where I start to lose it. It seems like it would be as above, only starting with "ABC ABD ABE ABF..." then repeating again, without the A: "BCD BCE BCF BCG..."

Then again, without the B: "CDE CDF CDG CDH..."

And so on. It would have to be repeated a total of 18 times, until the last possible combination of RST.

Then when you get to four objects, I THINK it would have to be repeated 18*17 times. Is that correct? If so, then with five objects, it would have to be repeated 17*16, then with six, 16*15.

But I'm just guessing.

Any help?

 

[Boondock_Saint]

Somehow I figured out the second one before I figured out the first one. But I think the second one is a bit easier. Then I just took half the equation from the second one and it happened to solve the first one. This should give us a hint as to what to do with 3 pairs and hopefully help you along.

1. (1/2X)(X-1)
2. (X*Y) - (1/2X)(X-1)
3. ????? this seems tricky. But now out of curiosity, I want to figure this out. If I get it over the next few days, I'll let you know.
------------------------------------------------------------------------------------------------------------------------------------------------------------------

The first equation is (1/2X)(X-1)
X=number of letters.
X=20

1/2X=10
X-1=19

10*19=190

The equation solves A-T (20 letters)
This also works for A-E (5 letters)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------

The second one: This equation (X*Y) - (1/2X)(X-1) gives you the number of pairs you can make
X= the numerical position of the column (1st column, 2nd column, 3rd column...).
Y= number of pairs in each column.

X=4th column
Y=4 pairs in the 4th column.
4*4=16

1/2(4)=2
4-1=3
2(3)=6

16-6=10
10 is the number of combinations for 4 rows and 4 columns.

It works for 5 rows of 5 and for 6 rows of 6.

 

[MacFall]

Argh, I don't understand that. Sorry, I'm really slow with math concepts. What do you mean by rows and columns? And how does that give the number of combinations with more available objects?

 

[Boondock_Saint]

Argh, I don't understand that. Sorry, I'm really slow with math concepts. What do you mean by rows and columns? And how does that give the number of combinations with more available objects?

That's because did not describe the value of X and Y correctly. Give me a minute.

I edited my first post with these changes to the SECOND EQUATION.
Thanks.
X= the numerical position of the column (1st column, 2nd column, 3rd column...).
Y= number of pairs in each column.

X=4th column
Y=4 pairs in the 4th column.

 

[Boondock_Saint]

I'm terrible at explaining. I Hope it helps a little.

 

[Nanopants]

This should be solvable using combinatorics. The forumula you need for the number of combinations is what is known as the binomial coefficient and can be expressed as:

n!/(k!(n-k)!)
​

Where n is the total number of elements to select from, and k is the number of elements in the selection.

 

[Nanopants]

That's because did not describe the value of X and Y correctly. Give me a minute.

I edited my first post with these changes to the SECOND EQUATION.
Thanks.
X= the numerical position of the column (1st column, 2nd column, 3rd column...).
Y= number of pairs in each column.

X=4th column
Y=4 pairs in the 4th column.

If your expressions are correct for those specific cases, I'm going to bet that you could arrive at those same expressions beginning with the binomial coefficient.

 

[Keri]

I can't help with the equations but I noticed in the code box for two objects, "ST" is listed twice.

Not that it matters because I'm sure it's just a typo, but it's bugging me.

 

[Radagast]

Nanopants is right. The pattern is:

singles -- 20
pairs -- 20 * 19 / 2 = 190
triples -- 20 * 19 * 18 / 6 = 1140
etc.

See Combination - Wikipedia, the free encyclopedia

Basically, there are 20 ways to get the first element of a triple, 19 for the second (since one is used), 18 for the third (since two are used). So far that's standard permutations. But 3! = 6 different permutations (ABC, ACB, BAC, BCA, CAB, CBA) are treated the same because of the need for ordering (they're all ABC). Hence the division by 6.

More generally, for k items:

20 * 19 * 18 * ... * (20 + 1 - k) / k!

 

[MacFall]

Ha, thanks Keri. I fixed it.

Everyone else: thank you as well. I'll try parsing this.

 

[MacFall]

This should be solvable using combinatorics. The forumula you need for the number of combinations is what is known as the binomial coefficient and can be expressed as:

n!/(k!(n-k)!)
​

Where n is the total number of elements to select from, and k is the number of elements in the selection.

The exclamation point means a factorial, right?

Also, is there a proof for that in layman's (read: moron's) terms? I'd like to understand why it works.

 

[Nanopants]

And the exclamation point means a factorial, right?

Yes. It's easier to work out though if you cancel out as many terms within each factorial as you can, so that the next step would look like basic algebra.

 

[MacFall]

Yes. It's easier to work out though if you cancel out as many terms within each factorial as you can, so that the next step would look like basic algebra.

I'd just use a factorial calculator to get my number, but see the comment after the one you quoted.

 

[MacFall]

Nanopants is right. The pattern is:

singles -- 20
pairs -- 20 * 19 / 2 = 190
triples -- 20 * 19 * 18 / 6 = 1140
etc.

See Combination - Wikipedia, the free encyclopedia

Basically, there are 20 ways to get the first element of a triple, 19 for the second (since one is used), 18 for the third (since two are used). So far that's standard permutations. But 3! = 6 different permutations (ABC, ACB, BAC, BCA, CAB, CBA) are treated the same because of the need for ordering (they're all ABC). Hence the division by 6.

More generally, for k items:

20 * 19 * 18 * ... * (20 + 1 - k) / k!

Did you get the 6 by multiplying the current value of k by the previous?

 

[Nanopants]

I'd just use a factorial calculator to get my number, but see the comment after the one you quoted.

Well, there was a time when I would have been able to answer that question. I worked it out for myself once several years ago but it wasn't easy. It's an interesting problem though so I'll try to get back to this possibly tomorrow.

 

[Radagast]

Did you get the 6 by multiplying the current value of k by the previous?

6 = 3! where ! = factorial

k! is the number of ways of rearranging k things (you want the permutations ABC, ACB, BAC, BCA, CAB, CBA to all be treated as the same because of ordering).

k! = k * (k - 1) * (k - 2) * ... * 3 * 2 * 1

So:

n * (n - 1) * (n - 2) * ... * (n + 1 - k) = n! / (n - k)!

is the number of permutations of k things, and dividing by k! gives what you wanted (Nanopants's formula):

n * (n - 1) * (n - 2) * ... * (n + 1 - k) = n! / ( (n - k)! k! )

See also the good explanation here: http://www.mathsisfun.com/combinatorics/combinations-permutations.html

 

[m.a.r.X]

m.intmath.com/series-binomial-theorem/4-binomial-theorem.php

 

[friend of]

My goodness how do people do math it boggles the mind

 

[DragonFox91]

My goodness how do people do math it boggles the mind

I don’t understand why people care to remember the most obscure formulas. My initial thought was X! but there’s so many different formulas for the different kinds of variations it could’ve been anything.
I tried X! on a brain teaser I saw the other day & it was wrong of course.

 

[Citanul]

I don’t understand why people care to remember the most obscure formulas.

The binomial coefficient (also known as the "choose" function) is typically found on scientific calculators, so isn't really something that's obscure. For a question like this it's a matter of working through it step by step, and you would come up with the pattern Radagast described.