Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

 Messages: [ Previous | Next ]
 Butch Malahide Posts: 894 Registered: 6/29/05
Re: Permutation/Combination Problem
Posted: Feb 7, 2013 1:28 AM

On Feb 6, 6:29 pm, 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.

The in-and-out principle leads directly to the following formula:

sum, from k = 0 to floor(N/3), of (-1)^k * C(N-2k,k) * 3^(N-3k).

This is sequence A076264, "Number of ternary (0,1,2) sequences without
a consecutive '012'", at oeis.org, the on-line encyclopedia of integer
sequences:

http://oeis.org/search?q=1%2C3%2C9%2C26%2C75%2C216%2C622&sort=&language=english&go=Search

Date Subject Author
2/6/13 gnasher729
2/7/13 Butch Malahide
2/7/13 bacle