16
votes
Positivity of a finite sum involving Stirling numbers
The numbers $a_{n,m}$ are in fact the Fourier coefficients of the polynomial
$$P_n(x)=\prod_{j=1}^{n-1} \Big( \frac{nx}{2} + \frac{n}{2}-j\Big) $$
with respect to the Chebyshev measure $d\sigma:=(1-x^...
10
votes
Accepted
Some strange multinomial averaging
Denote by $f(n,m)=M(n+m,m;2)/m!$ the number of partitions of $\{1,2,\dots,n+m\}$ onto $m$ subsets of size at least 2 (observation of Darij Grinberg). Your identity rewrites as $A(n):=\sum_{j\geqslant ...
9
votes
Accepted
Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
Let $Y = \{1,\ldots, n\}$. Throughout $r \in \{1,\ldots, k\}$ will be the size of the range of a function.
The left-hand side $k^n \binom{n}{k}$ is the size of the union of the sets $\mathcal{L}_r$ ...
8
votes
Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
I have already accepted Mark Wildon's answer, but just for the reference, let me also post another proof that I found while the discussion was closed. The proof uses the following auxiliary notion ...
8
votes
Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
Given a partition $\pi=\{B_1,\dots,B_k\}$ of $[n]$ and a function
$f\colon \pi\to[n]$, define $g\colon[n]\to f(\pi)$ (the image of $f$)
by the condition $g(i)=f(B_j)$, where $i\in B_j$. When $f$ is
...
8
votes
Accepted
Divisibility of Stirling numbers
The Stirling numbers of the first kind satisfy $x^{\underline{n}} = \sum_{k=0}^n s_1(n,k)x^k$. For $n > 0$ we have $s_1(n, 0) = 0$, $s_1(n, 1) = (-1)^{n-1}(n-1)!$, $s_1(n, n) = 1$.
If $n > 1$ ...
7
votes
Accepted
Sum of the Stirling numbers of the second kind multiplied by $k$ and falling factorials
We have that $(x)_k - (x-1)_k = k (x-1)_{k-1}$. So applying the linear operator $f \mapsto xf(x) - xf(x-1)$, to the identity $$ \sum_{k=1}^{n} \genfrac\{\}{0pt}{}{n}{k}(x)_k = x^n $$ we get that $$...
6
votes
Proof of Stirling number symmetric formulas
$\def\sone#1#2{\left[#1\atop #2\right]}
\def\stwo#1#2{\left\{#1\atop #2\right\}}
$
These formulas can be proved by Lagrange interpolation, using the fact that
$\stwo{n}{n-m}$ and $\sone{n}{n-m}$ are ...
6
votes
Accepted
Proof of identity involving Stirling numbers of the second kind
You can give a short proof by interpreting the identity as an instance of inclusion-exclusion. The left hand side counts the number of ways of partitioning $S=\{1,2,\dots,k\}$ into $\ell$ parts and ...
6
votes
Proof of identity involving Stirling numbers of the second kind
The identity can be proved by equating coefficients of $z^k/k!$ in
$$ l \frac{(e^z-1)^l}{l!}= (1-e^{-z}) \frac{d\ }{dz} \frac{(e^z-1)^l}{l!}.$$
5
votes
What is this sequence?
I've got that $a_{n,h}$ is the coefficient of $x^{n-1}$ in
\begin{split}
&(-1)^{n+h+1} \frac{n!}{2\cdot (h-1)!}\frac{\log(1+x)^{h}\left(\coth(-\frac{n}2\log(1+x))-1\right)}{1+x} \\
=\ &(-1)^{n+...
5
votes
Accepted
Identity involving Stirling number of the second kind
The first formula in Section 24.1.4.I.B in Handbook of mathematical functions with formulas, graphs, and mathematical tables, Dover edition, 1965 (Library of Congress Catalog Card Number: 65.12253) by ...
4
votes
Showing this formula counts these things
Here is a proof using (formal) generating functions.
The Lah number $L(n,m+1)$
$$L(n,m+1)=\frac{n!}{(m+1)!}[x^n] \bigg(\frac{x}{1-x}\bigg)^{m+1}$$
counts the number of unordered partitions of the ...
4
votes
How to find the coefficient of $x^k$ in the expression $\prod_{p=2}^n (1+xp) $
From representation
$$\prod_{p=2}^n (1+xp) = (-x)^{n+1} (-1/x)_{n+1} (1+x)^{-1}=
\sum_{i\geq 0} s_1(n+1,i) (-x)^{n+1-i}\cdot \sum_{j\geq0} (-x)^j,
$$
it follows that the coefficient of $x^{k-1}$ in ...
3
votes
Accepted
Determinant of matrix with Stirling numbers as elements
If we take a general sequence of (unsigned) Comtet numbers of the first kind [1, 2] $$c(n, k) = e_{n-k}(\xi_1, \ldots, \xi_n)$$ then the $n \times n$ submatrix with a row offset of $k$ has determinant ...
3
votes
Singular values of Stirling numbers matrix
I will make the first attempt, though my resulting bound can certainly be improved.
I will do the $N\times N$ Stirling matrix of the second kind. We have $S_2(n,k) = \left\{n\atop k\right\}$ for $0\...
3
votes
Evaluating a sinusoidal series
Those are very close to the spherical Bessel functions of the first kind
$$f_{n}=\left(\frac{-z}{2}\right)^{n}j_{n}(z)=(-1)^{n}\frac{\sqrt{\pi}}{2}\left(\frac{z}{2}\right)^{n-\frac{1}{2}}J_{n+\frac{1}{...
2
votes
Inequality for Stirling numbers of the second kind
Let me prove a weaker inequality, the proof of which allows further improvements. Note that $S(n,k)=h_{n-k}(1,2,\dots,k)$, where $$h_t(x_1,\dots,x_k)=\sum_{a_1+\dots+a_k=t,a_i\geqslant 0} x_1^{a_1}\...
2
votes
Acyclic orientations of complete graphs in terms of Stirling numbers?
Ok, this is 6 years late, and it might just be kicking the can down the road, but: the number of acyclic orientations of a graph $G$ with $n$ vertices is given by $(-1)^n \chi_G(-1)$, where $\chi_G$ ...
2
votes
Finite differences of Stirling numbers
Let $c(n,k) = |s(n,k)| = (-1)^{n-k} s(n,k)$. It is well known that for fixed $k$, $S(n+k,n)$ and $s(n+k,n)$ are polynomials in $n$ of degree $2k$ with leading coefficient $(2k-1)!!/(2k)!$. If we ...
2
votes
Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?
Doesn't this admit the following easy argument: given an injection $f:[k] \rightarrow [n]$, let $\sigma(f): [n] \rightarrow [k]$ send $i \in [n]$ to $j \in [k]$ if $f(j)=i$ and to 1 otherwise. $\...
2
votes
Accepted
Sum of divisors of Stirling numbers of the second kind
Conjecture 2 seems to be true. If $n \geq 2$ then
$$\frac{1}{2}(k^2+k+2)k^{n-k-1}-1 \leq \left\{{n \atop k}\right\} \leq \frac{1}{2}{n \choose k} k^{n-k} < 2^n k^{n-k}. $$ (Inequalities from Here....
2
votes
Determinant of matrix with Stirling numbers as elements
I realize you've seen a solution to $\det\binom{n+i-1}j=\binom{2n-1}n$ earlier. But, I just wanted to give it a different proof, in case you encounter similar questions. The method is called Dodgson's ...
2
votes
Accepted
Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?
$R(n, k, -\tfrac k2)$ is just the central factorial number $T(n, k)$. (Given the definition of the central factorial numbers, it may be more natural to use them in your context than $R$).
Consider ...
2
votes
Accepted
Sum with Stirling numbers of the second kind
The same idea of grouping terms by the number of unit bits, as well as grouping by the value of $\mathrm{wt}(j)$ (representing $j$ via individual bits) works here:
\begin{split}
s(n,m) &= \sum_{\...
2
votes
Accepted
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 $
First off, there should be $(-1)^{i+1}$ not $(-1)^{R+i}$ (now it's corrected in the question). UPDATE. Argument below is simplified and streamlined.
The identity generalizes the previous question, ...
2
votes
Accepted
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.$
As pointed out by Ira Gessel, $u(k,j)=j!S(k+1,j+1)$. Correspondingly, the sum in question reduces to
$$f_{2k}(n) + f_{2k}(-n-1),$$
where
$$f_k(t):=\sum_{i=1}^{k+1} S(k+1,i)\frac{(t)_i}i,$$
where $(t)...
2
votes
Bell polynomial with variables 1 and 0
From the generating function:
$$\sum_{n\geq k \geq 0} B_{n,k}(x_1,\ldots,x_{n-k+1}) \frac{t^n}{n!} u^k = \exp\left( u \sum_{j=1}^\infty x_j \frac{t^j}{j!} \right)$$
it follows that
$$\sum_{n\geq k \...
2
votes
Accepted
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}$
We will prove the identity (A8) that qifeng618 alluded to. The method is called the Wilf-Zeilberger methodology. To this end, define the two functions (suppressing $x$)
$$F(n,k):=\frac{\binom{2x+1}{2k+...
2
votes
Evaluating a sinusoidal series
Letting $y:=-x^2$, we reduce the calculation to
$$g_n(y):=\sum_{m=n}^\infty \frac{y^{m-n}}{(2m+1)!}\,m(m-1)\cdots(m-(n-1)) \\
=\partial_y^n\sum_{m=0}^\infty \frac{y^m}{(2m+1)!}
=\frac12\,\partial_y^n ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
stirling-numbers × 53co.combinatorics × 37
binomial-coefficients × 10
nt.number-theory × 9
sequences-and-series × 8
reference-request × 6
divisors-multiples × 4
combinatorial-identities × 4
enumerative-combinatorics × 3
generating-functions × 3
analytic-number-theory × 2
polynomials × 2
st.statistics × 2
inequalities × 2
special-functions × 2
riemann-zeta-function × 2
power-series × 2
partitions × 2
laplace-transform × 2
pr.probability × 1
real-analysis × 1
ca.classical-analysis-and-odes × 1
integration × 1
asymptotics × 1
diophantine-equations × 1