-3
$\begingroup$

Find the total number of permutations of the word STAKEXCHANGEPUZZLING such that the letters STAK always stay together.

Rules:

  • No 3 adjacent consonants, no 2 adjacent vowels.
  • For every odd pair of adjacent consonants - first letter must be alphabetically smaller than the second.
  • For every even pair of adjacent consonants - the opposite (first letter must be alphabetically bigger than the second).

What is odd and even pair - let's say we have hnanh - hn is the first ( odd ) consonants pair, nh is the second ( even ) pair.

$\endgroup$

closed as off-topic by Glorfindel, w l, Omega Krypton, Feeds, QuantumTwinkie Apr 11 at 16:37

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is off-topic as it appears to be a mathematics problem, as opposed to a mathematical puzzle. For more info, see "Are math-textbook-style problems on topic?" on meta." – Glorfindel, w l, Omega Krypton, Feeds, QuantumTwinkie
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Added in end of question. $\endgroup$ – Kradec na kysmet Apr 10 at 22:32
  • $\begingroup$ Thank you for that. So "even" refers to the 2nd, 4th etc pair, not to the index within the word? $\endgroup$ – Weather Vane Apr 10 at 22:32
  • 1
    $\begingroup$ I can't find any words at all - even stack is unacceptable becaus both sets of consonant pairs are in alphabetical order. $\endgroup$ – Weather Vane Apr 10 at 22:39
  • 2
    $\begingroup$ Unless you have a definitive list of every rearrangement of letters that fits your ruleset, comprised of "words" taken from some definitive authoritative word list, and you intend to give a checkmark to the first person who reproduces your definitive "Find all the words" solution... I think you may need to reformulate what you're asking. Usually these types of questions make poor puzzles (there's nothing to solve, just a search for pattern matches to arbitrary rules), and nothing that makes one answer more "right" than another, so any answer is equally valid. Maybe a way to "keep score"? $\endgroup$ – Rubio Apr 10 at 22:40
  • 1
    $\begingroup$ It's solved by programming and a lexicon. By "words" do you mean dictionary words or some other definition? $\endgroup$ – Weather Vane Apr 10 at 22:43
3
$\begingroup$

So far:

The first attempt to solve it by brute force for the given conditions is still running.
It will quite likely still be running next week...
So thinking through a strategic solution:

There are 6 vowels and 14 consonants in STAKEXCHANGEPUZZLING.
There cannot be any double vowels, or triple consonants.
So if v=vowel and c=consonant, the arrangement must be
ccvccvccvccvccvccvcc

The letters STAK must be adjacent.
The 1st, 3rd, 5th and 7th consonant pair must be in alphabetical sequence, so one of
STAKcvccvccvccvccvcc
ccvccvSTAKcvccvccvcc
ccvccvccvccvSTAKcvcc

The 2nd, 4th and 6th consonant pair must be in reverse alphabetical sequence.
So K must be followed by C, G or H, now one of
STAKCvccvccvccvccvcc
STAKGvccvccvccvccvcc
STAKHvccvccvccvccvcc
ccvccvSTAKCvccvccvcc
ccvccvSTAKGvccvccvcc
ccvccvSTAKHvccvccvcc
ccvccvccvccvSTAKCvcc
ccvccvccvccvSTAKGvcc
ccvccvccvccvSTAKHvcc

The number of ways to arrange the remaining 5 vowels, with 1 duplicate, is
$ \frac{5!}{2!} = 60$
So the next task is to permute consonant pairs leaving out the vowels,
and them multiply the result by $60$.

Edit (continued):

There are 3 sets of 10 consonants to permute in pairs with the given restrictions.
There are some duplicated consonants, and by brute force I found $74340$ unique perms.
Each of the STAKC, STAKG and STAKH can be in $3$ positions.

So my final answer is
$ 74340 \times 3 \times 60 = $

13381200 solutions.

Edit 2: thanks to @PiIsNot3 observation about double letters.

The revised number of unique consonant perms is $42660$.
So my final answer is
$ 42660\times 3 \times 60 = $

7678800 solutions.

$\endgroup$
  • $\begingroup$ I don't think brute force will do it this year to be honest :P $\endgroup$ – Kradec na kysmet Apr 11 at 8:17
  • $\begingroup$ I gave up on that, but for finding the number of consonant pair perms took a fraction of a second. $\endgroup$ – Weather Vane Apr 11 at 9:51
1
$\begingroup$

I’ve made a (possible) discovery about the arrangements of the consonants:

Say we distributed the consonants randomly according to one of Weather Vane’s patterns. We’d get something like:
$$ \text{STAKG_CG_HL_NZ_NP_XZ} $$ Call each group of 2 consonants (excluding the STAKG substring that must exist together) a cluster. There are $ 2^5 $ distributions of the consonants such that each cluster contains the same consonants in the same locations. For example, in the example above, an equivalent distribution of consonants with the same clusters would be:
$$ \text{STAKG_GC_HL_ZN_PN_XZ} $$ However, only one of these distributions satisfies the constraints of the problem statement, namely this one:
$$ \text{STAKG_CG_LH_NZ_PN_XZ} $$ Thus, to count the total number of valid consonant distributions, we only need to count the number of valid cluster distributions, then divide by $ 2^5. $

Note that we can’t have double consonants such as NN or ZZ, since then the cluster rules would not be satisfied. So that means we just have to count the total number of consonant distributions at all, then subtract by the number of distributions where at least one cluster has repeated consonants in them. This also means that we have to split by whether we go with STAKG or not, since that removes a consonant that can potentially form a pair.

I hope the explanation was clear enough - if not, let me know what I can do to make it clearer.

$\endgroup$
  • $\begingroup$ I was edit this post with my final answer, but I realized that I forgot about possible repeated clusters e.g. NZ and GN. Drat! Back to the drawing board... $\endgroup$ – PiIsNot3 Apr 11 at 3:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.