추가 적립 안내

요세미테 국립공원에 대하여 아는 최선의 방법은 많은 경로를 산책하는 것이다. 최적의 경우에, 펼쳐지는 장관은 우리의 단단해진 근육에 풍부한 보상을 해 줄 것이다. 이 책에서는 아름다운 결과를 산책하면서 조합론의 기본을 설명하고자 한다. 첫 장부터, 매우 간단한 기술이 동시에 매우 강력할 수 있다는, 이 분야의 가장 매력적인 특징을 나타내는 많은 예를 보여줄 것이다. 또한 동전의 다른 면, 즉 때로 전적으로 기초적인 듯한 문제가 예상 외로 깊거나 미지일 수조차 있다는 것을 보여줄 것이다. 이 책은 한 두 학기용 조합론 기초 과정의 교재로 저술했다. 기계적인 수준부터 독립적으로 발표할 수 있는 수준까지 매우 광범위한 연습문제를 포함한다. 각 절에 기존의 교재에서 명시적으로 논하지 않은 내용을 포함하는 연습문제가 있는데 강사가 강조점을 옮긴다면 부가적으로 선택할 수 있도록 하기 위하여서이다. 당연히 고전적인 내용인 조합론의 선택 문제와 그래프 이론을 포함했다. 또한 보다 정교한 개념인 램지 이론, 확률론적 방법, 패턴 회피를 포함했다. 이는 패턴 회피의 첫 시도일 것이다. 이 분야의 표면만 스쳤지만 어떤 학생들이 첫 눈에도 주목할 만큼 흥미롭다고 믿는다. 대부분의 학부생은 조합론을 한 과목 이하로 수강하므로 그들을 사로잡는 문제를 가능한 한 많이 보는 것이 중요하다. 이러한 의미에서 제 ?판에서 알고리듬과 계산복잡도 이론에 관한 장을 추가했다. 이 책을 끝까지 읽을 가장 우수한 학부생은 이 두분야에 관하여 매우 어려운 문제를 풍부하게 알게 될 것이다. 제 ?판에서 블록 디자인과그로부터 얻는 코드에 관한 장과 라벨 없는 구조의 계수에 관한 장을 추가했다. 이 책을 조합론은 연구, 강의, 배움이 항상 즐겁다는 믿음에서 썼다. 산책이 끝날 때 독자도 동의하기를 기대한다. 평균보다 현저히 어려운 연습문제는 몇 개의 +로 표시한다. +가 한 개 표시된 문제는 어려운 숙제 수준이다. 두 개 이상 표시된 문제는 독자적으로 발표 가능한 수준이다. 평균적인 문제보다 현저히 쉬운 문제는 -로 표시한다. 각 장의 말미에 부가 연습문제를 제공한다. 이는 대개 그 장에서 가장 쉬운 문제를 포함하나 그러한 문제만으로 국한되지는 않는다.

Chapter 1 기본적인 방법
1장. 일곱은 여섯보다 크다. 비둘기집 원리
1.1 기본적인 비둘기집 원리
1.2 일반화된 비둘기집 원리
연습문제
부가 연습문제
2장. 한 번에 한 단계. 수학적 귀납법
2.1 귀납법
2.2 강귀납법
연습문제
부가 연습문제

Chapter 2 계수 조합론
3장. 그러한 여럿이 있다. 기본적인 계수 문제
3.1 조합
3.2 유한 알파벳에서의 문자열
3.3 선택 문제
연습문제
부가 연습문제
4장. 어떤 방법으로 자르거나. 이항 정리와 관계식
4.1 이항 정리
4.2 다항 정리
4.3 승수가 양의 정수가 아닐 때
연습문제
부가 연습문제
5장. 나누어 정복. 분할
5.1 합성
5.2 집합의 분할
5.3 자연수의 분할
연습문제
부가 연습문제
6장. 그다지 악순환이 아닌 순환. 순열의 순환
6.1 순열의 순환
6.2 제한된 순환 구조의 순열
연습문제
부가 연습문제
7장. 그과도하게 계수하지 않는다. 체
7.1 교집합의 원소 계수하기
7.2 체 공식의 응용
연습문제
부가 연습문제
8장. 한 개의 함수는 많은 수만큼 가치가 있다. 생성 함수
8.1 일반 생성 함수
8.2 지수 생성 함수
연습문제
부가 연습문제

Chapter 3 그래프 이론
9장. 점과 선분. 그래프 이론의 기원
9.1 그래프 개념. 오일러 트레일
9.2 해밀톤 순환
9.3 방향 그래프
9.4 동형
연습문제
부가 연습문제
10장. 연결되어 있음. 트리
10.1 극소의 연결 그래프
10.2 최소 가중 신장 트리, 크러스칼의 탐욕 알고리듬
10.3 그래프와 행렬
10.4 그래프의 신장 트리의 개수
연습문제
부가 연습문제
11장. 좋은 짝짓기. 색채론과 짝짓기
11.1 소개
11.2 이분 그래프
11.3 이분 그래프에서의 짝짓기
11.4 세 가지 이상의 색
11.5 이분 그래프가 아닌 그래프의 짝짓기
연습문제
부가 연습문제
12장. 교차 없음. 평면적 그래프
12.1 평면적 그래프에서의 오일러 정리
12.2 다면체
12.3 지도의 색칠
연습문제
부가 연습문제

Chapter 4 지평
13장. 깨달음이 오는가?(클릭하는가?) 램지 이론
13.1 유한 그래프의 램지 정리
13.2 램지 정리의 일반화
13.3 기하학에서의 램지 이론
연습문제
부가 연습문제
14장. 그토록 회피하기 어렵다. 치환의 조건
14.1 패턴 회피 치환
14.2 스택 정렬 가능한 치환
연습문제
부가 연습문제
15장. 모습은 모르지만, 존재한다. 확률적 방법
15.1 확률의 개념
15.2 예를 제시하지 않는 증명
15.3 독립 사건
15.4 기대값
연습문제
부가 연습문제
16장. 적어도 어떤 순서가 있다. 부분 순서와 격자
16.1 부분 순서의 개념
16.2 포셋의 뫼비우스 함수
16.3 격자
연습문제
부가 연습문제
17장. 최대한 공평하게. 블록 디자인과 오류 정정 부호
17.1 소개
17.2 균형불완전 블록 디자인
17.3 기존 디자인으로부터의 새 디자인
17.4 어떤 BIBD의 존재성
17.5 부호와 디자인
연습문제
부가 연습문제
18장. 그들은 정말 다른가? 라벨 없는 구조 계수하기
18.1 군의 작용에서의 계수하기
18.2 라벨 없는 트리 계수하기
연습문제
부가 연습문제
19장. 이를수록 좋다. 조합 알고리듬
19.1 정의를 대신하여
19.2 정렬 알고리듬
19.3 그래프 알고리듬
연습문제
부가 연습문제
20장. 여럿은 하나보다 많은가? 계산 복잡도
20.1 튜링 기계
20.2 복잡도 클라스
연습문제
부가 연습문제

참고문헌