# 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 ...
55 views

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$ ...
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 ...
40 views

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{...
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.
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'...
119 views

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: ...
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 ...
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)^{... 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 ... 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\... 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 ... 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 ... 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 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 \begin{equation} {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}{... 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 ... 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 ... 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 \... 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,... 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 ... 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}{... 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 \begin{equation} \sum_{k=2}^{m-1}\binom{m}{k}S(k+1,3)S_{3}(m-k+3,1+3) \qquad \qquad (1) \end{equation} where, $$n\in \mathbb {N}$$ and \begin{equation} S(k+1,3)...