이 글은 벡터공간의 차원이, 그 벡터공간의 기저의 기수(cardinal number)로서 잘 정의됨을 살펴보는 글이다. 유한집합으로 생성되는 벡터공간의 차원이 잘 정의된다는 것은 보통의 선형대수학 교재에 아주 잘 소개되어 있으므로 여기서는 생략하고, 이 글에서는 유한집합으로 생성되지 않는 벡터공간, 즉 무한차원벡터공간의 차원이 잘 정의되는 것을 살펴본다. 이 글은 참고문헌 [1]의 제9장 2절의 내용을 바탕으로 작성하였다. Invariance of Dimensionality 체 \(\mathbb{F}\) 위의 벡터공간 \(V\)가 주어졌을…

장혜영 의원의 페이스북 담벼락에서 본 글이다. 기록해두고 이따금 꺼내 읽고 싶은 글귀라 이곳에 남겨둔다. "힘 있는 자들은 스스로를 망각과 무지라는 막으로 감싼 채 타인의 고통을 회피하고 그 고통과 자신은 관련이 없다고 믿는다. 그들의 눈에는 많은 것이 숨겨지고 빈자와 약자들의 세상에서 멀찍이 떨어져있다. 더 많이 가진 사람일수록 더 조금 안다." -- Rebecca Solnit의 책 '이것은 누구의 이야기인가'에서

