Combinatorics problem

Mathegocart · 2017-02-01 15:09:17

1. In the word "Moondust", how many 3- letter combinations are there? I said 168, since (8*7*6)/2 = 168.
The solution is 228. Could someone provide a explanation?

bobbym · 2017-02-01 17:02:25

Hi;

I suggest that you program this one to see why your answer is not correct. Also, I would use the word arrangements instead of combinations.

Moondust

We break the word into how many of each.

{m},{o,o},{n},{d}{u},{s},{t}

There are 6 groups of 1 letter and 1 group of two letters.

That is the exponential generating function. We expand it,

get the coefficient of x^3 which is 38 and times it by 3!.

38 x 3! = 228

Mathegocart · 2017-02-02 03:41:01

That's interesting...

bobbym · 2017-02-02 04:33:08

Nope, mandatory. GF's can solve lots of combinatoric problems and what is more they solve them in the correct manner. They follow the teakettle principle.

Did you get your machine online yet?

Mathegocart · 2017-02-02 09:27:46

Yes, I had to insert another dongle... frustrating..
So I presume GFs are used for a myriad of things, including combinatorics and discrete maths in general?

Last edited by Mathegocart (2017-02-02 09:30:01)

bobbym · 2017-02-02 09:28:26

What make of machine is it?

Mathegocart · 2017-02-02 09:30:42

HP-EliteBook-8560p

bobbym · 2017-02-02 09:40:15

Hmmm, I thought maybe you had a Lenovo.

haidi · 2017-02-04 00:18:08

I don't really understand why people use all that in post #2 for combinatorics problems as simple as this one.
And I don't see how come it's mandatory, unless I'm missing something...

There is A LOT easier way to solve this, without using any formulas at all.
Maybe someone will find it useful, so I'm going to explain in plain English

The word has 8 letters. If they all were different letters, our solution would be 8*7*6=336 (first choose one letter out of eight, then one out of the remaining seven, and one out of the remaining six letters).

But! We want only words that contain three DIFFERENT letters.

Letter "O" appears twice, so we need first to eliminate all the combinations that contain a double "O".

This double "O" can be combined with each of the 6 remaining letters; additionally, the double "O" can have three different positions in a three-letter word (i.e. OO-, O-O, -OO). So that's 6*3 combinations that contain the double "O" and that we need to subtract from 336.

Then, we also need to account for 1 "O" overcount in our original result. This means that in some 3-word combinations the first O (O1) was used and in some the second O (O2) was used, but these are essentially the same words (MO1N and MO2N = MON). So, we need to eliminate this as well.

We choose either O1 or O2 to eliminate. Again, this one "O" is combined with 2 other non-O letters (first, we choose one letter out of 6 non-O letters, then one out of the remaining 5 letters); additionally, "O" can have three different positions in a word (i.e. O--, -O-, --O). So that's 6*5 combinations for one position multiplied by 3 positions: 30*3=90, meaning we need to subtract 90 additional combinations.

Finally:

336-18-90 = 228

Hope someone will find this helpful.

bobbym · 2017-02-04 00:31:19

Hi;

This will be a long reply and I still will only scratch the surface.

Depends on how you define simple. The reason for the generating function is because it eliminates the need to reason about the problem. Also, it can do much more difficult problems than this one without increasing the complexity of the solution. We turn a combinatorics problem into a computational one. Computers do not reason, they can not assist us when we reason as you did. But they can compute, which is one reason to favor the gf approach. Your computer can help you!

As for why I use them on even smaller ones is because of the teakettle principle. Why is it considered simpler to know dozens of tricks for each type of problem when the gf will do them all?

And I don't see how come it's mandatory, unless I'm missing something...

I stress it first because the gf approach is a general method for solving counting problems. The same method does them all, difficult or simple, it does not matter.

Because they can be done with a computer the answers are error free and quick. They fit nicely into a framework we call Experimental Math. Not only do we get the answer, we have proof and we know we did not make a mistake. Of course, I can use both methods and so can lots of other people, but my weapon of choice is the gf.

When I lived in Vegas I was a professional player for 20 years. I found that it was necessary on a daily basis to solve tough combinatorics and probability problems. Problems that even experienced mathematicians would sometimes get wrong. I found that a programmer who could hardly code beyond a beginners level could often solve such problems easily and quickly when math reasoning failed. It was the beginning of my education into EM.

So to sum it up, when you have to solve a quadratic which is better? Completing the square, factoring or the formula. Well, if you have been following along the answer is simple - the quadratic formula!

