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 ...
- 109k
10
votes
Accepted
What is the formula for $\mathcal P_{n}^{k} (a_{1}, a_{2}, ...)$, defined by Peter Luschny?
$P_n$ is given as $$P_n(f) = \sum_{\lambda \,\vdash\, n} (-1)^{\lambda_1} \prod \binom{\lambda_j}{\lambda_{j+1}} f_{j}^{\lambda_j}$$ where
the sum is over partitions $\lambda = \lambda_1 \ge \...
- 7,226
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$ ...
- 11.2k
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 ...
- 483
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
...
- 50.8k
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,226
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 $$...
- 193
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 ...
- 85.6k
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!}.$$
- 17k
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+...
- 34.4k
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 ...
- 128k
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 ...
- 3,255
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 ...
- 34.4k
4
votes
Accepted
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In umbral notation and maneuvers, it's quite simple. With an obvious change of notation, let the Stirling polynomials of the first kind (a binomial Sheffer sequence of polynomials in the hybrid umbral-...
- 10.5k
3
votes
Counting permutations with a fixed number of descents and an extra condition
This question requires a refinement of Eulerian numbers. Namely, let $A_{n,k,\ell}$ be the number of permutations of order $n$ with $k$ descents and ending in element $\ell$. Under subtracting each ...
- 34.4k
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 ...
- 7,226
3
votes
Closed form for product of Stirling numbers of the second kind
We have
\begin{split}
\sum_{k=0}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} &= n!^2[x^ny^n] \sum_{k=0}^n \binom{n}{k} ((e^x-1)(e^y-...
- 34.4k
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,217
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}{...
- 1,422
3
votes
Accepted
Recursion for the sum with Stirling numbers of both kinds
Noticing that $j^n = n![x^n]\ e^{jx}$ and $\left\{m+1\atop j\right\}=(m+1)![y^{m+1}]\ \frac{(e^y-1)^j}{j!}$, and using e.g.f. for Stirling numbers of first kind, we have
$$f(n,m,i) = (-1)^{m-i+1} \...
- 34.4k
3
votes
Accepted
how to prove identity for nth derivative of $(\text{arctanh}(x))^j$?
The derivative of the arctanh can be evaluated in terms of the Stirling numbers by following the suggestion of Tyma Gaidash.
Start from the generating function of the Stirling numbers of the first ...
- 188k
3
votes
Accepted
A question on signed Stirling numbers of the first kind
There is some $N(k, p)$ such that $n \ge N(k, p) \implies s(n, k) \equiv 0 \pmod p$. Proof is straightforward by fixing $p$ and using induction on $k$ via the recurrence $$s(n, k) = s(n-1, k-1) - (n-1)...
- 7,226
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}\...
- 109k
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$ ...
- 399
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 ...
- 17k
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. $\...
- 11.2k
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....
- 7,059
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 ...
- 43.2k
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 ...
- 7,226
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_{\...
- 34.4k
Only top scored, non community-wiki answers of a minimum length are eligible