최근 수정 시각 : 2024-05-11 11:21:23

읽고 말하기 수열


이산수학
Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" 		이론
<colbgcolor=#3CC> 기본 대상 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제
기타 P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설
관련 문서 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 }}}}}}}}}


1. 개요2. 상세
2.1. 파생형
3. 성질4. 기타

1. 개요

look and say sequence · 읽고(보고) 말하기 數 列, 개미 數 列

읽고 말하는 대로 다음 항을 도출하는 수열이다. 보통은 초항이 1이지만, 다른 수를 초항으로 설정하기도 한다. 보고 말하기 수열이라고도 하며, 프랑스의 유명 소설가 베르나르 베르베르의 소설 < 개미>에 등장한다고 하여 개미 수열이라고도 한다. 이 수열은 일상적 언어를 사용한 구술적인 방식으로 정의되기에, 엄밀한 수학적 표현으로 정의되는 여타 수열과 달리 일반항이나 점화식이 아직까지 알려지지 않았다.

콘웨이의 생명 게임으로 유명한 존 호튼 콘웨이가 만들었다.

2. 상세

읽고 말하기 수열을 [math(L_n)]([math(n)]은 자연수)[1]이라 칭하고 [math(L_1=1)]이라 한다면, [math(L_{n+1})]의 값은 [math(L_n)]의 값의 각 자릿값을 따지게 된다. 그리고 '[math(a)]개의 [math(b)], [math(c)]개의 [math(d)]...'의 형태는 [math(abcd)]처럼 모든 숫자를 붙여서 나타낸다.[2] 다만 가장 큰 자릿수부터 숫자의 개수를 세되, 자릿수의 값이 달라지면 그만 세고 그 달라진 수의 개수를 센다. 또한, 각 자릿수에 전혀 등장하지 않는 수는 '0개의 1'처럼 세지 않고 아예 생략한다.

이상의 설명대로라면 읽고 말하기 수열은 다음과 같다. 말로만 설명해서는 이해가 어려울 것이니 직접 수열을 보라.
[math(n)] [math(L_n)] 해설
[math(1)] [math(1)] 시작.
[math(2)] [math(11)] 앞의 수 [math(1)]은 '1개의 1'이다.
[math(3)] [math(21)] 앞의 수 [math(11)]은 '2개의 1'이다.
[math(4)] [math(1211)] 앞의 수 [math(21)]은 '1개의 2, 1개의 1'이다.
[math(5)] [math(111221)] 앞의 수 [math(1211)]은 '1개의 1, 1개의 2, 2개의 1'이다.
[math(6)] [math(312211)] 앞의 수 [math(111221)]은 '3개의 1, 2개의 2, 1개의 1'이다.
[math(7)] [math(13112221)] 앞의 수 [math(312211)]은 '1개의 3, 1개의 1, 2개의 2, 2개의 1'이다.
[math(8)] [math(1113213211)] 앞의 수 [math(13112221)]은 '1개의 1, 1개의 3, 2개의 1, 3개의 2, 1개의 1'이다.
⋮ ⋮ ⋮

이 경우 읽고 말하기 수열의 일의 자리는 항상 [math(1)]이다. [math(L_{1}=1)]인 이상 마지막에는 '[math(1)]'의 개수를 셀 수밖에 없고, '[math(n)]개의 [math(1)]'이 되어 '[math(n1)]' 꼴로 표기가 끝날 수밖에 없다. 다만 원래 이 수열은 서구권에서 만든 만큼 서구권 어순을 따라서 그런지(one of 1, two of 1...), 한국인이 읽으면 이해는 되지만 다소 부자연스럽거나 서양 언어를 번역한 듯한 느낌이 들 수 있다.

그래서 한국어 어순을 따라 '[math(a)]개의 [math(b)]'가 아니라 '([math(??)]에는) [math(b)]가(이) [math(a)]개' 식으로 나타낼 수도 있다.[3] 이 경우 읽고 말하기 수열은 다음과 같이 된다.
[math(n)] [math(L_n)] 해설
[math(1)] [math(1)] 시작.
[math(2)] [math(11)] 앞의 수 [math(1)]에는 '1이 1개' 있다.
[math(3)] [math(12)] 앞의 수 [math(11)]에는 '1이 2개' 있다.
[math(4)] [math(1121)] 앞의 수 [math(12)]에는 '1이 1개, 2가 1개' 있다.
[math(5)] [math(122111)] 앞의 수 [math(1121)]에는 '1이 2개, 2가 1개, 1이 1개' 있다.
[math(6)] [math(112213)] 앞의 수 [math(122211)]에는 '1이 1개, 2가 2개, 1이 3개' 있다.
[math(7)] [math(12221131)] 앞의 수 [math(112213)]에는 '1이 2개, 2가 2개, 1이 1개, 3이 1개' 있다.
[math(8)] [math(1123123111)] 앞의 수 [math(12221131)]에는 '1이 1개, 2가 3개, 1이 2개, 3이 1개, 1이 1개' 있다.
⋮ ⋮ ⋮

