3
$\begingroup$

In how many ways can one write the numbers ${1, 2, 3, 4, 5, 6}$ in a row so that given any number in the row, all of its divisors (not including itself) appear to its left?

I know $1$ has to be the first element, so we only concern ourselves with ordering the numbers $2$ to $6$. $5$ can be anywhere except the first position. We order ${2, 3, 4, 6}$ then multiply that by five (for the five positions we can insert $5$ into afterwards).

Is this correct? And can anyone help me solve the rest? I'm not quite sure how to proceed.

$\endgroup$
3
$\begingroup$

Yes, you're on right track.

We have two base cases ${2,4,6}$ and ${2,6,4}$ :

  • ${2,4,6}$

Here $3$ can go in $3$ places. $5$ follows in $5$ spaces.

  • ${2,6,4}$

Here $3$ can go in $2$ places. $5$ follows in $5$ spaces.

Total ways $= \boxed{25}$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Let's place $1, 2, 6$ first which can be done in just one way.

Now, $4$ can be placed in $2$ ways -

i) either in between $2, 6$ - then $3$ can be placed in $3$ ways (before $6$).

ii) after $6$ - then $3$ can be placed in $2$ ways (before $6$).

$5$ can always be placed in $5$ ways (any place after $1$).

So total number of ways = $(3 + 2) \times 5 = 25$.

| cite | improve this answer | |
$\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.