1. 집합의 분할과 스털링 수

서로 다른 열 개의 팀을 네 그룹으로 나눈다면?

아이브, 르세라핌, 레드벨벳, 에스파, 블랙핑크, 아이들, 트와이스, 오마이걸, 에이핑크, 엔믹스

팀이 하나뿐인 그룹이 존재할 수 있지만 빈 그룹은 없어야 한다.

1) 엔믹스 제외 아홉개 팀을 네 그룹으로 나누고 엔믹스를 배치하는 방법

• 2) 엔믹스 제외 팀을 세 그룹으로 나누고 엔믹스를 홀로 배치하는 방법

팀 수를 n, 그룹 수를 k라 하고 배정 경우의 수를 S(n, k)라 한다면

S(n, k) = S(n-1, k-1) + kS(n-1, k)

이를 제2종 스털링 수라고 한다.

제2종 스털링 수의 특징

1. S(n, 1) = 1
2. S(n, n) = 1
3. n < k 은 의미가 없다.

📍python 코드

S = list()
n = 10
k = 4

for i in range(0, 100) :
  new_list = list()
  for j in range(0, 100) :
    new_list.append(-1)
  S.append(new_list)

#0번 인덱스 고려하지 않고 인덱스 번호와 n, k 번호 동일하게 진행 
for i in range (1, n + 1) :
  for j in range(1, i + 1) :
    if (j == 1) :
      S[i][j] = 1
    elif (j == i) :
      S[i][j] = 1
    else :
      S[i][j] = S[i -1][j -1] + (j * S[i - 1][j])

print(S[n][k])

연습문제

서로 다른 자연수 N개를 다음 규칙에 따라 둘 이상의 여러 그룹으로 분할하고자 한다.
1) 하나의 그룹에는 적어도 하나의 자연수가 존재해야 한다.
2) 각 그룹의 순서는 고려하지 않으며, 그룹 내에 존재하는 자연수의 순서도 고려하지 않는다.

사용자로부터 자연수 N을 입력받아, 분할의 모든 경우의 수를 출력하시오

n = input()
n = int(n)
total = 0
S = list()
for i in range(2, n + 1) :
  k = i

  for i in range(0, 100) :
    new_list = list()
    for j in range(0, 100) :
      new_list.append(-1)
    S.append(new_list)


  for i in range(1, n + 1) :
    for j in range(1, i + 1) :
      if (j == 1) :
        S[i][j] = 1
      elif (j == i) :
        S[i][j] = 1
      else :
        S[i][j] = S[i - 1][j - 1] + (j * S[i - 1][j])


  total += S[n][k]

print(total)

2. 카탈란 수의 뜻과 그 응용

카탈란 수란?(Catalan Number)

C0 = 1일 때, n번째 카탈란 수 Cn은 아래와 같은 점화식을 이용하여 정의될 수 있음

Cn = C0Cn-1 + C1Cn-2 + C2Cn-3 + ... + Cn-3C2 + Cn-2C1 + Cn-1C0

📍python 코드

#카탈란 수의 계산

n = input()
n = int(n)

#초기값 설정하기
C = [1]

for round in range(1, n + 1) :
  new_C = 0
  i = 0
  j = round - 1
  while (j >= 0) :
    new_C = new_C + (C[i] * C[j])
    i = i + 1
    j = j -1
  C.append(new_C)

#마지막 카탈란 수 출력
print(C[-1])

카탈란 수 응용

사용자로부터 N을 입력받아, 정N각형을 삼각형으로 분할하는 경우의 수는?

3. 교란순열과 경우의 수

Dn = (교란 형태로 n개의 쌍을 구성하는 모든 경우의 수) -> D1 = 0, D2 = 1, D3 = 2...

Dn = (n - 1)(D n-1 + D n-2)

연습문제

사용자로부터 자연수 N을 입력받아, 소화전과 제세동기를 설치하는 모든 경우의 수를 구하라.
단, 한 행과 열에 소화전과 제세동기가 한 대씩은 있어야 한다.

n = input()
n = int(n)

for round in range(1, n + 1) :
  fire = 0
  i = 0
  j = round - 1
  while(j >= 0) :
    fire