All Questions
Tagged with stirling-numbers co.combinatorics
46 questions
1
vote
0
answers
33
views
Closed form for $a(2^m(2k+1))$
Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\dotsc,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
- 4,948
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
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
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
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
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
1
vote
0
answers
86
views
Closed form for the family of polynomials
Let $s(n,k)$ be a (signed) Stirling number of the first kind.
Let $R(n,x)$ be the family of polynomials such that
$$
R(2n+1,x) = xR(n,x), \\
R(2n,x) = x(R(n,x+1) - R(n, x)), \\
R(0, x) = x
$$
Let $\...
- 4,948
1
vote
0
answers
59
views
Simple recursion for the A329369 using 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 $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with ...
- 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
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
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 ...
0
votes
1
answer
368
views
Identity involving Stirling number of the second kind
I'm looking for a citable reference for the following identity involving the Stirling numbers of the second kind $S(n, k)$ stated in Equation (27): For $n \geq 2$,
$$
\sum_{m=1}^n S(n, m) (-1)^m (m-1)!...
- 58
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
7
votes
2
answers
819
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
0
votes
1
answer
403
views
Could you please confirm or deny two identities involving weighted Stirling numbers of the second kind?
In the paper [1] below, among other things, Carlitz introduced weighted Stirling numbers of the second kind $R(n,k,r)$. He also proved that the numbers $R(n,k,r)$ can be generated by
\begin{equation*}%...
- 1,101
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
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
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
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
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
1
vote
1
answer
921
views
What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?
Introduction
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
\begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...
- 4,829
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
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
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
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
0
votes
1
answer
378
views
Simplify a double summation involving binomial coeficient
$$T(N,K)=\sum_{i=2}^{K}\sum_{j=2}^{i}(-1)^{i-j}\binom{i}{j}\frac{j^{N+1}-1}{j-1}$$
Is it possible to evaluate the sum for $K=10^7$ efficiently. If we manage to remove one of the sums, it will be ...
- 221
1
vote
1
answer
516
views
Evaluation of a complete homogeneous symmetric polynomial related to Stirling number of 2nd kind
It is well known that the complete homogeneous symmetric polynomial $h_{n-k}(1,\,2,\,3, ...,\,k-1,\,k)$ equals $S(n,\,k)$ the Stirling number of the second kind. [Wikipedia]
During a research project ...
- 145
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
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
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
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
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
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
1
vote
1
answer
299
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
3
votes
1
answer
585
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
0
votes
2
answers
187
views
Combinatorial Interpretation of Generalized Stirling numbers
I know the combinatorial interpretation of first, and second order Stirling numbers (#of k cycles of n items, and #of partitions n items into k subsets). Is there an interpretation for the generalized ...
- 113
9
votes
1
answer
568
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
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
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
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
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
4
votes
1
answer
886
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
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