haidi · 2017-02-04 01:40:43

Okay, point taken.
I still prefer reasoning though, whenever possible.

I assume many members are just interested in getting the correct answers followed by a simple explanations they can actually understand. On the other side, advanced users are probably interested in learning more, and would benefit from the gf.

Just saying that not all of us on here are advanced users, or interested in the gf. It would be then reasonable to think about adding a small feature, like a question to be answered by new members for instance, so that one can say what exactly we're looking for when posting a question in "Help me !" section.

bobbym · 2017-02-04 02:05:51

Hi;

Do what works for you. If you are comfortable with logic then use it.

Just saying that not all of us on here are advanced users, or interested in the gf. It would be then reasonable to think about adding a small feature, like a question to be answered by new members for instance, so that one can say what exactly we're looking for when posting a question in "Help me !" section.

The choice of type of an answer is determined by the question. If someone just poses the problem I am going to go with what I like best. I know that he just wants to check an answer. If he asks for how then I must ask what method he was taught and wants to use. In this case the OP usually just wants to check an answer.

Regarding this point:

haidi wrote:

I assume many members are just interested in getting the correct answers followed by a simple explanations they can actually understand.

Gf's only require a person to understand how to multiply polynomials. This is taught early on in algebra. Actually, combinatoric reasoning is much more advanced. If a person or a computer can multiply a polynomial he can automatically solve lots of combinatorics. But students are not told that, they are made to believe that combinatorics is something difficult. All those binomials and factorials confuse people and I have seen this time and time again. Gf's are simple and easy to compute and since polynomial multiplication precedes the study of binomials, the gf approach should be taught first.

thickhead · 2017-02-04 03:30:49

haidi · 2017-02-04 04:14:48

bobbym wrote:

Do what works for you. If you are comfortable with logic then use it.

I am doing what works for me

I just think using logic makes it all so much more fun. I do agree, however, that the gf can be used to help us out at times.

haidi · 2017-02-04 04:17:39

thickhead wrote:

(3) Double o to be taken in a word...

If I understood correctly, your 228 combinations contain 18 combinations with double "O"?

Mathegocart · 2017-02-04 11:14:54

bobbym wrote:

Hi;
This will be a long reply and I still will only scratch the surface.
Depends on how you define simple. The reason for the generating function is because it eliminates the need to reason about the problem. Also, it can do much more difficult problems than this one without increasing the complexity of the solution. We turn a combinatorics problem into a computational one. Computers do not reason, they can not assist us when we reason as you did. But they can compute, which is one reason to favor the gf approach. Your computer can help you!
As for why I use them on even smaller ones is because of the teakettle principle. Why is it considered simpler to know dozens of tricks for each type of problem when the gf will do them all?
And I don't see how come it's mandatory, unless I'm missing something...
I stress it first because the gf approach is a general method for solving counting problems. The same method does them all, difficult or simple, it does not matter.
Because they can be done with a computer the answers are error free and quick. They fit nicely into a framework we call Experimental Math. Not only do we get the answer, we have proof and we know we did not make a mistake. Of course, I can use both methods and so can lots of other people, but my weapon of choice is the gf.
When I lived in Vegas I was a professional player for 20 years. I found that it was necessary on a daily basis to solve tough combinatorics and probability problems. Problems that even experienced mathematicians would sometimes get wrong. I found that a programmer who could hardly code beyond a beginners level could often solve such problems easily and quickly when math reasoning failed. It was the beginning of my education into EM.
So to sum it up, when you have to solve a quadratic which is better? Completing the square, factoring or the formula. Well, if you have been following along the answer is simple - the quadratic formula!

I have a preference for algebra instead of ugly combinatorics, gfs sound interesting to learn as a general approach.

bobbym · 2017-02-04 12:12:37

Hmmm, I taught my brother and EVW and now they are better than I am. But I do differ from some other EM guys, I suggest you learn both ways. I also suggest that you start to learn how to program or acquire a CAS, preferably Mathematica. I will teach you how to use it. We use tools in EM, I use M and Gebra, with those two we can solve many, many problems.

thickhead · 2017-02-04 16:17:24

Agnishom · 2017-02-04 17:27:09

bobbym wrote:

How did you get this exponential generating function?

bobbym · 2017-02-04 18:01:29

To answer that question one must always think in terms of EM, check this quote out which is in another thread where EM is used to solve a tougher problem than this one.

