[일반] 조합론 질문(간단)

[익명(113.60)]

1. n자리 자연수중 같은수가 연속해서 나오지않는 경우의수
2. 이 중 짝수의 개수


1은 9^n인거 귀납으로 쉽게보여지는디
2가 생각보다 안구해짐..

[겨울_(silhouet72)]

저런 n자리 짝수가 x(n)개 있다고 하면.. n+2자리 짝수는 n+1자리 짝수 앞에 숫자 8개 중 하나를 붙이거나 n자리 짝수 앞에 0을 붙이고 그 앞에 숫자 9개 중 하나를 붙이면 되니까 x(n+2)=8x(n+1)+9x(n) 풀면 될듯

[익명(49.143)]

b_n을 연속한 두 수가 나오지 않는 n자리 짝수의 개수라고 하면.. 먼저 1자리수는 4개 2,4,6,8 뿐이니까 b_1 = 4이고.. n이 2 이상이면 b_n = 5(9^n - b_{n-1}) + 4b_{n-1} = 5*9^n - b_{n-1}이라는 점화식을 얻는데, 왜냐하면 앞의 n-1자리가 홀수인, 두 수가 연속해서 나오지 않는 n-1자리수의 경우수는 9^n - b_{n-1}이고 이 경우는 뒤에 2,4,6,8,0 아무거나 붙여도 상관없으니 5(9^n - b_{n-1}), 앞의 n-1자리가 짝수인 경우에는 n-1번째 자리와 다른 수가 n번째 자리에 나와야하니까 2,4,6,8,0 5개 중에서 n-1번째자리인 경우 하나 빼면 총 4가지, 따라서 4b_{n-1}. 이 두개를 더하면 원하는 점화식을 얻겠네.

[익명(49.143)]

댓글에 9^n은 모두 9^{n-1}으로 바꾸면 됨.. 실수

[익명(49.143)]

점화식을 쓰지 않는 bijective한 증명법도 있는데, 이번 댓글에서는 그 방법론에 대해서 다루고자 함. 머릿속으로 생각하는건 아주 쉬운데, 막상 글로 쓰려고 하니까 쓸데없이 복잡해지네.. 이래서 조합론 문제 풀이는 글로 적는게 굉장히 귀찮기 마련이다. 먼저 위의 점화식을 풀면 (9^n + (-1)^n)/2가 나오는데, 보면 9^n의 절반에 가까우니까 연속한 두 수가 출현하지 않는 n자리 홀수와 연속한 두 수가 출현하지 않는 n자리 짝수간의 bijection 비스무리한걸 만들면 좋겠다는 생각을 할 수 있다. 물론 9^n이 홀수이니 정확히 반 나누게 만드는 bijection은 존재하지 않으므로, 적절히 변형을 해야한다. 다음과 같은 bijective한 증명을 생각해보자.

[익명(49.143)]

A_n을 연속된 두 수가 출현하지 않는 n자리 홀수의 모임, B_n을 연속한 두 수가 출현하지 않는 n자리 짝수의 모임이라 하자. 이제 A_n의 임의의 원소 x에 대해서, 만약 x의 n번째 자리수가 2k+1 (k는 1,2,3,4)이면 x의 모든 자리수들 중에서 2k인것을 2k+1로 바꾸고 2k+1인것을 2k로 바꾸자. 바뀐 결과를 x'라 하면 x'는 B_n 안에 들어가게 된다.

[익명(49.143)]

반대로 B_n의 임의의 원소 y에 대해서, 만약 y의 n번째 자리수가 2k (k는 1,2,3,4)이면 x의 모든 자리수들 중에서 2k인것을 2k+1로 바꾸고 2k+1인것을 2k로 바꾸자. 바뀐 결과를 y'라 하면 y'는 마찬가지로 A_n 안에 들어가게 된다. 이제 남은건 x의 n번째 자리수가 1인 경우와 y의 n번째 자리수가 0인 경우인데, 이 경우에는 x의 자리수 중 1인 녀석을 0으로 바꾸고 0인 녀석을 1로 바꾸면, 만약 x의 첫번째 자리수가 1이라면 0으로 바뀌므로 n자리수가 아니게 되어서 문제가 생긴다. 따라서, 얘네들은 다음과 같은 예외처리를 한다.

[익명(49.143)]

n번째 자리가 1인 x∈A_n에 대해서, 1≤k_x≤n을 x의 k_x부터 n번째 자리수가 모두 1과 0으로 이루어진 최소의 자연수라 하자. k_x>1이라면 k_x번째부터 n번째 사이의 자리수 중에서 1인녀석을 0으로, 0인녀석을 1로 변환한 뒤 바뀐 결과를 x'이라 하면 x'는 B_n에 속하게 되며, x'의 n번째 자리는 0이 된다. k_x=1인 경우는 정확히 x=1010...01 꼴의 모양인 경우 뿐이다.

[익명(49.143)]

마찬가지로 n번째 자리가 1인 y∈B_n에 대해서, 1≤k_y≤n을 y의 k_y부터 n번째 자리수가 모두 1과 0으로 이루어진 최소의 자연수라 하자. k_y>1이라면 k_y번째부터 n번째 사이의 자리수 중에서 1인녀석을 0으로, 0인녀석을 1로 변환한 뒤 바뀐 결과를 y'이라 하면 y'는 A_n에 속하게 되며, y'의 n번째 자리는 0이 된다. k_y=1인 경우는 정확히 y=1010...10 꼴의 모양인 경우 뿐이다.

[익명(49.143)]

따라서 우리는 A_n - {1010...01}과 B_n - {1010...10} 사이의 bijection (정확히 말하자면 involution)을 얻었다.

[익명(49.143)]

이제, 1번째 질문의 결론으로부터 |A_n|+|B_n|=9^n임을 알고, n이 짝수인 경우에는 1010...01인 n자리 수는 존재하지 않지만 1010...10인 n자리수는 존재하므로 |A_n|=|B_n|-1이므로, |B_n|=(9^n+1)/2이다. 마찬가지로 n이 홀수인 경우에는 1010...01인 n자리 수는 존재하지만 1010...10인 n자리 수는 존재하므로, |A_n|=|B_n|+1이므로, |B_n|=(9^n-1)/2이다. 종합하면 n의 기우성에 관계없이 |B_n|=(9^n+(-1)^n)/2라는 결론을 얻는다.

[익명(211.36)]

지리네

[코세(rationnel)]

넘치는 수학력 무엇

[익명(117.111)]

다들 감사요 이맛에 수갤합니다