Articles of stirling numbers

I just don't see what I do wrong – number of surjections seems higher than number of functions.

EDIT: Answer added. I haven’t slept much lately and I’ve been raging on this thing for a couple hours now. I really hope some people here can have the same obsession/rage and will help me out. I have two sets, A and B. |A| = m, |B| = n. I was looking for the number […]

Sum identity using Stirling numbers of the second kind

Experimenting with series representations of $e^{x e^x}$ I came across the two seemingly different power series $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{(n-k)^k}{(n-k)! \cdot k!}$$ and $$e^{x e^x} = \sum_{n=0}^{\infty} x^n \sum_{k=0}^{n} \frac{1}{(n-k)!} \sum_{i=0}^{k} \frac{1}{(k-i)!} {k-i \brace i}\,.$$ They should be and are in fact identical. By equating the coefficients it is obvious that $$\sum_{k=0}^{n} […]

Nonattacking rooks on a triangular chessboard

Given an $n \times n$ chessboard from which the squares above the diagonal have been removed, find the number of ways to place $k$ non-attacking rooks on this board. I believe the answer to be $S(n+1, n-k+1)$, where $S(n,k)$ is the Stirling number of the second kind. Most of the sources I’ve encountered state this […]

Stirling numbers, binomial coefficients

Could you help me prove the following: $$\left\{n\atop k\right\} = \frac{1}{k!} \cdot \sum^{k}_{j=0} {k\choose j} \cdot j^{n} \cdot (-1)^{k-j}$$ It looks very scary to me. I’ve looked for it in Graham, Knuth, Patashnik’s “Concrete Mathematics”, but I didn’t find it. All I know about Stirling numbers is that we can use them as coefficients in […]

Stirling numbers with $k=n-2$

Is there a more general method of calculating: $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ Like for :$$ \genfrac\{\}{0pt}{}{n}{n-1} $$ we can use $nC_2 $

About the Stirling number of the second kind

Find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ distinct boxes with no empty box, and determine $s_{n,r}$. My solution is $$\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^n=(e^x-1)^n$$ $$=\sum_{k=0}^n(-1)^k\binom{n}{k}e^{kx}=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{r=0}^{\infty}k^r\frac{x^r}{r!}$$ Thus, $s_{n,r}$ is the coef. of $\frac{x^r}{r!}$, which is $\sum_{k=0}^n(-1)^k\binom{n}{k}k^r$. However, I found it in another book that $s_{m,n}=\frac{1}{n!}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m$, where $s_{m,n}$ denotes the […]

Approximating Stirling's number of the second kind to allow for large inputs

I’m looking for an approximation for Stirling’s number of the second kind, $S_2(n,k)$, which counts the ways to partition a set of $n$ objects into $k$ non-empty subsets: ( ) I need to compute $S_2(n,k)$ for values of $n$ up to $10^6$ and values of $k$ up to $10^5$ or so. Is this possible? […]

$\Delta^d m^n =d! \sum_{k} \left { {k+n} \brace m + d}(-1)^{m+k}$ Is this a new formula?

(EDIT: The variable $z$ is changed to $d$ so as not to be confused with generating function notation) I have derived this formula involving the Stirling numbers that I now feel confident is correct (at least for non-negative integers $m$, $n$ and $d$). $$\frac{\Delta^d m^n}{d!} = \sum_{k} \left[ m \atop k \right] { {k+n} \brace […]

Stirling number of the first kind: Proof of Recursion formula

I want to prove this recursion formula for Stirling numbers of the first kind: $$s_{n+1,k+1} = \sum_{i=k}^{n} \binom{i}{k} s_{n,i}$$ But I lack a useful idea. Perhaps someone could inspire me? Kind regards.

Stirling number

I am trying to evaluate the following finite sum: $$ \sum_{k=1}^{n}(-1)^{k}(k-1)!S(n-1, k-1)(\sum_{i=0}^{k-1}H_{i}), $$ where $S(n, k)$ are the Stirling’s numbers of the second kind and $H_{i}$ denotes the $i$ harmonic number. Could you please shed some light? @Gerry Myerson I think that the first few terms obey the sequence with alternating signs.