5
$\begingroup$

Find the number of permutations of the set $\left\{ 1,2,3,4,5,6,7\right\} $ not containing four consecutive elements of ascending order.

My try:
All permutations in cycles are $6!$.
Let's deal with cases that do not meet the requirements of the task:

  • When four growing elements are not at the beginning:
    - choice of beginning: ${3 \choose 1}$
    - choice of four numbers ${6 \choose 4}$
    So: $${3 \choose 1}\cdot {6 \choose 4}\cdot 2!=90$$
  • When four growing elements are at the beginning:
    $${6 \choose 3}\cdot 3!=120$$
    Then we must count cases common to the previous two considerations: $${6 \choose 4}\cdot2!=30$$That is why my answer is: $$6!-90-120+30=540$$ However I wrote a Python program to check the number of solutions and he says it's $342$ so I have a mistake.

    Can you help me and tell me what I'm doing wrong?
$\endgroup$
  • 3
    $\begingroup$ You haven't mentioned that the permutation is cyclic. It looks as if it isn't from the question. $\endgroup$ – Parcly Taxel Aug 16 at 11:01
  • 1
    $\begingroup$ @ParclyTaxel I'm just not sure how to receive cyclicality here because there is no mention of it in the content $\endgroup$ – MP3129 Aug 16 at 11:10
  • 1
    $\begingroup$ not containing "exactly four" or not containing "four or more" consecutive elements? $\endgroup$ – samerivertwice Aug 16 at 13:49
  • 2
    $\begingroup$ @samerivertwice: If a permutation has $5$ consecutive terms in ascending order, then it certainly has $4$ consecutive terms in ascending order. Hence if a permutation does not contain $4$ consecutive terms in ascending order, then it does not contain $5$ consecutive terms in ascending order. $\endgroup$ – quasi Aug 16 at 13:55
  • $\begingroup$ @quasi agreed, but you make the assumption (which I have next to no doubt is correct) that this asker has a precision which we know some askers not to have. $\endgroup$ – samerivertwice Aug 16 at 14:00
6
$\begingroup$

Let $A$ be the set of permutations of the sequence $1,2,3,4,5,6,7$ which have $4$ consecutive terms in ascending order.

  • The number of elements of $A$ whose first $4$ terms are ascending is $$\binom{7}{4}{\,\cdot\,} 3!=210$$ Explanation:

    • There are ${\large{\binom{7}{4}}}$ choices for the first $4$ terms.$\\[2pt]$
    • There are $3!$ ways to order the $3$ remaining terms.
    $\\[2pt]$
  • The number of elements of $A$ whose initial block of $4$ consecutive ascending terms are not the first $4$ terms, and which start with the value $1$ is $$\binom{6}{3}{\,\cdot\,} 3{\,\cdot\,} 3!=360$$ Explanation:

    • There are ${\large{\binom{6}{3}}}$ choices for the $3$ terms which follow the value $1$.$\\[2pt]$
    • There are $3$ positions where the value $1$ can be placed.$\\[2pt]$
    • There are $3!$ ways to order the $3$ remaining terms.
    $\\[4pt]$
  • The number of elements of $A$ whose initial block of $4$ consecutive ascending terms are not the first $4$ terms, and which start with the value $2$ is $$\binom{5}{1}\binom{4}{3}{\,\cdot\,} 3{\,\cdot\,} 2!=120$$ Explanation:

    • There are ${\large{\binom{5}{1}}}$ choices for the term immediately before the value $2$.$\\[2pt]$
    • There are ${\large{\binom{4}{3}}}$ choices for the $3$ terms which follow the value $2$.$\\[2pt]$
    • There are $3$ positions where the value $2$ can be placed.$\\[2pt]$
    • There are $2!$ ways to order the $2$ remaining terms.
    $\\[4pt]$
  • The number of elements of $A$ whose initial block of $4$ consecutive ascending terms are not the first $4$ terms, and which start with the value $3$ is $$\binom{4}{1}\binom{3}{3}{\,\cdot\,} 3{\,\cdot\,} 2!=24$$ Explanation:

    • There are ${\large{\binom{4}{1}}}$ choices for the term immediately before the value $3$.$\\[2pt]$
    • There are ${\large{\binom{3}{3}}}$ choices for the $3$ terms which follow the value $3$.$\\[2pt]$
    • There are $3$ positions where the value $3$ can be placed.$\\[2pt]$
    • There are $2!$ ways to order the $2$ remaining terms.
    $\\[2pt]$

hence we get $$|A|=210+360+120+24=714$$ so the number of permutations of the sequence $1,2,3,4,5,6,7$ which do not have $4$ consecutive terms in ascending order is $$7!-|A|=7!-714=4326$$

$\endgroup$
  • $\begingroup$ Downvoting because this doesn't answer the OP's question, which was "Can you help me and tell me what I'm doing wrong?" This presents an entirely new approach and makes no reference to the OP's attempt. $\endgroup$ – BallBoy Aug 16 at 14:05
  • $\begingroup$ @Y. Forman: You're entitled to your opinion (and your downvote), but$\;(1)\,{:}\;$I'm doing a case analysis along the same lines as the OP's attempt, but using cases that have the chance of achieving successful counts, and$\;(2)\,{:}\;$In my opinion, trying to take apart the OP's hard to comprehend argument would be less helpful than showing a more understandable and potentially reusable approach. $\endgroup$ – quasi Aug 16 at 14:16
  • $\begingroup$ Yeah, I agree the OP's argument is hard to comprehend, and I would encourage keeping your answer and just adding a sentence or two at the beginning explaining what you just explained in that comment. $\endgroup$ – BallBoy Aug 16 at 14:23
  • $\begingroup$ I think it's better to leave it as is. $\endgroup$ – quasi Aug 16 at 14:24
  • 1
    $\begingroup$ Feel free to downvote my perhaps quixotic attempt to muddle through the OP's work. $\endgroup$ – BallBoy Aug 16 at 14:38
3
$\begingroup$

I'm going to relate to the question how I think you understood it, even though I think quasi's read is much more straightforward.

(If I'm reading your answer correctly, you're considering cyclic permutations and fixing "the beginning" at $1$.)

You haven't accounted for all the overcounting. Any case with $5$ ascending elements starting not at the beginning has been counted twice in the first step. By your method, there are $2\binom651!=12$ such cases, so we must add $12$.

Then there are the $5$ cases in which exactly $6$ elements appear in order (starting from $1$, with anything other than a $7$ omitted) and the $1$ case in which all appear in order. The former cases were subtracted $3$ times each, then added $2$ times each, so no further correction is needed. The latter case was subtracted $4$ times then added $3$ times, so again no correction is needed.

So the answer should be $552$. I don't know how you got $342$ -- perhaps you can post the Python code?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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