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^...
Pietro Majer's user avatar
  • 56.5k
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 ...
Fedor Petrov's user avatar
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$ ...
Mark Wildon's user avatar
  • 10.8k
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 ...
Filip Nikšić's user avatar
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 ...
Richard Stanley's user avatar
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$ ...
Peter Taylor's user avatar
  • 6,516
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 $$...
user41282141's user avatar
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 ...
Ira Gessel's user avatar
  • 16.2k
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 ...
Gjergji Zaimi's user avatar
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!}.$$
Ira Gessel's user avatar
  • 16.2k
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+...
Max Alekseyev's user avatar
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 ...
Iosif Pinelis's user avatar
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 ...
esg's user avatar
  • 3,150
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 ...
Max Alekseyev's user avatar
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 ...
Peter Taylor's user avatar
  • 6,516
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\...
alext87's user avatar
  • 3,167
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}{...
Buzz's user avatar
  • 1,360
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}\...
Fedor Petrov's user avatar
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$ ...
Angelo Lucia's user avatar
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 ...
Ira Gessel's user avatar
  • 16.2k
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. $\...
Nicholas Kuhn's user avatar
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....
JoshuaZ's user avatar
  • 6,090
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 ...
T. Amdeberhan's user avatar
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 ...
Peter Taylor's user avatar
  • 6,516
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_{\...
Max Alekseyev's user avatar
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, ...
Max Alekseyev's user avatar
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)...
Max Alekseyev's user avatar
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 \...
Max Alekseyev's user avatar
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+...
T. Amdeberhan's user avatar
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 ...
Iosif Pinelis's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible