Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- dart
- 기본키 변경
- list_display
- shake!
- iupc
- 카카오 로그인
- 레지스터
- 코드포스
- Round 866
- 넥토리얼
- expand item
- django
- Graph Cost
- 앳코더
- 밑바닥부터 시작하는 딥러닝 1
- Good Bye 2022: 2023 is NEAR
- Flutter
- 1557
- 알고리즘 대회
- vue-google-login
- Codeforces Round 831 (Div. 1 + Div. 2)
- idpiframe_initialization_failed
- 인하대 프로그래밍 경진대회
- Div. 2
- 2022
- Hello 2023
- E - Hanging Hearts
- vue3
- 카카오 API
- 리버싱
Archives
- Today
- Total
pseong
제 1종, 2종 스털링 수 본문
제 1종 스털링 수
모든 노드의 outdegree가 1이고 indegree도 1인 노드가 n개인 그래프에서 k개의 사이클이 생기는 경우의 수를 의미한다.
이 그래프는 일대일 대응이므로 간선은 전단사 함수라고 할 수 있다.
s(n,k) = s(n−1, k−1) + (n−1)s(n−1, k)
어떤 한 노드를 self loop라고 했을 때 n-1개에서 k-1개의 사이클이 생기는 경우의 수는 s(n-1, k-1) 이다.
어떤 한 노드를 제외하고 n-1개에서 k개의 사이클이 생기는 경우의 수는 s(n-1, k) 이고
어떤 한 노드를 이제 이미 만들어진 k개의 사이클로 넣어야 한다.
이 경우 어떤 한 노드의 친구를 정해고 그 친구와 함께 사이클에 들어간다고 하면
친구를 만드는 경우의 수는 n-1개이고 따라서 (n-1)s(n-1, k) 개 이다.
제 2종 스털링 수
n개의 원소를 갖는 집합에서 k개의 부분 집합으로 나누는 경우의 수
S(n, k) = S(n−1, k−1) + kS(n−1, k)
한 원소를 혼자 부분집합을 만들고 나머지 n-1 개에서 k-1개의 부분집합으로 나누는 경우의 수 S(n-1, k-1)
한 원소를 제외한 나머지 n-1 개에서 k개의 집합을 만드는 경우의 수 S(n-1, k)
한 원소가 이미 만들어진 k개의 집합중에서 선택하는 경우의 수 k
따라서 kS(n-1, k) 이다.
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
중국인의 나머지 정리 (0) | 2023.02.19 |
---|---|
세그먼트 트리 (구간 트리), 느리게 갱신되는 세그먼트 트리 (Lazy Propagation) (0) | 2022.03.16 |
Comments