본문 바로가기
[이산수학] 조합이론 - Part 4. 점화식 점화식이란? 점화식(Reccurence relation)은 수열에서 항과 항 사이의 규칙을 수식으로 표현한 것이다.즉, 수열의 어떤 항 an​을 앞에 있는 항들 an−1,an−2,…을 이용해서 나타낼 수 있다면, 이 식을 점화식이라고 한다.점화식을 사용하면 수열의 구조를 간단하게 나타낼 수 있고, 반복되는 계산을 체계적으로 처리할 수 있다.예를 들어 수열 1, 4, 7, 10, 13, …은 각 항이 앞 항보다 3만큼 커지는 규칙을 갖고 있다. 이 수열의 점화식은 다음과 같다.이 식은 “첫째 항은 1이고, 그 다음 항은 앞 항에 3을 더해서 만든다”는 뜻이다.***점화식에서 n은 수열의 항 번호를 뜻함. "점화식을 푼다"는 것은?점화식을 푼다는 것은 반복적으로 항을 계산하지 않고,n만 입력해도 곧바로 값을.. 2025. 6. 3.
[이산수학] 조합이론 - Part 3. 이항정리 이항정리란 ? 수학에서 다항식을 전개할 때 사용하는 중요한 공식 중 하나가 이항정리다.이 공식은 단순히 식을 전개하는 것을 넘어서,선택과 경우의 수라는 조합의 개념이 수학적으로 어떻게 쓰이는지를 잘 보여준다. 가장 간단한 예부터 출발해 보자. 중학교 때 무지성으로 외워서 수능까지 잘 써먹었던 (x + y)2 = x2+2xy+y2 은 사실 조합과 관련이 깊다. ✅ 1단계: 가장 간단한 예부터 출발해 보자먼저 (x + y)2를 전개해보자.이걸 분배법칙으로 전개하면 다음과 같다. 여기서 중요한 점은 xy와 yx가 사실 같은 문자 조합이라는 것이다.즉, 순서만 다를 뿐 둘 다 똑같이 xy라는 항이 되므로 하나로 묶는다.그렇다면 xy라는 같은 문자 조합이 만들어지는 방법은 몇 가지일까?첫 번째 괄호에서 x, 두.. 2025. 6. 3.
[이산수학] 행렬곱은 어떻게 구할까? (feat. 펭귄 90도 회전시키기) 행렬의 합과 차는 직관적으로 이해가 되는 반면 행렬곱은 그 원리와 계산 방식이 다소 복잡하게 느껴질 수 있다. 하지만 행렬곱은 명확한 규칙을 기반으로 하기 때문에 규칙만 알면 간단하게 구할 수 있다. 👌 행렬곱이란?우선 행렬은 숫자(꼭 숫자가 아닐 수도 있음)들이 행(가로)과 열(세로)로 배열된 구조다. 간단한 예를 들어, 두 학생의 국어와 수학 점수를 행렬로 나타내면 다음과 같다. 첫 번째 행은 학생 A의 점수 (국어 80, 수학 90)을, 두 번째 행은 학생 B의 점수 (국어 70, 수학 60)을 의미한다.행렬곱은 두 행렬을 결합하여 새로운 행렬을 생성하는 연산이다. 첫 번째 행렬의 행과 두 번째 행렬의 열을 특정 규칙에 따라 곱하고 더해 새로운 값을 만드는 것이다.  행렬곱의 기본 원리와 조건행렬.. 2025. 3. 11.
[이산수학] 조합이론 - Part 1. 순열과 조합의 차이 (feat. 팩토리얼) 순열(Permutation)이란?모든 순열의 수 :n개의 항목을 가지고 k개를 선택하면서 순서를 고려하는 경우의 수(= 순열의 수)는 n⋅(n−1)⋅(n−2)⋯(n−k+1)이다. 처음 상태: 총 n개의 항목이 있음.1번째 선택 후: 1개를 뽑았으므로 n−1개 남음.2번째 선택 후: 또 1개를 뽑았으므로 n−2개 남음.3번째 선택 후: n−3개 남음. ...(k-1)번째 선택 후: k−1개를 이미 뽑았으므로 n−(k−1)개 남음.이제 k번째 선택을 해야 하는데, 이 때 남아 있는 항목의 수는 n−(k−1)개."k번째 선택"은 총 k번 선택 중 마지막 번째를 의미함. 따라서 이미 k−1번을 선택한 후 남은 항목에서 하나를 더 고르는 상황.남은 항목 수 = n−(k−1) = n-k+1정리하면, 전체 순열의 수.. 2025. 3. 5.