coupon_collector.py 文件源码

def stirling2(n, k):
    """

    The Stirling numbers of the second kind,
    written S(n,k) or :math:`\lbrace\textstyle{n\atop k}\rbrace`
    count the number of ways to partition a set of n labelled objects
    into k nonempty unlabelled subsets.

    ..  math::

        \lbrace\textstyle{n\atop n}\rbrace = 1  \\

        \lbrace\textstyle{n\atop 1}\rbrace = 1  \\

        \lbrace\textstyle{n\atop k}\rbrace = k \lbrace\textstyle{n-1 \atop k}\rbrace + \lbrace\textstyle{n-1 \atop k-1}\rbrace

    Or

    ..  math::

        \left\{ {n \atop k}\right\} = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n
    """

    return 1/factorial(k)*sum( (-1 if (k-j)%2 else 1)*binom(k,j)*j**n for j in range(0,k+1) )