# Questions tagged [stirling-numbers]

There are two kinds of Stirling numbers. Stirling numbers of the first kind $[{n \atop k}]$ count the number of ways to arrange $n$ objects into $k$ cycles. Stirling numbers of the second kind $\{ {n \atop k} \}$ count the number of ways to partition a set of $n$ objects into $k$ non-empty subsets.

499 questions
Filter by
Sorted by
Tagged with
20 views

### Closed-form solution to the recurrence

Context In a game players are divided into two groups, A and B. Players in A know identities of all players whereas players in B only know the identity of himself. In the first round Group A ...
48 views

88 views

### Combinatorial proof of ${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$

It's known that Stirling numbers of the second kind satisfy the following relation: $${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$$ However I have not ever ...
22 views

### How do I derive the formula S(G,k)=S(G+e,k)+S(G/e,k)?

I found this in a paper from Auburn University and they just state it but do not derive it. I would like to know how to derive it. I'm fairly certian that e is edges in the graph G, but I don't know ...
49 views

### Use combinatorial reasoning to show that Stirling number

Use combinatorial reasoning to show $\begin{Bmatrix} n\\ n-2 \end{Bmatrix} = \binom{n}{3} + 3\binom{n}{4}.$ The Stirling number is the number of permutation of n into $n-2$ parts.
47 views

76 views

38 views

### What is the reasoning behind Stirling number $S(n,2)$?

The answer that was given in class was $(2^n -2)/2$. I think it's trying to use the theorem that the number of $k$-digit strings that can be formed over $n$ element set is $n^k$. Or, I think it ...
79 views

### Combinatorial proof for Touchard's congruence

Bell number denoted $B_n$ is the number of ways to partition a set with cardinality $n$ into $k$ indistinguishable sets , where $0\le k\le n$ It's known that Bell numbers obey Touchard's Congruence ...
30 views

### A formula for $r$-fold sums of powers of integers

Let $m \geq 1$ be a fixed integer. There are classical well-known formulas for the sum $\sum\limits_{k=0}^{n} k^{m}$ involving Bernoulli polynomials and/or Stirling numbers. For instance I am ...
47 views

### Distribution into different groups if blank groups are not permissible

The number of ways in which $n$ different things can be distributed into $r$ different groups if blank groups are not allowed is: $r^n-{}^rC_1(r-1)^n+{}^rC_2(r-2)^n-\cdots+(-1)^{r-1}.{}^rC_{r-1}$ The ...
68 views

### Stirling Numbers of the Second Kind Proof

Prove that \begin{align*} \sum_{n=1}^\infty S(n,n-2)x^n=\dfrac{x^3(1+2x)}{(1-x)^5} \end{align*} My guess is that I have to take the LHS and simply it, as well as take the RHS and simplify ...
76 views

### integral representation for $\sum_{k=0}^{x}k^{p}$

How the following integral representation can be derived? $$\sum_{k=0}^{x}k^{p}=\int_{0}^{x+1}B_{p}\left(t\right)dt=\frac{B_{p+1}\left(x+1\right)-B_{p+1}}{p+1}$$ I know Faulhaber's formula which is ...
53 views

### Asymptotic Expansion of MGF of squared Poisson - Touchard Polynomials and Second stirling number

What is the asymptotic expansion of the following expression as $\theta \to 0^+$? Alternatively, what is the asymptotic expansion of the MGF $M(\theta)$ of the squared Poisson(1) as $\theta \to 0^+$? ...
### Stirling numbers: Show that $S(n+1, r)=rS(n, r)+S(n, r-1)$.
I know that the Stirling numbers of the second kind are the number of partitions of an $n$-set with $r$ non-empty parts, and that they can be denoted $S(n,r)$. How would I then show \$S(n+1, r)=rS(n, ...