Questions tagged [stirling-numbers]
The stirling-numbers tag has no usage guidance.
63 questions
29
votes
3
answers
1k
views
Stirling number identity via homology?
This is a question about the well-known formula involving both types of Stirling numbers:
$\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$,
where $S(n,k)$ is the number of partitions of an $n$-element set ...
- 533
20
votes
4
answers
1k
views
Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
Here's an interesting inequality involving binomial coefficient and Stirling numbers of the second kind that I believe holds for all $n,k$:
$$ k^n {n \choose k} \leq n^k {n \brace k} $$
On the left-...
- 483
16
votes
1
answer
584
views
What is this sequence?
This is again a question that I asked at Stack Exchange, but got no answer so far, so I am trying here.
Let:
$$ a_n=\sum_{k\ge0}(k+1) {n+2\brack k+2}(n+2)^kB_k$$
$B_k$ is the Bernoulli number. ${n\...
- 505
15
votes
1
answer
733
views
Positivity of a finite sum involving Stirling numbers
In my research in theoretical physics, I have arrived at some coefficients $a_{n,m}$ depending on two integers, $n\geq 1$ and $0\leq m\leq n$:
$$
a_{n,m}=\sum_{j=0}^{n-1} {2j \choose j+m} \left(\frac{...
- 183
13
votes
4
answers
3k
views
Simple/efficient representation of Stirling numbers of the first kind
Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum
$$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$
...
- 2,235
9
votes
1
answer
339
views
What is the formula for $\mathcal P_{n}^{k} (a_{1}, a_{2}, ...)$, defined by Peter Luschny?
Recently, I was reading a blog post called The P-transform by Peter Luschny, where the following formulas are given:
\begin{align*}
(-1)^k\frac{n!}{k!}\mathcal P^k_n\left(1, \frac1 2, \frac2 3, \dotsc\...
- 93
9
votes
1
answer
826
views
An infinite set of identities using Stirling numbers 1st kind - are they all zero?
I have the following set of series involving the Stirling numbers 1'st kind and binomials, which can be understood as a set of dot-products of row- and column-vectors of two infinite matrices (where R ...
- 5,342
9
votes
1
answer
569
views
Is this a new formula? $\Delta^d x^n/d! = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$
$$\frac{\Delta^d x^n}{d!} = \sum_k \left[ x \atop k\right]{ k+n \brace x + d}(-1)^{x+k}$$
Where $x$, $n$ and $d$ are non-negative integers, $\Delta^d$ is the $d$-th difference with respect to $x$, $\...
- 191
8
votes
1
answer
263
views
Singular values of Stirling numbers matrix
Consider the Stirling numbers of the first kind $s(i, j)$, and form a matrix $S_1(n),$ where the $(i, j)$th entry is $s(i, j)$. (IMPORTANT NOTE the indices start at $0,$ so this matrix is $(n+1)\times ...
- 96.4k
8
votes
1
answer
631
views
Inequality for Stirling numbers of the second kind
I stumbled upon the following inequality which, I believe, is true. I was able to prove it for small k, but I have no proof for the general case. Any help is welcome.
Let $n\geq k\geq 1$ then
$$\left(...
- 343
7
votes
2
answers
820
views
Determinant of matrix with Stirling numbers as elements
After noticing that the determinant of an $n \times n$ matrix $A_n$ with elements $a_{i,j}=i^j$, $1 \le i \le n$, $1 \le j \le n$, is the superfactorial (product of the first $n$ factorials), I wanted ...
- 700
7
votes
0
answers
444
views
Is there any literature on $\sum_{i=1}^{k} \left[ {k \atop i} \right] \zeta(i+1) $?
As per these questions, I'm trying to evaluate $$\sum_{n=2}^{\infty} \big{(} \zeta(n)^{2}-1 \big{)} = 1+ \sum_{m=2}^{\infty} \frac{H_{-\frac{1}{m}}}{m}. $$
Here, $H_{x}$ is a generalized Harmonic ...
- 4,829
6
votes
1
answer
377
views
Some strange multinomial averaging
How do I prove :
$\sum_{j=2}^{n} (-1)^j {\frac {M(n+j,j;2)}{j!}} = (-1)^n n! + 1$?
where $M(n+j,j;2)$ is the multinomial sum $M(n+j,j;2) = \sum_{t_1 + t_2 + \dotsc + t_j = n+j, t_k \geq 2} {n+j \...
- 405
5
votes
1
answer
585
views
Alternating sums of alternate Stirling numbers
Does anybody know of any identities or combinatorial interpretations for alternating sums of alternate Stirling numbers?
I am particularly interested in expressions of the form:
$$\pm\sum_{k}(-1)^k|...
- 1,327
5
votes
3
answers
1k
views
Acyclic orientations of complete graphs in terms of Stirling numbers?
It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity:
$$n!=\sum_{k=1}^ns(n,k),$$
where the $...
- 1,327
5
votes
0
answers
775
views
A conjecture about the degrees of special polynomials
Define the congruence "modulo m" on exponential Taylor series as
$$
\sum_{n=0}^\infty \frac{a_n}{n!}x^n \equiv \sum_{n=0}^\infty \frac{b_n}{n!} x^n \mod m \iff \forall n: \frac{a_n-b_n}{m}\in \mathbb{...
- 237
4
votes
2
answers
427
views
Divisibility of Stirling numbers
It is well known that if $p$ is prime, Stirling numbers of the first and second kind, $s_1(p,k)$ and $s_2(p,k)$, are divisible by $p$ if $1<k\le p-1$ (Lagrange ; easiest is working in $\mathbb F_p$ ...
- 3,630
4
votes
1
answer
887
views
A bound involving Stirling numbers of the second kind and the asymptotics
Let $S_{n,r}$ denote the Stirling number of the second kind. Define $A_{n,r}:=\frac{\binom{n+r-1}{n}(n+r)!}{S_{n+r,r}r!}$. I want to prove:
$A_{n,1}\ge A_{n,2}\ge..\ge A_{n,r}\ge \lim_{r\to\infty} ...
- 2,232
4
votes
2
answers
495
views
Showing this formula counts these things
I'm writing an article, and I got stuck trying to prove that some numbers are positive. I have a relatively good intuition for guessing what an expression is counting, but in this case I'm not being ...
- 1,889
4
votes
2
answers
219
views
how to prove identity for nth derivative of $(\text{arctanh}(x))^j$?
this question asked on MSE
I worked on integral problem and I got that
$$ \int_0^1 \frac{x^n}{\ln \left(\frac{1-x}{1+x} \right) } dx=-\frac{2}{(n+1)!}\sum_{j=1}^{n+1}F(n,j) \eta'(-j)$$
where $\eta(x)$ ...
- 513
4
votes
1
answer
407
views
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In combinatorics, a well-known result is that the matrix formed by the Stirling numbers of the second kind $\left(S(n,k)\right)_{n,k\geq 0}$ and the matrix of the signed Stirling numbers of the first ...
- 151
4
votes
1
answer
385
views
Relations involving Stirling numbers of second kind
While inverting a Laplace transform using Post's inversion formula I found the following expression:
$$
\sum_{k=1}^n S^n_k \ x^k(\alpha)_k
$$
where $S^n_k$ is a Stirling number of second kind and $(\...
- 157
4
votes
1
answer
379
views
Counting permutations with a fixed number of descents and an extra condition
I am computing the volumes of certain polytopes and it turns out that knowing a "closed formula" for the following number would help a lot.
Determine the number of permutations $\sigma\in \...
- 1,889
4
votes
0
answers
312
views
Positivity of a finite sum involving Stirling numbers of the first kind
Past days I've been trying to prove that certain polynomials have positive coefficients. After a lot of thinking, I came up with a formula for each coefficient individually, and they are not that ugly....
- 1,889
4
votes
0
answers
158
views
Multiple integral evaluation involving Stirling numbers and Riemann zeta function
Hello Mathoverflow community, how are you doing? I just wanted to know if anything is known about the following integral:
$$K_n(m) = \overbrace{\int_0^1 \dots \int_0^1}^{n-\mathrm{times}} \left(-\...
- 1,549
4
votes
0
answers
578
views
A combinatorial bound involving Stirling numbers of the second type
My previous question was solved in a very elegant way, hopefully this (seemingly more complicated) case is also easy for experts.
I need the inequality
$\Big(\prod^r_{i=1}p_i\Big)\sum^n_{j=0}(-1)^j\...
- 2,232
3
votes
2
answers
1k
views
Proof of identity involving Stirling numbers of the second kind
While computing conditional expectations of certain functionals of a Poisson white noise field (details are long and probably irrelevant), I've stumbled upon the need to use the following identity ...
- 393
3
votes
1
answer
828
views
Sum of the Stirling numbers of the second kind multiplied by $k$ and falling factorials
I am looking for closed forms, or at least a good approximation for
$$f(n) = \sum_{k=1}^{k=n} \genfrac\{\}{0pt}{}{n}{k}(n)_kk$$
I know that
$$\sum_{k=1}^{k=n} \genfrac\{\}{0pt}{}{n}{k}(n)_k = n^n$$
I ...
- 33
3
votes
1
answer
586
views
Trying to prove a congruence for Stirling numbers of the second kind
This a repost of a question I asked at Stack Exchange, but I got no answer so far, so I am trying here, even though it may not suit the "research level" requirement.
Proposition: When $n$ and $m$ are ...
- 505
3
votes
1
answer
223
views
How to find the coefficient of $x^k$ in the expression $\prod_{p=2}^n (1+xp) $
I got this general formula for $ n\in N$ (I showed it here)
$$\int_0^1 \left(\frac{x}{1-x} \ln x \right)^n dx=n \sum_{p=0}^{n-1}a(n,p+1) (-1)^{n-p} \zeta(p+2)+n! $$
where $a(n,k)$ is the coefficient ...
- 513
3
votes
2
answers
463
views
Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$
Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...
- 1,101
3
votes
2
answers
403
views
Closed form for product of Stirling numbers of the second kind
What does the following expression evaluate to:
\begin{equation}
\sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix}
\end{...
- 37
3
votes
1
answer
324
views
Sum with Stirling numbers of the second kind
Let $wt(n)$ be A000120, number of $1$'s in binary expansion of $n$ (or the binary weight of $n$)
and
$$n=2^{t_1}(1+2^{t_2+1}(1+\dots(1+2^{t_{wt(n)}+1}))\dots)$$
Then we have an integer sequence given ...
- 4,948
3
votes
0
answers
89
views
Recursion for reversed rows of the A373183 using unsigned Stirling numbers of the first kind
Let $\left[{n \atop k}\right]$ be unsigned Stirling numbers of the first kind. Here
$$
\left[{n \atop k}\right] = (n-1)\left[{n-1 \atop k}\right] + \left[{n-1 \atop k-1}\right], \\
\left[{n \atop 0}\...
- 4,948
3
votes
0
answers
190
views
Stirling number, Delannoy number, and binomial coefficients in a sum
I want to compute/prove that the following sum is positive:
$$ \sum_{i = 0}^n \left[\frac{D(n - i, i)}{d} \sum_{j = m}^d s(d, j) \binom{j}{m} (d - i)^{j - m}\right] > 0
$$
where $s(d, j)$ is the ...
- 51
3
votes
0
answers
170
views
Stirling number bounds and polynomials and the Lambert $W$ function
Let $s(n,k)$ be the (signed) Stirling numbers of the first kind. The polynomials
$$L_n(x)=\sum_{j=1}^ns(n,n+1-j)\dfrac{x^j}{j!}$$
enter in the asymptotic expansion of the Lambert $W$ function, see for ...
- 13.1k
2
votes
1
answer
338
views
Simple approximation to a sum involving Stirling numbers?
I have also posted this question at https://math.stackexchange.com/questions/486917/simple-approximation-to-a-sum-involving-stirling-numbers. I have an exact answer to a problem, which is the function:...
- 23
2
votes
1
answer
222
views
A question on signed Stirling numbers of the first kind
Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by
$$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$
Question. ...
- 15.6k
2
votes
1
answer
129
views
Recursion for the sum with Stirling numbers of both kinds
Let $s(n,k)$ be a (signed) Stirling number of the first kind.
Let $n \brace k$ be a Stirling number of the second kind.
Let
$$
f(n,m,i) = (-1)^{m-i+1}\sum\limits_{j=i}^{m+1}j^n s(j,i) {m+1 \brace j}...
- 4,948
2
votes
1
answer
761
views
Prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $
For all $k,R \in \mathbb{N}$ fixed, prove that $ \sum_{i=0}^{2k}( {n+R-1\choose R+i} + (-1)^{i+1}{ n+R+i\choose R+i } )\sum_{j=0}^i {i\choose j}(-1)^j(i+1-j)^{2k}=0 $. I'm quite sure this is true but ...
- 1,109
2
votes
1
answer
345
views
Show that $\sum_{i=0}^{2k} [ {n\choose i+1} + (-1)^{i+1}{n+i+1\choose i+1} ] \sum_{j=0}^i {i\choose j}(-1)^j (i+1-j)^{2k} =0.$
Let $u(k,j) = 1$ if $j=0$, $0$ if $j > k$, or else it is $j*u(k-1,j-1) +(j+1)*u(k-1,j) $. Prove that $ \sum_{i=0}^{2k} {n \choose i+1} u(2k,i) +\sum_{i=0}^{2k} {-n-1 \choose i+1} u(2k,i)=0. $ ...
- 1,109
2
votes
1
answer
193
views
Bell polynomial with variables 1 and 0
Let $B_{n,k}(x_1,\cdots,x_{n-k+1})$ be the Bell polynomial.
If $x_1=\cdots=x_{n-k+1}=1$, we know that $B_{n,k}(x_1,\cdots,x_{n-k+1})=S(n,k)$, where $S(n,k)$ is the Stirling number of second kind.
...
- 549
2
votes
3
answers
529
views
How this expression leads to the given sequence
Here given is a sequence from OEIS.
The sequence is triangle of coefficients from fractional iteration of $e^x - 1$. Few terms are:
1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, ...
- 21
2
votes
0
answers
126
views
Generalized identity with Stirling numbers of the second kind and falling factorials
It is known that Striling numbers of the second kind satisfy the relation
$$
\sum\limits_{k=0}^{n}{n \brace k}(x)_k = x^n.
$$
where $(x)_n$ is the falling factorials such that
$$
(x)_n = x(x-1)(x-2)\...
- 4,948
2
votes
0
answers
125
views
Inequality for 2-associated Stirling numbers of the second kind
Let $S_2(n,k)$ denote the 2-associated Stirling number of the second kind for $n$ objects and $k$ blocks, with $n$ being at least two. That is, we partition $n$ labeled objects into $k$ unlabeled ...
2
votes
1
answer
145
views
Estimation of a sum involving Stirling's number of second kind and binomial coefficient
Let $S(n, j)$ be Stirling's number of second kind. Let $p\in [0,1]$ and $m \in N$.
Bound from above the following sum:
$$
\sum_{j=0}^m S(n,j) {m \choose j}\, j! \, p^j
$$
- 97
1
vote
3
answers
183
views
Evaluating a sinusoidal series
Define the sequence of functions
$$f_n(x)=\sum_{m=n}^\infty(-1)^m\frac{x^{2m}}{(2m+1)!} {m \choose n} $$
Is there a closed form expression for arbitrary $n$? It is clear that the result should assume ...
- 151
1
vote
1
answer
300
views
Proof of Stirling number symmetric formulas [closed]
I'm looking for a reference to a proof of formulas 6.26 and 6.27 in Concrete Mathematics:
$\def\sone#1#2{\left[#1\atop #2\right]}
\def\stwo#1#2{\left\{#1\atop #2\right\}}
$
$$ \stwo{n}{n-m} = \sum_k \...
- 21
1
vote
1
answer
258
views
Sum of divisors of Stirling numbers of the second kind
In this post we denote the Stirling number of the second kind as ${n\brace k}$, I add as reference the article Stirling numbers of the second kind from the encyclopedia Wikipedia. And we denote the ...
1
vote
1
answer
211
views
Finite differences of Stirling numbers
Let s(n,k) and S(n,k) denote the Stirling numbers of the first (with signs) and second kinds, respectively. Next consider the sequence |s(n+2,n)| which begins: (2,11,35,85,175,...) . Using this to ...
- 1,411