Math Is Fun Forum

chetah

Member

Registered: 2008-02-15

Posts: 32

Discrete Math

How many arrangements of the letters MISSISSIPPI  have no consecutive S's?

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Discrete Math

MPPIIII = 7777777 
SSSS = 4444

47474747777
47474774777
47474777477
47474777747
47474777774

47477474777
47477477477
47477477747
47477477774

47477747477
47477747747
47477747774

47477774747
47477774774

47477777474

47747474777
47747477477
47747477747
47747477774

47747747477
47747747747 (nice one!)
47747747774

47747774747
47747774774

47747777474

47774747477
47774747747
47774747774 (nice!)

47774774747 (cool)
47774774774

47774777474

47777474747
47777474774

47777477474 (wik)

47777747474

74747474777
74747477477
74747477747
74747477774

74747747477
74747747747
74747747774

74747774747 (slick)
74747774774

74747777474

74774747477
74774747747
74774747774

74774774747
74774774774

74774777474 (nice 123)

74777474747
74777474774

74777477474 (yeah yeah yeah 321)

74777747474

77474747477 (sure is getting boring)
77474747747
77474747774

77474774747
77474774774

77474777474 (213, reminds me of 231 which is some product)

77477474747
77477474774

77477477474 (actually, a nice paired one)

77477747474

77747474747
77747474774

77747477474

77747747474

77774747474 (Holy Smokes, We're Done!)

(There might be a more interesting order to do this; maybe someone else will come up with one)

Last edited by John E. Franklin (2008-03-25 13:09:19)

---

igloo myrtilles fourmis

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Discrete Math

Now the MPPIIII can
be mixed up where all
the 7's are.
And however many
MPPIIII mixes you get,
you can multiply that by
the 70  47474747777 mixes
up above.

MPPIIII
MPIPIII
MPIIPII
MPIIIPI
MPIIIIP

MIPPIII
MIPIPII
MIPIIPI
MIPIIIP

MIIPPII (someday, someone might generalize a method to proceed through)
MIIPIPI
MIIPIIP

MIIIPPI
MIIIPIP

MIIIIPP

Now the M can move through the
above 15 IIIIPP mixes.

There are 6 locations you can
move the M to the right, so
15 times (6+1) times 70 is the final answer
for Mississippi with the S's not
touching each other.

15 by 7 = 15 times 7 = 105
and
105 by 70 = 105 times 70 = 7350 Wow!

So answer is 7350 ways to mix up
mississippi with no touching S's.
But if I missed some, then the
answer is higher.

Last edited by John E. Franklin (2008-03-25 13:51:50)

---

igloo myrtilles fourmis

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: Discrete Math

For the number of ways the S's can be together:

And the total number of combinations:

Now subtract to get the complement - the number of permutations where the S's are not together:

That seems to be wrong... but that's the best I can do

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Discrete Math

John, a bunch of these combinations/permutations questions have come up and you always try to write them all out by hand.  I don't mean to criticize and if you enjoy doing them, then by all means go ahead.  Certainly it verifies if an answer is correct.  But the beauty behind mathematics (specifically, combinatorics) is that you don't have to do all that work to get an answer.

Personally, I find writing them all out by hand to be tedious and boring, but to each his own.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: Discrete Math

I agree about finding beauty and form. 
Instead of standing on previous shoulders, I am building my own.
Eventually, I intend to generalize these long lists as
I find algorithms that work, and then I may compare
my methods with known methods.

Last edited by John E. Franklin (2008-03-25 15:41:37)

---

igloo myrtilles fourmis

Identity

Member

Registered: 2007-04-18

Posts: 934

Re: Discrete Math

Yes, you can try writing out a few to get the feel of how to tackle the problem, and I think that's a smart thing to do, but in the end I believe it should be done using combinatorical methods.

And btw, what do you think of my answer? Is it WAY TO BIG, or just right?