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
0
votes
0
answers
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
3
votes
2
answers
55
views
Proving an identity relating the number of linearly ordered partitions to Stirling numbers
For $n,k\in N_0$, let $L(n,k)$ be the number of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly ordered subsets. I want to prove that for $n,k\in N_0$,
$L(n,k)=\sum_{i=0}^nc(n,...
- 115
3
votes
1
answer
76
views
Inequality involving Stirling numbers of the first kind
For every $n\geq1$, there is some $f(n)$ such that for the Stirling numbers of the first kind we have:
$c(n,0)<c(n,1)<...<c(n,f(n)-1)\leq c(n,f(n))>c(n,f(n)+1)>...>c(n,n)$
Moreover, $...
- 61
0
votes
0
answers
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
4
votes
1
answer
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
0
votes
0
answers
40
views
Finding the number of ways of posting six letters in three letter boxes such that no letter box remains empty.
Find the number of ways of posting six letters in three letter boxes such that no letter box remains empty.
This question already has answers here. But my doubt is in the following method.
$$^6C_3\...
- 5,236
2
votes
0
answers
51
views
Even generating function with Stirling numbers of the second kind
Is there a known closed form for the following generating function?
$$
\sum_{n=0}^{\infty}\sum_{k=0}^{n} \frac{S(n, k)}{(2n) !}x^{2n}y^k
$$
If we had $n!$ at the denominator instead, this would simply ...
1
vote
0
answers
46
views
Finding sum of Stirling numbers (signed) of the first kind $\sum_{k=0}^n s(n,k)$
Compute $\sum_{k=0}^n s(n,k)=\sum_{k=0}^n (-1)^{n-k}{n\brack k}$.
From definition, it's clear than the sum of the unsigned Stirling numbers is: $$\sum_{k=0}^n {n\brack k}=n!$$
But I'm stucked at $\...
- 97
1
vote
1
answer
52
views
How would you use Stirling numbers to partition a n unique objects, into m unique subsets, with minimum cardinality of 2 for each subset?
For example, how would one go about partitioning 10 numbered balls into 4 numbered boxes, such that each box contains at least 2 balls?
- 25
1
vote
0
answers
34
views
Is there a recurrence in the lower index of the Stirling numbers of the lower kind? [closed]
Is there a recurrence that relates $S(n,k)$, the Stirling number of the second kind, to $S(n,k-1)$ so that you can compute $S(n,k)$ without changing the upper index?
- 307
1
vote
1
answer
75
views
prove that $\sum_{k=0}^{n}S(n,k)(x)_k=x^n$
my attempt:
assume there are a teacher decided to buy $n$ different types of chocolate and present it as a reward to the students who will give a correct answer to one of the questions. The number of ...
user998997
2
votes
1
answer
94
views
Coupon Collector's Problem and Stirling numbers of the second kind: rationale
I have basic notions of probability and combinatorics, but I hadn't heard of Stirling numbers (or I forgot them 😐) until I recently fell into the Coupon Collector's Problem, and into the formula for ...
- 145
1
vote
1
answer
60
views
range of r parameter of second kind r-Stirling numbers
My question is about second kind r-Stirling numbers.
Here are two important papers about it.
https://www.sciencedirect.com/science/article/pii/0012365X84901614#:~:text=The%20r%2DStirling%20numbers%E2%...
- 411
0
votes
1
answer
40
views
In how many different ways can persons A,B,C,D and E be seated around two equal round tables so that no table remains empty?
Persons A and E never sit at the same table.
I'm guessing you could describe this in terms of Stirling numbers but I'm basically lost from there.
My guess is that it's s(5,2) - the number of ...
- 53
1
vote
1
answer
37
views
Limit involving Stirling numbers of the first kind
This question arose whilst working on this problem.
Let $\ \left[{n\atop k}\right]\ $ denote the $\ (n,k)-$th Stirling number of the first kind.
Define $$ f(n) = \left[{n\atop 1}\right] r\ +\ \left[{n\...
- 11.7k
0
votes
1
answer
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
0
votes
0
answers
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
1
answer
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
0
votes
1
answer
119
views
Formula for Stirling numbers expressed with Bernoulli numbers?
Is there a formula which expresses any of the Stirling numbers (1st or 2nd kind) in terms of the Bernoulli numbers? For example, here is the reverse
$$
B_k=\sum_{m=0}^{k} (-1)^m \frac{m!}{m+1}\sigma(k,...
- 465
1
vote
1
answer
68
views
Line up objects in each box after using Stirling number of second kind?
If I have n distinct objects and k identical boxes, I can use Stirling number of second kind to distribute them in every posible way so that every box contains atleast one object. I would like to know ...
- 11
0
votes
0
answers
56
views
What is $\lim_{t \to 0} \left[ {k \atop t} \right] \zeta(t+1) $?
As per this question, I'm trying to evaluate $$\sum_{k=2}^{\infty} \big{(} \zeta(n)^{2}-1 \big{)} = -\sum_{m=2}^{\infty} \frac{H_{-\frac{1}{m}}}{m}. $$
Here, $H_{x}$ is a generalized Harmonic number. ...
- 5,027
0
votes
1
answer
49
views
Combinatorial interpretation of an identity for expressing Stirling number of the second kind using binomial coefficients
Consider the identities as follows (Graham, Knuth, and Patashnik, Concrete Mathematics, Sec.6.2, p.271),
$${x\brace x-2}={x+1\choose4}+2{x\choose 4}$$
and
$${x\brace x-3}={x+2\choose6}+8{x+1\choose6}+...
- 604
0
votes
1
answer
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
1
answer
53
views
Order of central moments for Binomial distribution
Suppose $X\sim \operatorname{Bin}(n,p_n)$ (binomial distribution) with $p_n\to 0$ and $np_n\to \infty$. Then
$$\limsup_{n\to\infty} \frac{\mathbb{E}\left[(X-np_n)^{2k}\right]}{(np_n)^k}<\infty, \...
- 513
1
vote
1
answer
54
views
At an event , If there are m actors, n singers and r tables , find the number of ways you can place the guests. (tables are alike)
So the question asks us to find the total arrangements possible given the no. of singers, actors and tables given the fact that -
A table can have either only singers or only actors, not both.
No ...
- 53
2
votes
1
answer
198
views
Find closed formula for the exponential generating function of sequence counting permutations with 2 cycles.
Find a closed formula for the exponential generating function of $\{c(n,2)\}_{n\geq2}$, that is the sequence counting permutations of length $n$ that consist of $2$ cycles.
My approach: The ...
- 121
1
vote
1
answer
70
views
definition of stirling numbers
Here is a definition without partition about Stirling numbers of second kind.
"Let $S(n,k)$ be Stirling numbers of second kind.
$1 \leq k \leq n$, and let $k$ and $n$ be positive integers. Let $h(...
- 411
1
vote
1
answer
43
views
A calculation about the sum of the product of Binomial and Stirling numbers of the first kind
I have came to a calculation about the sum of the product of Binomial and Stirling first numbers as following
$$
\sum_{i=0}^{2k-j}\binom{2k}{i}(-1)^{i}s(2k-i,2k-i-j)~\text{for}~j=0,1,2,\ldots,k-1, ~\...
- 25
1
vote
1
answer
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 ...
0
votes
1
answer
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
1
answer
34
views
How to relate the number of all applications $X\to Y$ with the Stirling numbers of the second kind?
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}+1$ avoiding 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
...
- 8,321
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\}}
...
- 8,321
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}...
- 33
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 ...
- 784
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
\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}{...
- 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 ...
- 309
0
votes
0
answers
46
views
Summation ofProduct of r-Stirling numbers of the second kind
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)...
