계승 진법

주의: 혼자 쓴 거라서 이해하기 애매모호한 부분이 존재합니다. 그 자리 짚어서 알려주시면 정말 감사하겠습니다.

 

그런 문제 있잖아요?

사전 순으로 배열하라고 주는 NGD 문제 말이에요.

a, b, c, d, e 주고서는

bdaec가 몇 번째로 오나, 하는 거요...

 

그때마다 저는 꼼수를 써서 풀었습니다.

b가 왔으니 a... 에 대해서는 카운팅을 완료했다고 생각할 수 있으므로 4! × 1

d가 왔으니 a..., c... 에 대해서는  카운팅을 완료했다고 생각할 수 있으므로 3! × 2

a가 왔으니 아직이라 2! × 0

e가 왔으니  c...에 대해서는 카운팅을 완료했다고 생각할 수 있으므로 1! × 1

 

 

그리고서 0000부터 세어 나가는 것을 감안하여 +1

∴24+12+0+1+1 = 38

이렇게 문제를 풀어왔었습니다.

 

그런데..?!

역시나 저만 그런 생각을 한 것이 아녔습니다.

이게 수학의 단점인 것 같습니다. 기발한 생각을 해내면 이미 다 있는 것들이라 허망한 거요...

칸토어 아저씨가 이미 다 정리해 놓았네요...

 

어쨌든, '계승 진법'으로 이런 것들을 나타낼 수 있는데요!

 

정의

\(a\in \mathbf{N}\)인 \(a\)를 계승 진법으로

\(a = \overline{a_na_{n-1}\cdots a_2a_1}_{(!)}\)와 같이 표현할 수 있습니다.

단, \(a_i\in [0,i)\)라는 조건이 있고, 특히 *\(a_1\)는 항상 0이라 정의합니다. 

 

촉이 좋으신 분들은 여기서 이제 설명할 내용을 눈치채실 수도 있습니다.

계승 진법의 '변환' 과정을 설명할 것입니다.

 

진법이 있을 때 당연하게 따라오는 것이고, 제가 맨 위에서 시전했던 내용이지요.

원리는 역시 이진법과 다를 바가 없습니다.

\(a_1 = n \mod 1, n'=\lfloor n/1 \rfloor\)

\(a_2 =n'\mod 2, n''=\lfloor n'/2\rfloor\)

\(a_3=n''\mod 3,n'''=\lfloor n''/3\rfloor\)

.

.

.

을 반복하시면 되겠습니다.

 

bdaec 순열을 생각합시다.

맨 위에서 구했던 것을 생각하면 \(\overline{12010}_{(!)}\)으로 대응될 것이란 사실을 알 수 있습니다.

그러면 bdaec를 우선 \((a,b,c,d,e)\rightarrow(0,1,2,3,4)\)로 매칭시킵니다.

그러면 순열 13042라고 불러줄 수 있습니다.

이제 각 자리보다 아래자리에서 자신보다 작은 숫자의 개수로 자릿수를 설정해봅시다.

\(1\rightarrow 1\)

\(3\rightarrow 2\)

\(0\rightarrow 0\)

\(4\rightarrow 1\)

\(2\rightarrow 0\)

가 됩니다. 그러면 정확히 \(\overline{12010}_{(!)}\)가 나온다는 것을 알 수 있습니다.

이를 십진법으로 전개해주면, \(0\cdot 0!+1\cdot 1!+0\cdot 2!+2\cdot 3!+1\cdot 4!=0+1+0+12+24=37\)이 됩니다.

이 상태에서 기수를 0번이 아닌 1번부터 하기에 1을 더해주면 됩니다.

 

와 웅장이 가슴해진다... 이렇게 적고서 위키피디아에 순열과의 관계를 읽어봤는데(전에 추상대수에 대해 다룬 글 몇개를 읽어보면 대략 뭔 소린지 감 잡는데 무리가 없다), 완전히 똑같은 얘기를 하고 있어서 놀랐다.

게다가 +1 더하는 부분에 적당한 의미를 찾지 못해 헤매이고 있었는데, "이 알고리즘에서, ‘집합의 〜번째 원소’란 0번째부터 센다."라고 위키피디아도 걍 1 더하면 되는 듯 이 모양으로 답한 것까지 똑같았다. ㅋㅋㅋㅋ

암튼...

www.numdam.org/article/BSMF_1888__16__176_0.pdf 여기를 참고하면 샤를앙주 레장의 구체적인 연구를 확인할 수 있다. 다만, 불어를 하지 못하는 사람은 읽을 수 없다는 점이 함정이다.