Challenging permutations on words?

Those are 2 difficult problems. You probably should have posted them separately. I just worked on the first part.

I created a program in Excel to generate permutations and confirmed that 2016 is correct.

I expressed the numbers from 0 to 4^11 - 1 in base 4, then checked the results to make sure that there were 4 0's, 4 1's, 2 2's, and 1 3, and that no number was the same as the one before it.

It's easier to work with numbers than letters, so I'm working with

0 0 0 0 1 1 1 1 2 2 3 instead of

I I I I S S S S P P M

I don't have an analytic way of doing this. I think doing so has to involve a lot of different cases, and it gets very tedious.

Here's a fact that might simplify things. There are only 3 sequences that do NOT have "01" someplace in it, and they are

10210210310

10210310210

10310210210

Similarly, there are only 3 without "10":

01201201301

01201301201

01301201201

It's pretty easy to prove that those are the only 3 of each.

Now you can try to analyze cases with a 01 AND a 10, or with a "010."

There are 210 without a "010."

There are 210 without a "101"

There are 48 with neither of those.

All the rest have a 01 and a 10.

Depending on how you look at the cases, things like that might be helpful, but I haven't tried to use those facts to find an analytic solution.

I would love to know how you manage to get so much out of Excel.

I manged to piece together a method from other sources, but it is quite involved all the same:

For MPPIIIISSSS if we first make letters distinct:

M1 P1 P2 I1 I2 I3 I4 S1 S2 S3 S4

then, for each set of letters of the same type (types are M, P, I, S) count the ways of creating a particular number of blocks of letters, where the order within the blocks matters but not the blocks themselves.

eg.

for M1

1 block

{M1} 1 way

for P1 P2

2 blocks

{P1}{P2} 1 way

1 block

{P1 P2}

{P2 P1} 2 ways

for I1 I2 I3 I4

4 blocks

{I1}{I2}{I3}{I4} 1 way

3 blocks

{I1 I2}{I3}{I4} ■ {I1 I3}{I2}{I4} ■ {I1 I4}{I3}{I2}

{I2 I1}{I3}{I4} ■ {I3 I1}{I2}{I4} ■ {I4 I1}{I3}{I4} 6 ways

2 blocks

{I1 I2}{I3 I4} ■ {I1 I3}{I2 I4} ■ {I1 I4}{I3 I2}

{I2 I1}{I3 I4} ■ {I3 I1}{I2 I4} ■ {I4 I1}{I3 I2}

{I1 I2}{I4 I3} ■ {I1 I3}{I4 I2} ■ {I1 I4}{I2 I3}

{I2 I1}{I4 I3} ■ {I3 I1}{I4 I2} ■ {I4 I1}{I2 I3}

{I1 I2 I3}{I4} ■ {I1 I3 I2}{I4} ■ {I2 I1 I3}{I4} ■ {I2 I3 I1}{I4} ■ {I3 I1 I2}{I4} ■ {I3 I2 I1}{I4}

{I1 I2 I4}{I3} ■ {I1 I4 I2}{I3} ■ {I2 I1 I4}{I3} ■ {I2 I4 I1}{I3} ■ {I4 I1 I2}{I3} ■ {I4 I2 I1}{I3}

{I1 I4 I3}{I2} ■ {I1 I3 I4}{I2} ■ {I4 I1 I3}{I2} ■ {I4 I3 I1}{I2} ■ {I3 I1 I4}{I2} ■ {I3 I4 I1}{I2}

{I4 I2 I3}{I1} ■ {I4 I3 I2}{I1} ■ {I2 I4 I3}{I1} ■ {I2 I3 I4}{I1} ■ {I3 I4 I2}{I1} ■ {I3 I2 I4}{I1} 36 ways

1 block

{I1 I2 I3 I4} 4! = 24 ways

similarly for S1 S2 S3 S4:

4 blocks: 1 way

3 blocks: 6 ways

2 blocks: 36 ways

1 block: 24 ways

We can generalise the above ways of splitting r letters into n blocks by firstly counting ways of placing r indistinguishable letters into n bins in C(r-1,n-1) then permuting the r letters and then dividing out the n! arrangements of the blocks to give: C(r-1,n-1)*r!/n!

This can be tested for each case. (eg. For 2 blocks of 4 letters C(3,1)*4!/2! = 3*3*4 = 36)

Form a polynomial for *each type of letter* with coefficients of x^n (where n= number of blocks) given by the ways above:

M: 1x^1

P: 1x^2 - 2x^1

I: 1x^4 - 6x^3 + 36x^2 - 24x^1

S: 1x^4 - 6x^3 + 36x^2 - 24x^1

Multiplying the polynomials for each letter we have:

x(x^2 - 2x)(x^4 - 6x^3 + 36x^2 - 24x)^2

notice that the magnitude of the coefficient (Ak) of the general term x^k in the expansion of the above is the number of ways of dividing the distinct letters M1 P1 P2 I1 I2 I3 I4 S1 S2 S3 S4 into k blocks (where blocks each contain letters of a single type).

The expansion is of the form:

A11x^11 - A10x^10 + A9x^9 - .. - A4x^4

If we replace x^11 with 11!, x^10 with 10! etc then the above becomes:

A11*11! - A10*10! + A9*9! - .. - A4*4!

A11*11! is the total number of permutations of the 11 distinct letters (blocks of size 1), A10*10! is the permutations of block of size 2 or less, A9*9! is the number of permutations of blocks size 3 or less etc. By inclusion-exclusion the result:

A11*11! - A10*10! + A9*9! - .. - A4*4!

counts the permutations where each letter is not adjacent to it's own type (eg. I1 not next to I2, I3 or I4 etc). If we divide the last result by permutations of each type 1!*2!*4!^2 we get the required permutations of *indistinguishable* letters of each type.

A succinct way of writing this uses the fact that:

∫[0,∞] x^k*e^(-x) dx = k!

For natural k.

So our answer is:

(∫[0,∞] x*(x^2 - 2x)*(x^4 - 6x^3 + 36x^2 - 24x)^2*e^(-x) dx)/(1!*2!*4!^2) = 2016

I thought this was pretty cool. The polynomials are a type of Laguerre Polynomial although for this problem it doesn't really help to know that.