[til]기초 확률&통계#5: 자연수 분할&집합분할

01. 자연수 분할

  • 생각해 볼 거리1

    • 5를 2개의 자연수 합으로 표현하는 방법
      • {1, 4}, {2, 3}, {3, 2}, {1, 4} : 순서를 고려할 필요 없음
      • 2개
    • 5를 3개의 자연수 합으로 표현
      • {3, 1, 1}, {2, 2, 1}
  • n = n_1+n_2+n_3+……+n_k

    • n을 k개의 수로 분할할 수 있음
    • n>=n_1>=n_2>=n_3>=…..>=n_k
    • 1 <= k <= n
    • example
      • 5
      • k=1 ==> {5}
      • k=5 ==> {1,1,1,1,1}
  • 자연수 n을 n보다 작거나 같은 k개의 자연수의 합으로 순서를 고려하지 않고 표현한 것은 자연수의 분할 이라고 한다.

  • 분할에 대한 표기법

  • P(n, k) = 자연수 n을 k개의 자연수의 합으로 표현의 경우의 수

    • Partition
    • Partition n k
    • example
      • p(5, 2) = {3, 2}
  • 자연수 n의 불할의 수

    • 자연수 n을 n개 이하의 자연수로 표현할 수 있는 총 가지 수
      • p(n, 1)+p(n, 2)+p(n, 3)+….+p(n, n-1)+p(n, n)
    • example: 5의 분할의 수
      • p(5, 1) = 1, {5}
      • p(5, 2) = 2, {4, 1}, {3, 2}
      • p(5, 3) = 2, {3, 1, 1}, {2, 2, 1}
      • p(5, 4) = 1, {2, 1, 1, 1}
      • p(5, 5) = 1, {1, 1, 1, 1, 1}
      • total: 7

p(n, k)의 성질

  • 성질 1

    • p(n, 1) = 1
    • p(n, n) = 1
    • p(n, k) = 0 if k>n
  • 성질 2

    • p(n, k) = p(n-k, 1) + p(n-k, 2) + …. +p(n-k, k)
    • exmaple
      • p(7, 4) = 자연수 7을 자연수 4개로 나타내는 방법
        • 4개의 주머니에 공 7개를 분할아여 채우며, 모든 주머니는 1개 이상의 공을 갖고 있어야 함

  • 각 주머니에는 1개의 공이 있어야 함
    • 나머지 3개의 공을 4개의 주머니에 담는 경우의 수와 같음

  • 성질 3
    • p(n,k) = p(n-1, k-1)+ p(n-k, k)
    • example
      • p(7,3) = 7을 3개의 자연수의 합을 표현하는 경우의 수
      • 1을 포함하는 것과 1을 포함하지 않는 경우로 구분
        • 1+a+b => p(6, 2)
        • a+b+c (a, b, c는 모두 2 이상의 자연수) ==> p(4, 3)
          • a=A+1, b=B+1, c=C+1
          • A+B+C+3 = 7
          • A+B+C=4
          • P(4, 3)

  • 성질 3의 예제
    • p(7, 4) = p(6, 3) + p(3, 4)
    • p(7, 4) = p(6, 3) + 0
    • p(3, 4) = 경우의 수 0, 자연수 3을 4개의 자연수 합으로 표현할 수 없음

2. 집합의 분할

  • {a, b, c} 집합을 부분집합이 합집합으로 표현할 수 있다.
  • { a, b, c }
    • {a} $\cup$ {b, c}
    • {b} $\cup$ {a, c}
    • {c} $\cup$ {a, b}
  • 특징

    • 두 부분 집합은 전체이 부분집합
    • 두 부분 집합은 공집합은 아니다
    • 교집합이 공집합인 서로소
  • 집합의 분할

    • 원소가 유한개인 집합을 공집합이 아니면서 서로소인 집합인 몇 개의 부분 집합의 합집합으로 나타내는 것

  • A = {a, b, c, d}, s(4, 2)

    • 원소가 4개인 집합을 2개의 서로소인 부분 집합의 합집합으로 표현하는 경우의 수
    • 원소의 객수를 (1, 3)으로 분할하는 것과 (2, 2) 분할
    • (1, 3)
      • {1}, {2, 3, 4}
      • {2}, {1, 3, 4}
      • {3}, {1, 2, 4}
      • $_4C_1 * _3C_3=4$
    • (2, 2)
      • $_4C_2 * _2C_2 / 2!=3$
    • 4+3 ==> 7 가지
  • 원소의 갯수가 n 개인 집합 A의 분할의 수

    • s(n, 1)+s(n, 2)+…+s(n, n)
  • s(n, k)의 성질

    1. s(n, 1) = 1
      • {a, b, c}={a, b, c}
    2. s(n, n) = 1
      • {a, b, c}= {a} $\cup$ {b} $\cup$ {c}
    3. 1<k<n, S(n, k) = S(n-1, k-1)+k*S(n-1, k)
      • {a, b, c, d}의 S(4, 3)
        • 4개의 원소 집합을 3개 부분집합의 합집합으로 하는 경우의 수?
        • {a}를 포함하는 집합: S(3, 2)
        • {a}를 단독으로 포함하지 않는 집합
          • {b}$\cup$ {c}$\cup$ {d}
          • {a}를 포함하는 경우의 수: 3배
            • {ab}$\cup$ {c}$\cup$ {d}
            • {b}$\cup$ {ac}$\cup$ {d}
            • {b}$\cup$ {c}$\cup$ {ad}
      • S(4, 3)=S(3, 2)+3S(3, 3)
  • {1, 2, 3, 4} 집합의 모든 분할 경우의 수?

김태완 avatar
작성자: 김태완
1999년 부터 Java, Framework, Middleware, SOA, DB Replication, Cache, CEP, NoSQL, Big Data, Cloud를 키워드로 살아왔습니다. 현재는 빅데이터와 Machine Learning을 중점에 두고 있습니다.
E-mail: taewanme@gmail.com