First, I programmed it. There is nothing better than a direct count. After that, to make the math types happy I began to look for a math solution to the problem, keep in mind I already had the answer in hand. Working backwards, called in Nevada, "back engineering" is a powerful technique. We work from the answer to a solution. It is much easier to do the math when you only have to fill in the blanks. Once we get the analytical answer and it agrees with the programming we are very, very sure we are right. We invoke probability to say the chance that two different methods came up with the same answer and are both wrong is millions to one against. Those are the kind of odds I like.

The method of back engineering is so powerful that even if you did not remember anything about an EGF you would still be able to solve this problem in at least 3 or 4 ways.

The whole thing about gf's is sequences and some diophantine equation theory. This type of problem shows up a lot and requires an EGF instead of an OGF.

{m},{o,o},{n},{d}{u},{s},{t}

We see there is one group of {o,o} we can represent them by

which says we can have no o's, 1 o's or 2 o's.

there are six groups of 1 letter. Each single letter can be represented by (1+x) which means we can have 0 or 1 of them. There are 6 letters like that.

We multiply and times the coefficient of x^3 by 3! and we are done.

Agnishom · 2017-02-05 03:07:46

I checked out Tucker, he explains it pretty nicely.

bobbym · 2017-02-05 05:01:58

You will go to the Dagobar system, there you will learn from Tucker, the jedi master who instructed me.

thickhead · 2017-02-11 21:58:50

haidi wrote:

I don't really understand why people use all that in post #2 for combinatorics problems as simple as this one.
And I don't see how come it's mandatory, unless I'm missing something...
There is A LOT easier way to solve this, without using any formulas at all.
Maybe someone will find it useful, so I'm going to explain in plain English
The word has 8 letters. If they all were different letters, our solution would be 8*7*6=336 (first choose one letter out of eight, then one out of the remaining seven, and one out of the remaining six letters).
But! We want only words that contain three DIFFERENT letters.
Letter "O" appears twice, so we need first to eliminate all the combinations that contain a double "O".
This double "O" can be combined with each of the 6 remaining letters; additionally, the double "O" can have three different positions in a three-letter word (i.e. OO-, O-O, -OO). So that's 6*3 combinations that contain the double "O" and that we need to subtract from 336.
Then, we also need to account for 1 "O" overcount in our original result. This means that in some 3-word combinations the first O (O1) was used and in some the second O (O2) was used, but these are essentially the same words (MO1N and MO2N = MON). So, we need to eliminate this as well.
We choose either O1 or O2 to eliminate. Again, this one "O" is combined with 2 other non-O letters (first, we choose one letter out of 6 non-O letters, then one out of the remaining 5 letters); additionally, "O" can have three different positions in a word (i.e. O--, -O-, --O). So that's 6*5 combinations for one position multiplied by 3 positions: 30*3=90, meaning we need to subtract 90 additional combinations.
Finally:
336-18-90 = 228

Hope someone will find this helpful.

Math Is Fun Forum

#1 2017-02-01 15:09:17

Combinatorics problem

#2 2017-02-01 17:02:25

Re: Combinatorics problem

#3 2017-02-02 03:41:01

Re: Combinatorics problem

#4 2017-02-02 04:33:08

Re: Combinatorics problem

#5 2017-02-02 09:27:46

Re: Combinatorics problem

#6 2017-02-02 09:28:26

Re: Combinatorics problem

#7 2017-02-02 09:30:42

Re: Combinatorics problem

#8 2017-02-02 09:40:15

Re: Combinatorics problem

#9 2017-02-04 00:18:08

Re: Combinatorics problem

#10 2017-02-04 00:31:19

Re: Combinatorics problem

#11 2017-02-04 01:40:43

Re: Combinatorics problem

#12 2017-02-04 02:05:51

Re: Combinatorics problem

#13 2017-02-04 03:30:49

Re: Combinatorics problem

#14 2017-02-04 04:14:48

Re: Combinatorics problem

#15 2017-02-04 04:17:39

Re: Combinatorics problem

#16 2017-02-04 11:14:54

Re: Combinatorics problem

#17 2017-02-04 12:12:37

Re: Combinatorics problem

#18 2017-02-04 16:17:24

Re: Combinatorics problem

#19 2017-02-04 17:27:09

Re: Combinatorics problem

#20 2017-02-04 18:01:29

Re: Combinatorics problem

#21 2017-02-05 03:07:46

Re: Combinatorics problem

#22 2017-02-05 05:01:58

Re: Combinatorics problem

#23 2017-02-11 21:58:50

Re: Combinatorics problem

Board footer