A,B,C,D 카드 네 장을 한 번씩 모두 줄 세워요. 왼쪽부터 글자를 비교하고 A<B<C<D로 정렬한 가상 목록에서 첫 배열은 ABCD입니다. 배열은4!=24개예요. 열일곱 번째 배열을 찾으려면24개를 모두 적어야 할까요?
첫 글자를 하나 정하면 나머지 세 글자의 순서는3!=6개예요. A로 시작하는 배열이1~6번째, B는7~12번째, C는13~18번째, D는19~24번째입니다.17번째는 C로 시작하며 C묶음 안에서17−12=5번째예요.
이제 남은 글자는 A,B,D입니다. 둘째 글자를 정하면 나머지 두 글자를 배열하는 방법이2!=2개예요. C묶음에서 CA는1~2번째, CB는3~4번째, CD는5~6번째이므로 원하는 배열은 CD로 시작해요. 남은 A,B의 첫 순서는 AB이므로 답은 CDAB입니다.
이 식의 마지막1은 CD묶음 안에서의 첫 번째라는 뜻이에요. 순번을1부터 세었으므로 각 단계에서 앞서 지나간 묶음의 개수만 빼야 해요. CDAB 바로 앞은 CBDA로16번째, 뒤는 CDBA로18번째이니 순번도 검산됩니다.
전체 목록의 크기를 아는 것과 필요한 줄을 찾는 것은 달라요. 같은 첫 글자를 갖는 묶음의 크기를 계산하면 불필요한 나열을 줄일 수 있어요. 카드가 모두 서로 다르고, 왼쪽부터 비교하는 문자순이라는 조건이 있어야 이 묶음 계산을 그대로 적용할 수 있어요.
참고한 수학 개념: Mathigon · Combinatorics.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.