Stirling numbers of the second kind
(Mylib/Combinatorics/stirling_number_second.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• stirling_number(Ft, int n, int k)
  • n個の区別するボールをk個の区別しない箱に分配する(但し、すべての箱には1つ以上のボールが入る)ような方法の総数。
  • Time complexity $O(k\log n)$

Requirements

Notes

Problems

References

• https://drken1215.hatenablog.com/entry/2018/02/01/200628

Depends on

• Factorial table (Mylib/Combinatorics/factorial_table.cpp)

Verified with

• test/aoj/DPL_5_I/main.test.cpp

Code

#pragma once
#include <cstdint>
#include "Mylib/Combinatorics/factorial_table.cpp"

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  T stirling_number_of_second_kind(int64_t n, int64_t k) {
    if (n == 0 and k == 0) return T(1);

    T ret = 0;
    for (int i = 1; i <= k; ++i) {
      if ((k - i) % 2 == 0)
        ret += ft.C(k, i) * T::pow(i, n);
      else
        ret -= ft.C(k, i) * T::pow(i, n);
    }
    ret *= ft.inv_factorial(k);
    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/stirling_number_second.cpp"
#include <cstdint>
#line 2 "Mylib/Combinatorics/factorial_table.cpp"
#include <cassert>
#line 4 "Mylib/Combinatorics/factorial_table.cpp"
#include <vector>

namespace haar_lib {
  template <typename T>
  class factorial_table {
  public:
    using value_type = T;

  private:
    int N_;
    std::vector<T> f_table_, if_table_;

  public:
    factorial_table() {}
    factorial_table(int N) : N_(N) {
      f_table_.assign(N + 1, 1);
      if_table_.assign(N + 1, 1);

      for (int i = 1; i <= N; ++i) {
        f_table_[i] = f_table_[i - 1] * i;
      }

      if_table_[N] = f_table_[N].inv();

      for (int i = N; --i >= 0;) {
        if_table_[i] = if_table_[i + 1] * (i + 1);
      }
    }

    T factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return f_table_[i];
    }

    T inv_factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return if_table_[i];
    }

    T P(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return factorial(n) * inv_factorial(n - k);
    }

    T C(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return P(n, k) * inv_factorial(k);
    }

    T H(int64_t n, int64_t k) const {
      if (n == 0 and k == 0) return 1;
      return C(n + k - 1, k);
    }
  };
}  // namespace haar_lib
#line 4 "Mylib/Combinatorics/stirling_number_second.cpp"

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  T stirling_number_of_second_kind(int64_t n, int64_t k) {
    if (n == 0 and k == 0) return T(1);

    T ret = 0;
    for (int i = 1; i <= k; ++i) {
      if ((k - i) % 2 == 0)
        ret += ft.C(k, i) * T::pow(i, n);
      else
        ret -= ft.C(k, i) * T::pow(i, n);
    }
    ret *= ft.inv_factorial(k);
    return ret;
  }
}  // namespace haar_lib

Back to top page