Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Permutation/Combination Problem
Replies: 3   Last Post: Feb 7, 2013 2:08 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
gnasher729

Posts: 418
Registered: 10/7/06
Re: Permutation/Combination Problem
Posted: Feb 6, 2013 9:44 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Feb 7, 12:29 am, willmann...@gmail.com wrote:
> Sorry for the vulgarity:  I have a 3 letter keyboard with the letters E, S, & X.
> I need a formula that can tell me how many words of length N that I can make without the word SEX contained in it. The letters can be repeated so if it is of length 4 then SSXX would be ok or SSSS etc.  So my initial approach was to do (3^N) to find the total number of permutations(I think it is a permutation please correct me if it is a combinations) I can come up with and then subtract all those permutations that contain an instance or instances of the words SEX.  Any ideas on a mathematical formula for this?
>
> For anything of length 1 the answer is 3; for length 2 it is 9; length 3,4,and 5 this formula works (3^N)-(N-2)*(3^(N-3)) but anything higher than that does not and I think it has something to do with if it is of length 6 or 7 or 8 the word SEX can appear twice and if it is between length 9 and 11 it can appear 3 times and so on.  Any help is much appreciated.  I am looking for a formula that always works.


I'd start like this:

f (N) = number of sequences not containing S, E, X.
g (N) = number of those sequences ending in S
h (N) = number of those sequences ending in S, E.

g (N + 1) = f (N)
h (N + 1) = g (N)
f (N + 1) = 3 f (N) - h (N)

There is a reasonably simple method to solve that kind of recursions.
The vector f, g, h (N + 1) can be found my multiplying f, g, h (N) by
some constant matrix, so find the eighenvalues of the matrix and
things look good.





Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.