\( \newcommand{\rbinom}[2]{\left\langle\!{{#1}\atop{#2}}\!\right\rangle} \newcommand{\secondstirlingnum}[2]{\left\{\!{{#1}\atop{#2}}\!\right\}} \newcommand{\firststirlingnum}[2]{\left[\!{{#1}\atop{#2}}\!\right]} \) 상자에 공을 담는 문제를 살펴보자 해보자. 여기서는 \(8\)가지의 경우를 살펴볼 것이다. 즉 공의 구별 여부, 상자의 구별 여부, 그리고 비어 있는 상자의 가능 여부에 따른 셈하기를 살펴볼 것이다. 구별되지 않는 \(r\)개의 공을 구별되지 않는 \(n\)개의 상자에 담을 때, 빈상자가 없도록 담는 경우의 수는? \(\rightsquigarrow\) 이는 어떤 의미에서는 쉽다고 말 할 수 있겠으나, 이를 쉽다고 여길…

자연수 \(r\)의 분할(partition)이란, 합하여 \(r\)이 되는 자연수들의 모임이다. 만일 \(n\)개의 자연수를 합하여 \(r\)을 만들었다면, '\(r\)이 \(n\)개의 부분(part)들로 분할되었다'라고 말한다. 예를 들어, \(5\)는 \(7\)개의 분할, \( 5;\, 4+1,\ 3+2;\, 3+1+1,\ 2+2+1;\, 2+1+1+1;\, 1+1+1+1+1, \) 을 갖는다. \(5\)의 분할을 셀 때, 예를 들어 \(3+2\)와 \(2+3\)은 동일한 것으로 여긴다는 것에 유의하자. 또한 \(5\)를 한 개의 부분으로 분할하는 방법은 한 가지; \(5\)를 두 개의…

다음 문제를 생각해보자. The Hatcheck Problem. 안쪽에 자신의 이름이 적힌 모자를 하나씩 쓰고 있는 \(n\)명의 사람이 어떤 공연장에 들어가며 출입구에 모자를 맡겼다고 하자. 이들이 공연장에서 나오며 출입구에 맡겼던 \(n\)개의 모자를 각자 하나씩 받았나왔다고 할 때, 자신의 모자를 돌려 받은 사람이 한 명도 없는 경우의 수는? 이 Hatcheck Problem은 굉장히 오래된 문제이다(출입구에 모자를 맡기다니!). 그래도 재미있다. \(n\)개의 양의 정수 \(1, 2,…

이 글에서는 포함-배제의 원리를 일반적이고 명확하게 기술해보고 포함-배제 원리의 산뜻한 증명을 시도해 본다. 이 글에서 소개한 산뜻한 증명은 참고문헌 [1]을 바탕으로 작성한 것이다. 포함-배제의 원리를 산뜻하게 기술하기 학교수학에서는 포함-배제의 원리를 다음과 같이 소개하곤 한다. 포함-배제의 원리(중,고등학교 버전) 유한개의 원소를 갖는 집합 $A, B$에 대하여 \( \vert A\cup B\vert=\vert A\vert +\vert B\vert - \vert A\cap B\vert\) 가 성립한다. 또한 유한개의 원소를…

Lemma for PIE. 원소의 개수가 \(t\)인 전체집합이 주어져있을 때, 전체집합의 부분집합 \(A, B, C, \ldots, Z\)의 어느 것에도 속하지 않는 원소의 개수는 t \)\( -(\vert A\vert+\vert B\vert+\vert C\vert+\cdots+\vert Z\vert) \)\( +(\vert A\cap B\vert+\vert A\cap C\vert+\cdots+\vert Y\cap Z\vert) \)\( -(\vert A\cap B\cap C\vert+\vert A\cap B\cap D\vert+\cdots+\vert X\cap Y\cap Z\vert) \)\( +(\vert A\cap B\cap C\cap D\vert+\cdots+\vert…

아래에 있는 그림에 관한 이야기로 이야기를 시작해보자. 원소를 \(t\)개 갖고 있는 어떤 전체집합이 있고 그 전체집합의 세 부분집합 \(A, B, C\)가 있을 때, 원소의 개수와 관련된 성질을 관찰해보자. 그림의 직사각형은 전체집합을 나타낸다. 각각의 집합 \(S\)에 대하여, \(S\)의 원소의 개수를 \(\vert S\vert\)로 나타내며 이를 집합 \(S\)의 크기(size)라고 말한다. 그림에 있는 세 개의 다이어그램에서 첫 번째를 보면 자명하면서도 매우 중요한 성질을 찾을…

여기서는 기초 조합론 수준의 이항정리를 간단히 살펴본다. 일반화된 이항정리와 관련된 글은 "일반화된 이항정리의 두 가지 증명"이라는 제목의 포스트(바로가기)를 참조하라. 식 \((a+b)^{n}\)을 전개했을 때, \(a^{i}b^{j}\)의 계수는 무엇일까? 식 \((a+b)^{n}\)을 \( \underbrace{(a+b)(a+b)(a+b)(a+b)\cdots(a+b)}_{\text{\(n\)개의 \((a+b)\)의 곱}} \) 으로 나타내어, \(n\)개의 인수 중 \(i\)개의 인수에서 \(a\)를 택하고 나머지 \(j\)개의 인수에서 \(b\)를 택하여 곱한 것으로 항 \(a^{i}b^{j}\)가 만들어진다는 것을 알 수 있다. 따라서 \((a+b)^{n}\)를 전개하여 얻는…

Quickies. 아래의 문제들을, 각 질문에 바로 답할 수 있을 때까지, 다른 날짜에 세 번 이상 풀어보는 것을 강력히 권한다. 각 질문을 읽으면서 바로 답할 수 있을 정도가 되어야 한다. \(16\)쌍의 여학생-남학생 커플에서 5명의 여학생을 택하는 경우의 수는? \(7\)개의 글자 AAABBBB를 배열하는 경우의 수는? \(12\)개의 글자 AAABBBBCCCCC를 배열할 때, C끼리는 이웃하지 않도록 배열하는 경우의 수는? \(10\)명의 사람을 일렬로 앉히는 경우의 수는?…

콘 아이스크림 \(12\)가지의 맛을 고를 수 있는 아이스크림 가게에서, 중복을 허용하지 않고 \(5\)개의 싱글 콘 아이스크림을 주문하는 경우의 수는 \(\binom{12}{5}\)임을 알고 있다. 또한 중복을 허용하여 싱글 콘 아이스크림을 주문하는 경우의 수는 \(\binom{12+5-1}{5}\)인 것도 알고 있다. 이제 하나의 콘에 두 가지 맛을 고를 수 있는 더블 콘 아이스크림을 생각해보자. 물론 콘에 아이스크림을 담는 순서를 고려해야 한다는 진정한 아이스크림 미식가와 아이스크림을 담는…

서로 다른 \(n\)개의 물건에서 중복을 허용하여 \(r\)개를 선택하는 경우의 수를 찾아보려 한다. 이를 위해 Mississippi problem을 활용할 것이다. 먼저 다음의 기초적인 문제의 답을 확실히 할 수 있어야 한다. 기둥들을 일렬로 세워 울타리를 만드는데, 인접한 두 기둥은 \(2\)m만큼 떨어져있게 심고, 맨 끝의 기둥 끼리는 \(20\)m만큼 떨어져 있게한다고 할 때, 기둥이 총 몇 개 필요한가? 일렬로 있는 \(10\)개의 물건을 서로 분리하기 위해,…