이 경우, 수열의 각 항의 자릿수의 배열이 모두 역순이 되므로 맨 앞 자리가 항상 1이 된다.

2.1. 파생형

  • [math(L_{1})]이 1이 아닌 임의의 다른 한자릿수(k)일 경우
[math(n)] [math(L_n)]
[math(1)] [math(k)]
[math(2)] [math(k1)][4]
[math(3)] [math(k111)][5]
[math(4)] [math(k113)][6]
[math(5)] [math(k11231)][7]
[math(6)] [math(k112213111)][8]
[math(7)] [math(k11222113113)][9]
[math(8)] [math(k1122312311231)][10]
⋮ ⋮
[math(L_{1}=1)]일 때보다 더 큰 수로 나오며, 맨 처음 자리에 k가 1개 있으니 k 뒤엔 무조건 1이 붙어 k값이 뒤쪽 자리 값에 영향을 주지 않으므로 k를 떼고 보면 k값에 관계 없이 똑같은 값이 나온다.
  • 2진법으로 위 수열을 읽을 경우
[math(n)] [math(L_n)](2진법) [math(L_n)](10진법)
[math(1)] [math(1)] [math(1)]
[math(2)] [math(11)][11] [math(3)]
[math(3)] [math(110)][12] [math(6)]
[math(4)] [math(11001)][13] [math(25)]
[math(5)] [math(11001011)][14] 203
[math(6)] [math(1100101101110)][15] 6510
⋮ ⋮ ⋮
[math(L_{n-1})]의 값이 [math(L_{n})]의 앞쪽 자리로 계승됨을 알 수 있다.

3. 성질

각 자릿수의 값이 몇 개인지 세어 그것을 다음 항의 표기에 반영하므로, 한 번 출현한 자릿수는 영원히 그 수열에서 사라지지 않는다. 예를 들어 한 번 [math(3)]이 어떤 항의 어떤 자릿수에 출현하면, [math(3)]이 몇 개인지 세어 '[math(n)]개의 [math(3)]' 또는 '[math(3)]이 [math(n)]개' 식으로 그것을 바로 다음 항의 표기에 반영하므로, [math(3)]이 다음 항의 적어도 하나 이상의 자릿수에 출현하게 된다. 그렇다면 그 다음의 항도, 또 그 다음의 항도 마찬가지임은 자명하다. 이를 수학적으로 표현하면 다음과 같다.
  • 임의의 자연수 [math(m)], [math(n)]과 [math(0\leq{a}\leq{9})]인 정수 [math(a)]에 대하여, [math(L_n)]의 적어도 하나 이상의 자릿수에 [math(a)]가 출현한다면, [math(m)]의 값에 관계없이 [math(L_{n+m})]의 적어도 하나 이상의 자릿수에 [math(a)]가 출현한다.

4. 기타

[1] 영어 'Look and Say sequence'의 첫 글자를 땄다. [2] 즉 일반적인 수식에서처럼 곱하기 기호를 생략([math(a×b×c×d)] → [math(abcd)])한 게 아니라, 단순히 띄어쓰기를 생략하고 붙여서 썼음을 나타내는 것이다. 예를 들어 [math(a=1, b=2, c=3, d=4)]라면 전부 붙여 써서 [math(abcd=1234)]가 되는 식이다. [3] 실제로 베르나르 베르베르의 소설 '개미'의 국문판에서는 번역자가 이를 감안해 위 수열을 아래와 같이 바꿨음을 각주를 통해 밝혔다. [4] [math(k)]는 'k가 1개'이다. [5] [math(k1)]은 'k가 1개, 1이 1개'이다. [6] [math(k111)]은 'k가 1개, 1이 3개'이다. [7] [math(k113)]은 'k가 1개, 1이 2개, 3이 1개'이다. [8] [math(k11231)]은 'k가 1개, 1이 2개, 2가 1개, 3이 1개, 1이 1개'이다. [9] [math(k112213111)]은 'k가 1개, 1이 2개, 2가 2개, 1이 1개, 3이 1개, 1이 3개'이다. [10] [math(k11222113113)]은 'k가 1개, 1이 2개, 2가 3개, 1이 2개, 3이 1개, 1이 2개, 3이 1개'이다. [11] [math(1)]은 '1이 1개'이다. [12] [math(11)]은 '1이 2(10)개'이다. [13] [math(110)]는 '1이 2(10)개, 0이 1개'이다. [14] [math(11001)]은 '1이 2(10)개, 0이 2(10)개, 1이 1개'이다. [15] [math(11001011)]은 '1이 2(10)개, 0이 2(10)개, 1이 1개, 0이 1개, 1이 2(10)개'이다.

분류