## 123456

If all 720 permutations of the digits 1 through 6 are arranged in numerical order from least to greatest, what is the 409th permutation? Note that 123456 is the first permutation, 123465 is the second, and so on.
Source: mathcontest.olemiss.edu 10/8/2007

SOLUTION
Since $720=6\times 120$, there are 6 groups of 120 permutations in each group. Each group is further divided into 5 subgroups of 24 permutations in each subgroup. We list in increasing order the contents of the 6 groups below.

Group 1
$123456\rightarrow 126543$: 1 through 24. The first permutation through the twenty-fourth permutation with 123456 being the first permutation and 126543 the twenty-fourth permutation.
$132456\rightarrow 136542$: 25 through 48
$142356\rightarrow 146532$: 49 through 72
$152346\rightarrow 156432$: 73 through 96
$162345\rightarrow 165432$: 97 through 120

Group 2
$213456\rightarrow 216543$: 121 through 144
$231456\rightarrow 236541$: 145 through 168
$241356\rightarrow 246531$: 169 through 192
$251346\rightarrow 256431$: 193 through 216
$261345\rightarrow 265431$: 217 through 240

Group 3
$312456\rightarrow 316542$: 241 through 264
$321456\rightarrow 326541$: 265 through 288
$341256\rightarrow 346521$: 289 through 312
$351246\rightarrow 356421$: 313 through 336
$361245\rightarrow 365421$: 337 through 360

Group 4
$412356\rightarrow 416532$: 361 through 384
$421356\rightarrow 426531$: 385 through 408
$431256\rightarrow 436521$: 409 through 432
$451236\rightarrow 456321$: 433 through 456
$461235\rightarrow 465321$: 457 through 480

For completeness we will list Groups 5 and 6 even though we have found the answer: the 409th permutation is 431256.

Group 5
$512346\rightarrow 516432$: 481 through 504
$521346\rightarrow 526431$: 505 through 528
$531246\rightarrow 536421$: 529 through 552
$541236\rightarrow 546321$: 553 through 576
$561234\rightarrow 564321$: 577 through 600

Group 6
$612345\rightarrow 615432$: 601 through 624
$621345\rightarrow 625431$
: 623 through 648
$631245\rightarrow 635421$: 649 through 672
$641235\rightarrow 645321$: 673 through 696
$651234\rightarrow 654321$: 697 through 720