# Questions tagged [stirling-numbers]

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

625 questions
Filter by
Sorted by
Tagged with
23 views

### Stirling number expressed as a polynomial

I need to solve this problem : Let $p$ be an odd number. Show that there exist a polynomial $Q_p$ such that for every natural number $n$, $S_p(n) = Q_p\left(\frac{n(n+1)}{2}\right)$ I tried to solve ...
• 13
55 views

• 61
43 views

### Cycles in stirling cycle numbers example

I was reading about Stirling cycle numbers which count the permutations of $n$ objects that have just $k$ cycles. An example I read mentioned the $6$ permutations of $3$ objects are classified as: $1$ ...
• 1,507
92 views

### proof sum of power using Stirling number

question is prove $$1^{k} + 2^{k} + 3^{k} + \dots + n^{k} = \sum_{i=1}^{n} S(k,i) \cdot i! \cdot {{n+1}\choose{i+1}}$$ In my opinion, LHS means number of functions from X to Y (X has 'k' element and ...
• 53
40 views

• 11.7k
57 views

### Evaluating $\lim_{n\to\infty}\frac{1}{n+1}(\omega+\nu)^{(n+1)}z^\nu{_2F_1}(1,\omega+\nu+1;n+2;1-z)$

I recently found a proof for the following sum \begin{align*} S_n & =\sum_{k=0}^n\mathcal S_n^{(k)}(\Phi(z,-k,\omega)-z^\nu\Phi(z,-k,\omega+\nu))\\ & =\frac{1}{n+1}(\omega+\nu)^{(n+1)}z^\nu{...
• 4,081
25 views

### How do you convert negative integer powers to falling powers?

Is there a systematic way to convert $x^{-n}$ to falling powers for positive $n$? i.e. something like Stirling numbers, but that works when the exponent is negative.
• 307
1 vote
63 views

### Proof/disproof of conjecture involving noncentral Stirling numbers of the second kind

I have a conjecture I am looking at involving the noncentral Stirling numbers of the second kind (for explanation of these numbers, see e.g., Koutras 1982). I'm having some difficulty proving it. I'...
• 3,858
119 views

• 604
58 views

### Stirling Numbers of the Second Kind: Combinatorial Proof

Prove that $$1!\cdot S(n, 1) + 2!\cdot S(n, 2) + \cdots + k!\cdot S(n,k) = k^n,$$ where $k!\cdot S(n,k)$ represents the number of ways to place $n$ distinct objects into $k$ distinct boxes. Answer: ...
• 233
1 vote
53 views

1 vote
61 views

### Alternating sum of numbers of surjective functions

Let $S(n,k)$ denote the number of surjective functions from $\lbrace1,2,...,n\rbrace$ onto $\lbrace1,2,...,k\rbrace$. I am sure that $$S(n,n) - S(n,n-1) + S(n,n-2) - ... +(-1)^{n-1}S(n,1) = 1$$ Have ...
44 views

### Inequality with Stirling numbers of second kind

I have to prove that, $\forall n\geq 1$, $\forall 1\leq k\leq n$, $$\frac{k^{n}}{k^{k}}\leq S(n,k)\leq \frac{k^{n}}{k!}$$ The second inequality, is quite obvious for me, as $k!\cdot S(n,k)$ is the ...
• 587
1 vote
I am studying Stirling numbers of the second kind, and I have just saw why $S(n,k)=\frac{1}{k!}\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$ (knowing that $\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{... • 587 1 vote 2 answers 66 views ### Does the (Stirling number of the second kind) equality${2n\brace 2} = 2^{2n-1}-1$hold? I filled in from the definition of a Stirling number of the second kind that the following holds. $${2n\brace 2} = \frac{1}{2} \sum_{i=0}^{2} (-1)^i \binom{2}{i} (2-i)^{2n}$$ And I've visually ... • 1,306 2 votes 2 answers 78 views ### How to show this identity$\prod_{q=1}^k\frac{1}{1-qz}=\sum_{j=1}^{k}jz\prod_{q=1}^j\frac{1}{1-qz}+1avoiding a proof by induction When looking at a nice problem regarding Stirling numbers of the second kind a challenge was to show the validity of \begin{align*} \color{blue}{\prod_{q=1}^k\frac{1}{1-qz}=\sum_{j=1}^kjz\prod_{q=1}^j\... • 94k 2 votes 2 answers 86 views ### Prove that\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$Question I want to prove the following well known expression for Stirling Numbers of the Second Kind: $$\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$$ My Solution ... 1 vote 1 answer 76 views ### Prove that$\left\{{n+1}\atop{k+1}\right\}=\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}}$Question I want to prove the following well known expression for Stirling Numbers of the Second Kind: $$\left\{{n+1}\atop{k+1}\right\}=\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}} ... 6 votes 1 answer 140 views ### How to pronounce Stirling Numbers of Second Kind {n\brace k}? The Stirling Numbers of the Second Kind, {n\brace k}, count the number of ways to partition an n-element set into k unlabeled non-empty parts and are rather useful for several introductory ... • 71.2k 0 votes 2 answers 50 views ### Stirling numbers of the first kind explicit product in reverse for |s(n,k)|? I'm trying to find an explicit number theory definition of the Stirling numbers of the first kind in reverse as |s(n,k)| not |s(n,n-k)|, not the way it's usually written. Here is the typical ... • 465 2 votes 0 answers 29 views ### Distributing balls into bins for large numbers: approximating probabilities Distributing n balls into m bins with n > m, I want to calculate the probability that at least one box will be empty. If I'm not mistaken, that should be$$p_{m} = 1 - \frac{m! S_n^{(m)}}{m^n}... 0 votes 1 answer 98 views ### Number of surjections and generating function knowing that the number of surjections$N_m\to N_n$is (using the principle of inclusion exclusion):$\displaystyle\sum_{i=0}^n (-1)^i\binom{n}{i} (n-i)^m$furthermore, we know the connection with ... 1 vote 1 answer 113 views ### A formula for$1^m+2^m+3^m+\ldots+n^m$using binomial coefficients [duplicate] It is known that $$\sum_{k=1}^{n}k^1=\binom{n+1}{2}$$ and $$\sum_{k=1}^{n}k^2=\binom{n+1}{2}+2\binom{n+1}{3}$$ Is there a formula for $$\sum_{k=1}^{n}k^m,$$ where$m$is a positive integers, ... • 4,316 4 votes 2 answers 105 views ### Approximation of Stirling numbers of the second kind${2n \brace n}$I want an approximation of${2n \brace n}$as$n\to\infty$, also${\cdot\brace\cdot }$is the Stirling numbers of the second kind. Right now, I know an evaluation {2n \brace n}=O\left(... 1 vote 1 answer 88 views ### Why is the following not$S(n,3)$where$S(n,k)$is a Stirling number of the second kind? (almost solved) In an attempt to relate the number of partitions of integers to that of partitions of distincts objects I stumbled, in the particular case of$k:=3$, on the following sum $$\sum_{\genfrac{}{}{0pt}{1}{... • 2,955 1 vote 0 answers 51 views ### Can I make this combinatorial proof work? I'm trying to come up with a combinatorial proof that$$x^{\overline{n}} = \sum_{k = 0}^n s(n, k)x^k$$where s(n,k) is the stirling number of the first kind. Now, x^{\overline{n}} counts the ... • 307 1 vote 2 answers 187 views ### Combinatorial arguments for two stirling numbers I'm trying to use combinatorial arguments to find simple formulas for \begin{Bmatrix} n\\ 2 \end{Bmatrix} and \begin{Bmatrix} n\\ n-2 \end{Bmatrix} I've used combinatorial arguments to prove ... • 795 2 votes 3 answers 106 views ### What's a formal definition of cycles that will allow me to prove this identity? On page 261 of chapter 6 in Concrete Mathematics, the authors gesture towards the following proof of the identity$$\sum_{k = 0}^n \left[\begin{array}{l} n \\ k \end{array}\right] = n!$$where the \... • 307 1 vote 2 answers 291 views ### Discrete mathematics - ternary strings. Let n be a natural number, n≥3. A ternary string is a sequence of n symbols that has some of the digits 0, 1, 2. In other words, a ternary string is a n-permutation with a repetion of the set {∞⋅0,∞⋅1,... • 33 2 votes 1 answer 106 views ### Ordinary Generating Function For the Unsigned Stirling numbers of the First Kind On Wikipedia Here, the exponential generating function$$\sum_{n=k}^{\infty}{(-1)^{n-k}{n\brack k}\frac{z^n}{n!}}=\frac{1}{k!}(\log(1+z))^k$$is given, where {n\brack k} is the unsigned Stirling ... • 176 0 votes 0 answers 63 views ### Number of equivalence relations by using Stirling number of the second kind I am using bell number to find the number of equivalence relations. While doing so i used the general formula for Stirling number of the second kind$$S(n,k)=\frac{1}{k!}\sum_{i=0}^k (-1)^i \binom{k}{... • 125 0 votes 1 answer 110 views ### Expected number of cycles in random permutations Draw at random a permutation$\pi$in the set of permutations of$n$elements,$S_n$, with probability, $$P(\pi)= \frac{N^{L(\pi)}}{ \sum_{\pi \in S_n} N^{L(\pi)} },$$ where$ L(\pi)\$ is the number ...
I would like to simplify this block $$\sum_{k=2}^{m-1}\binom{m}{k}S(k+1,3)S_{3}(m-k+3,1+3) \qquad \qquad (1)$$ where, $$n\in \mathbb {N}$$ and S(k+1,3)...