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.
574
questions
0
votes
0answers
22 views
Isolate term in combinatoric inequality
I am trying to isolate $\Delta k$ to the left of the expression below to find for which values of $\Delta k$ the expression is positive. I have an intuition that it should be true for all $\Delta k>...
1
vote
2answers
39 views
Unsigned Stirling number of the first kind summation
I'm solving a question and I confronted with this summation:
$A_n = \sum _{k=1}^n\left(n-k\right)\begin{bmatrix}
n\\
k
\end{bmatrix}$
Where$ \begin{bmatrix}
n\\
k
\end{bmatrix}$ is unsigned Stirling ...
-6
votes
0answers
22 views
Evaluating limits by using Stirling's approximation [closed]
Let $a_1,a_2,a_3,\dots,a_n,\dots$ be a sequence of real numbers with $a_{n+1}=a_n+\sqrt{1+a_n^2}$ and $a_0=0$. Prove that $\lim\limits_{n \to \infty} \frac{a_n}{2^{n-1}}=\frac4\pi$.
So I tried ...
-1
votes
0answers
42 views
Prove identity $\sum_{k}{n\brack k}{k\brace m}=\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ [duplicate]
I'm looking for a proof of this identity:
$$
\sum_{k}{n\brack k}{k\brace m}=\binom{n}{m}\frac{(n-1)!}{(m-1)!}
$$
I'm looking especially for a combinatorial proof (if such exists), but different method ...
0
votes
2answers
66 views
Closed form of $\sum_{k=1}^{n} s(n, k) k x^{k}=?$
My question is
$$\sum_{k=1}^{n} s(n, k) k x^{k}=?$$
$s(n, k)$ are Stirling numbers of the first kind. Here is a reference for second kind of stirling numbers.
Formula for $\sum_{k=0}^n S(n,k) k$, ...
0
votes
0answers
39 views
Stirling unsigned numbers of first kind, identity.
I would like to find a combinatorial proof of the following formula, concerning Stirling numbers of first kind (unsigned):
$$s(n+1,k+1)=\sum_{j=k}^n \frac{n!}{j!} s(j,k).$$
Has anyone an idea?
Thank ...
0
votes
0answers
28 views
Finding a function such a partition of a set contains $x$, $y$, $x+y$ for some two elements [duplicate]
Prove that there exists a function $f: \mathbb{N} \to \mathbb{N}$ such that a partitioning of $\{1,2,...,f(n)\}$ into $n$ classes will have some $x,y$ such that $x$, $y$ and $x+y$ all belong to the ...
0
votes
1answer
30 views
Rising factorial stirling numbers from the recurrence
I have seen a proof that the recurrence of the unsigned stirling numbers of the first kind can be derived from the rising factorial definition.
That is, $s(n,k)$ are given by the coefficients on $x^k$ ...
0
votes
1answer
36 views
Induction proof with Stirling numbers of the second kind
I'm having trouble understanding this exercise from Bóna's book "A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory"
It says:
Let m be a fixed positive integer. ...
3
votes
2answers
80 views
Show that $\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}$
Let $m\le n$ be positive integers. I want to prove the inequality $$\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}.$$
I have tried direct algebraic ...
4
votes
3answers
155 views
Stirling number relation
Let $S(k,n)$ denote the Stirling number, i.e. the number of ways to partition $k$ distinguishable objects into $n$ indistinguishable blocks. Then consider $S(n+r,n)$ for some fixed $r$, how can I show ...
0
votes
1answer
44 views
Problem about counting partitions
The number $f(n)=B(n)-\sum_{k=1}^n B(n-k) {n \choose k}$ counts certain partitions of $[n]$.Which partitions?
From Wiki, The Bell numbers satisfy a recurrence relation involving binomial coefficients:...
1
vote
1answer
39 views
Show that for every natural number $n$ there is equality - Stirling numbers of the second kind [closed]
Show that for every natural number $n$ there is equality:
$$\left\{ n\atop 3\right\} = \frac{3^{n-1}-2^n+1}{2}$$
To prove this equality use equality
$${{n+1}\brace{m+1}} = \sum_{k=0}^{n}{n\choose k}...
3
votes
0answers
94 views
Is there a closed form of $\sum_{k=1}^{n} \frac{|S_{1}(n,k)|}{k!}z^{k} $?
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
$$ \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)_{n} = \prod_{k=0}^{n-1} (z+k) , $$ and $$ \...
1
vote
1answer
44 views
What is $\sum_{n} |S_{1} (n,k)| x^{n} $?
I'm trying to find out what the generating sum in the question title amounts to. So far, I've found the following related results (see p. 5 of this paper):
$$ \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)_{n}...
4
votes
2answers
104 views
How to prove an identity involving a finite sum of binomial coefficients
I’m struggling to prove this identity $\displaystyle\sum_{m=1}^{n}{\left(\binom nm\frac{{{\left( -1 \right)}^{m-1}}n!}{m} \right)}=\sum_{m=0}^{n-1}{\frac{n!}{n-m}}$. I do understand that it equals $\...
1
vote
0answers
54 views
Where am I misunderstanding this formula for Stirling numbers
Wkipedia says to count surjections with inclusion exclusion for this formula for the stirling numbers:$${n\brace k}={\frac {1}{k!}}\sum _{{j=0}}^{{k}}(-1)^{{k-j}}{k \choose j}j^{n}$$ I get that for $...
1
vote
1answer
33 views
Equivalence relations and Stirling numbers
Show that there are $\sum_{k=1}^{n}S_{n, k}$ equivalence relations on an n-element set. The numbers Sn,k
are Stirling numbers of the second kind.
I am learning discrete mathematics from different ...
2
votes
0answers
36 views
Show that the Stirling numbers of the second kind satisfy the recurrence:
I need help satisfying this recurrence. Thanks in advance!
Show that the Stirling numbers of the second kind satisfy the recurrence:
S(k,n) = $\sum_{i=1}^k S(k-i, n-1) {k-1 \choose i-1}$
I think a ...
0
votes
1answer
38 views
Stirling Numbers of second kind recurrence
While learning the stirling numbers of second kind, we see a recursive relation :
$$S(n, r) = S(n-1, r-1) + k\cdot S(n-1, r)$$
And we get its solution as :
$$S(n, r) = (1/{r!})[r^n - C(r,1)\cdot (r-1)^...
6
votes
1answer
137 views
Is there a standard compact notation for $k!{n\brace k}$?
Is there a standard compact notation for the numbers
$$
?(n,k)=\sum_{i=0}^k(-1)^i\binom ki(k-i)^n\equiv k!{n\brace k}
$$
where ${n\brace k}$ is the Stirling number of the second kind? In ...
5
votes
0answers
71 views
Is this combinatorics derivation correct?
On the Wikipedia I found the following formula:
$ x^m = \sum\limits_{k=1}^{m+1} \left \{ \begin{array}{cols} m+1 \\ k \end{array}\right \} (x-1)^{\underline{k-1}} \,\,\,\,\,\, (1) $
See: https://en....
3
votes
2answers
116 views
Difference of the Stirling cycle numbers and the Stirling set numbers
Denote by $\left\langle\!\! \left\langle k\atop j\right\rangle\!\! \right\rangle$ the second-order Eulerian numbers A340556. Define
$$ \left| n\atop k\right| = \sum_{j=0}^k \left( \binom{n + j - 1}{...
0
votes
1answer
33 views
Number of bits in a stirling number
I know that the number of bit required for $N!$ is $\Theta(n\log n)$ by the stirling approximation. But what is the number of bits required for a stirling number of the first kind of the form $\left[\...
2
votes
1answer
96 views
An associated Stirling number identity related to the second-order Eulerian numbers.
A similar Stirling number identity representing the second-order Eulerian numbers
can be found at this question.
We denote the associated Stirling cycle numbers as $\left[\!\left[ n\atop k\right] \! \...
0
votes
1answer
25 views
Stirling Numbers of the first kind diagonal closed form, understanding indexing.
So for the signed stirling numbers of the first kind, I wanted a formula for the diagonals
On Wikipedia they describe the formula as the below. I don't quite understand how the indexing works for the ...
1
vote
1answer
27 views
Is this Inclusion-Exclusion: $m$ balls colored $n$ colors such that each color is represented?
Suppose you have $m$ balls each of which can be colored by $n<m$ different colors, and your paint cans are unlimited. I want to count the number of ways that you can color balls such that each ...
4
votes
1answer
144 views
A Stirling number identity representing the second-order Eulerian numbers.
Graham, Knuth, and Patashnik give in
CMath
a thorough introduction to the Stirling numbers.
On table 250 and table 251, they compile two pages of
Stirling number identities.
Of course, there are many ...
5
votes
2answers
128 views
Limiting Sum including Stirling numbers
I would like to simplify the following summation including $S(m,n)$, Stirling numbers of the Second kind.
$\begin{gather*}\\
&&
\frac{1}{n^{n+1}}\sum_{k=1}^{n-1}\binom{n}{n-k}S\left( n,n-k\...
1
vote
2answers
50 views
Numerically evaluate a series involving Stirling numbers of the second kind
How can I numerically evaluate the following for $n$ above one million:
$$ \sum_{k>=n} \sum_{i=0}^{n-1} (-1)^i {{n-1}\choose{i}} \left( \frac{n-1-i}{n} \right)^{k-1} k (k+1)$$?
I have tried ...
2
votes
1answer
44 views
Recurrence relation for Stirling number of first kind with a minimum value
As it states in Wikipedia: Stirling numbers of the first kind count permutations according to their number of cycles. And the recurrence relation is as follows:
$\left[{n+1\atop k}\right] = n \left[{n\...
2
votes
2answers
83 views
Summation including Stirling numbers of the second kind
I would like to show the following: (I am pretty sure it is correct but was not able to prove it.)
$\begin{eqnarray*}
&&\sum_{j=1}^{n}j\binom{n}{j}S\left( n,j\right) j! =n(n^n-(n-1)^n) \\
&...
6
votes
3answers
171 views
Compact formula for the $n$th derivative of $f\left(\sqrt{x+1}\right)$?
I'm interested in a general formula for
$$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big].$$
In particular, Fàa di Bruno's formula gives
$$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big]=\sum_{k=...
2
votes
1answer
101 views
A combinatoric identity involving Eulerian and Stirling numbers
Let
$$
A_{n}(x)=\sum_{k=0}^{n}\left\langle\begin{array}{l}
n \\
k
\end{array}\right\rangle x^{n-k}
$$
Eulerian Polynomials
and $$
\left\langle\begin{array}{l}
n \\
k
\end{array}\right\rangle
$$ are ...
0
votes
0answers
20 views
Proof of $S_{n,r} = \frac{1}{r!} \sum_{k=0}^r (-1)^{r-k} \binom{r}{k} k^n$ with inclusion-exclusion principle [duplicate]
For $n, r \in \mathbb{N}$, $(X_1, ...,X_r)$ is an ordered partition of $[n]$ in $r$ non-empty sets, if $X_1,..., X_r$ are disjoint and non-empty subsets of $[n]$ for which it holds that $X_1 \cup .....
1
vote
1answer
60 views
Combinatorics - Counting Something Similar to Unsigned Stirling Numbers of the First Kind
I want to count something similar to unsigned Stirling numbers of the first kind. Can someone tell me what math describes the quantity I'm interested in?
Suppose I have $n$ people numbered $1, 2, ..., ...
1
vote
1answer
68 views
Show that the number of ways of splitting a set with $n$ elements into $k$ non-empty subsets is equal to $x^n$'s coefficient in a series
The series evaluates to (could not put it in the title): $$\frac{x^{k}}{(1-x)(1-2x)...(1-kx)}$$ I tried to come up with something. A solution would probably require a use of the geometric series ...
3
votes
1answer
43 views
Ambiguous solution on arranging $6$ people on $3$ indistinguishable tables.
If there must be at least one person in each table, in how many ways can $6$ people be seated around three circular tables?
(We assume tables are indistinguishable)
This problem was an introductory ...
1
vote
1answer
46 views
Further Stirling number series resummation
\begin{equation}
\sum_{m=1}^\infty\sum_{n=1}^\infty (-1)^{n } \frac{S_m^{(3)}}{m! n}(-1 + u)^{(m + n - 1)} (\frac{x}{-1 + x})^m
\end{equation}
Note: $S^{(3)}_m$ belongs to the Stirling number of the ...
0
votes
1answer
54 views
A problem on Stirling numbers of second kind.
In this section, there were four cases, the 4 combinations of distinguishable and identical balls and cells. I could understand [Distinguishable balls and cells] and [identical balls and ...
1
vote
1answer
26 views
Putting 10 distinguishable people into 2 groups so that no group is empty
In how many ways can we put 10 distinguishable people into 2 groups so that no group is empty? Order does not matter in a group and groups are not named.
So I've done some research and people seem to ...
0
votes
0answers
38 views
Stirling number series resummation
\begin{equation}\sum_{m=1}^{\infty}\frac{a_1^3 S_m^{(3)} (u-1)^{m-1}
\left(\frac{x}{x-1}\right)^m}{m!}\end{equation}
Does somebody know the result of this resummation?
Note:
$S_m^{(3)} $ belongs to ...
0
votes
0answers
76 views
General expression of a triangle sequence
\begin{gather*}
\frac{1}{4} \\
\frac{1}{4} \quad \frac{1}{4} \\
\frac{11}{48} \quad \frac{1}{4} \quad \frac{11}{48} \\
\frac{5}{24} \quad \frac{11}{48} \quad \frac{11}{48} \quad \frac{5}{24} \\
\frac{...
5
votes
2answers
93 views
An identity for $\binom{-1/2}{n}$
I would like to show the formula
$$\forall n \in \mathbb{N},\quad\sum_{p=0}^n \binom{n}{p} \frac{(-1)^p}{p!} \prod_{k=0}^{p-1} \left(n+\frac{1}{2} + k\right) = \binom{-1/2}{n} \, , $$
which is true ...
3
votes
1answer
121 views
Combinatorial proof of a nice expression for Stirling numbers of second kind
While answering a question I came across the following nice identity:
$$
\sum_{1\le k_1\le k_2\le\dots\le k_n\le m}\prod_{1\le i \le n}k_i={n+m \brace m},
$$
where ${n+m \brace m}$ refers to the ...
3
votes
1answer
109 views
A combinatorial identity involving Stirling numbers of the second kind
Answering a recent question I came across the following interesting identity:
$$
\sum_{k=0}^m\binom mk{n+k+1 \brace k+1}k!=\sum_{k=0}^m\binom mk (-k)^{m-k}(k+1)^{n+k}.
$$
Is there a simple way to ...
0
votes
1answer
61 views
Stirling number of the 2nd kind with pigeonhole theorem
I have just learnt Stirling number of the 2nd kind and I was also given a hint that this involves the pigeonhole theorem, but I have no idea how to approach this question. Any help would be much ...
0
votes
1answer
90 views
Partial sum of Stirling numbers of the second kind with falling factorial
Let $S_n = \{ 1, 3, ... \}$ be the set of odd numbers not greater than $n$ and $(x)_n$ be the falling factorial $x(x-1)\cdots(x-n+1)$. I am interested in the following partial sum:
$$
\sum_{i \in S_n} ...
2
votes
1answer
314 views
Faulhaber formula from geometric series and operators?
As shown in this post,
$$ \sum_{k=1}^n x^k = x \sum_{k=1}^{n} \binom{n}{k} (x-1)^{k-1}$$
For RHS, notice $x= \left(1+( x-1) \right)$ and using this we get,
$$ \sum_{k=1}^n x^k = \sum_{k=1}^{n} \binom{...
0
votes
2answers
83 views
10 ball as put in 7 boxes randomly. What is the probability that at least one box is empty?
My solution:
First, put one ball at each box and then distribute the remaining 3 balls in 7 boxes.
$p=1-\frac{\binom{9} {3} }{\binom{16}{10}}$
Is this correct?
Or?
$p=1-\frac{\binom{10} {7} 7!7^3}{7^{...
