There are two kinds of Stirling numbers. Stirling numbers of the first kind $[{n \atop k}]$ count the number of ways to arrange $n$ objects into $k$ cycles. Stirling numbers of the second kind $\{ {n \atop k} \}$ count the number of ways to partition a set of $n$ objects into $k$ subsets.

learn more… | top users | synonyms

2
votes
2answers
67 views

Closed form for an integral with log and power

Let $n \in \mathbb{N}$. We know that: $$\int_0^1 x^n \log(1-x) \, {\rm d}x = - \frac{\mathcal{H}_{n+1}}{n+1}$$ Now, let $m , n \in \mathbb{N}$. What can we say about the integral $$\int_0^1 x^n \...
1
vote
0answers
39 views

The logarithmic integral $\int_2^x\frac{dt}{\log t}$ and Stirling numbers of the first kind

From the generating function for the function $x/\log(1+x)$, denoting $(A_n)_{n\geq 0}$ the corresponding sequence of coefficients, by integration of the function $1/\log(t+1)$ over $ \left( 1,x-1 \...
2
votes
3answers
138 views

Expanding $\frac{\Gamma(n)}{\Gamma(n-k)}$ as a polynomial

I want to expand $\frac{\Gamma(n)}{\Gamma(n-k)}$ as a polynomial, where $\Gamma$ is the gamma function. For $k\in\mathbb{N}$, it can be "simplified" as $$\frac{\Gamma(n)}{\Gamma(n-k)}=(n-1)(n-2)(n-3)...
0
votes
1answer
15 views

Stirling Numbers of the First Kind and Permutations [closed]

How to prove that the number of $[n]$ permutations with $k$ cycles is equal with $|s(n,k)|$?
0
votes
0answers
31 views

Relationship between Riemann Zeta function and Prime zeta function

In his paper, Daniel Grunberg shows a relationship between the Stirling Numbers of the first kind and the Harmonic numbers via series of partitions (see Equation 3.1 on Page 5 in the link above). If ...
0
votes
1answer
29 views

Stirling number of first kind monotone for a half [closed]

Show that every $n>0$, there is some $m(n)$ such that $$s_{n,0}<s_{n,1}<\cdots < s_{n,m(n)}>s_{n,m(n)+1}>\cdots>s_{n,n},$$ where either $m(n)=m(n-1)$ or $m(n)=m(n-1)+1$ and $s_{...
3
votes
1answer
42 views

Combinatorial proof or meaning of the identity [duplicate]

I have to give a combinatorial proof and the meaning of the following identity. $$\sum_{k = 1}^n (-1)^k k !S(n,k) = (-1)^n,$$ where $S(n,k)$ is the Stirling number of the second kind. Could anyone ...
1
vote
1answer
14 views

Number of Blocks of Size $i$ in Set Partitions

Given a set of $N$ labeled elements $\{1, 2, ..., n\}$, we know that there are $S(N, k)$ ways to partition the elements into $k$ non-empty subsets (where $S(N, k)$ is the Stirling number of the second ...
1
vote
1answer
69 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
2
votes
1answer
34 views

Stirling numbers of first kind

Let $\sigma=\sigma_1 \sigma_2 \cdot \cdot \cdot \sigma_n \in S_n$ which means a permutation of the elements $1,2,...,n$. $\sigma_j$ is called a left-right maximum of $ \sigma$ if $\sigma_k <\...
2
votes
2answers
34 views

Interpretation of the unsigned Stirling number of the first kind.

Let $C_{2}, C_{3},\dots, C_{n}$ be the directed star graphs: the vertex set of $C_{j}$ is $\{1, 2, \dots, j\}$ and its edge set is $\{(j, i): 1\leq i <j\}$ . Let $c'(n,i)$ be the number of sets $X$ ...
1
vote
2answers
35 views

Why $S(n,k)$ is the coefficient of $x^{n-k}$ in $\prod_{t=0}^{k}(1+tx+t^2x^2+\cdots+t^nx^n)$?

$S(n,k)$ is the Stirling number of the second kind. I think an algebraic proof has something to do with the generating function. But I'm more interested in combinatorial proof. Could you please give ...
2
votes
2answers
83 views

If $S(n, n - 3) = a \binom n 4 + b \binom n 5 + c \binom n 6$, find $a, b, c$ (where $S(n, k)$ denotes a Stirling number of the second kind)

Given the identity $S(n, n - 3) = a \binom n 4 + b \binom n 5 + c \binom n 6$, find $a, b, c$. $S(n, k)$ denotes a Stirling number of the second kind, i.e., the number of ways to place $n$ labeled ...
3
votes
2answers
42 views

Showing that $x^n=\sum_{k=1}^{n}{n\brace k}(x)(x-1)\ldots (x-k+1)$ holds for all numbers, not just positive integers

I just finished proving that this statement holds for all positive integers $r$ (through a combinatorial argument) $$r^n=\sum_{k=1}^{n}{n\brace k}(r)(r-1)\ldots (r-k+1)$$ (where the curly braces ...
0
votes
0answers
19 views

Eulerian Numbers Generalization

Does anyone have a combinatorial proof for the following identity: $\sum_{i=j}^n S(n,n-j)(n-j)!(-1)^{n-j-1}=A(n,j)$. I have tried using ordered set partitions with inclusion/exclusion, but I have yet ...
3
votes
2answers
41 views

Proving that $\sum_{n=1}^{\infty}S(n,n-2)x^n = \frac{x^3(1+2x)}{(1-x)^5}$

I was wondering if anyone could give a hint on how to prove this expression, I have been stuck on it for hours. Thanks in advance! Proving that $$\sum_{n=1}^{\infty}S(n,n-2)x^n = \frac{x^3(1+2x)}{(...
2
votes
1answer
140 views

Formula for finding the nth number in this sequence: $[0, 1, 3, 11, 50, 274…]$?

The sequence here is what I have discovered to be this: https://oeis.org/A000254, which references Stirling numbers of the First Kind. The formulas provided in that link are very ambiguous with their ...
0
votes
1answer
32 views

How to solve the following limit using mathematics Stirling $\lim\limits_{n\to \infty}\frac{n!}{n^ne^{-n}\sqrt{2\pi n}}=1$

How to solve the following limit using mathematics Stirling $\lim\limits_{n\to \infty}\frac{n!}{n^ne^{-n}\sqrt{2\pi n}}$. a) $\lim\limits_{n\to \infty}\frac{n!e^n}{n^{n+1/2}}$. b) $\lim\limits_{n\to ...
1
vote
1answer
28 views

How many ways are for K people to work a one-day shift for N days so each of them works at least one day [closed]

Each person must work at least a day. Only one person can work in a given day. Example: 2 people, 3 days -> 6 -> (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1)
0
votes
1answer
42 views

Please explain the algebraic manipulations between these two formulas for Stirling numbers of the second kind

$$\begin{align}\\ S(n,r) &= \frac1{r!}\sum_{i = 0}^r (-1)^i\binom r i(r-i)^n\\ &= \frac1{r!}\sum_{i = 0}^r (-1)^{r-i}\binom r i i^n\\ \end{align}$$ I know how to derive the formula in the ...
2
votes
1answer
45 views

Solving inequalities regarding Stirling numbers

Prove that, for all integers $n \gt 1$, $$n! \lt S(2n,n) \lt (2n)!,$$ where $S(n.k)$ denotes the Stirling numbers is the number of ways of placing $n$ distinct balls into $k$ identical boxes so that ...
0
votes
1answer
52 views

set partition with constraints

The number of ways one can partition an $n$-element set into exactly $k$ subsets is described by the Stirling number of the second type. Would someone suggest some references on the problem of a set ...
1
vote
0answers
37 views

asymptotic approximation for the sum of stirling numbers of the second kind

The Stirling number of the second kind, $S(n,k)$, is defined to be the number of ways one can partition an $n$-element set into exactly $k$ subsets. The sum over the values for $k$ from 1 to $n$ ...
4
votes
0answers
100 views

Finite differences of power functions

I'm interested in finite differences, to be precise, finite differences $\Delta^n f(x)$, where $n \in \mathbb{N}$ and $f$ is a real function given by $f(x) = x^a$ for some $a \in \mathbb{R}$. I use ...
0
votes
0answers
59 views

Stirling Approximation: Finding the Error

I was looking at this post Is there a closed-form equation for $n!$? If not, why not?, and I had a question. Is there a way that we can calculate the relative error for the Stirling approximation, i.e....
2
votes
5answers
95 views

Coefficient of $x^{50}$ in the expansion of $\prod_{n=1}^{52}{(x+n)}$

Find the coefficient of $x^{50}$ in the expansion of $$\prod_{n=1}^{52}{(x+n)}$$ I can't find a way out.
1
vote
1answer
57 views

An Identity Involving Bernoulli Numbers and Stirling Numbers

I am trying to prove the following identity involving the Bernoulli numbers $B_n$: $$\sum_{i=0}^m\sum_{t=0}^{m-i}B_{2t}2^{2t}{4m+4\choose 2t,2i+1,4m-2t-2i+3}=(2m+2)\left(2^{4m+2}-{4m+2\choose 2m+1}\...
1
vote
1answer
57 views

Bijection for Rook placecement and Stirling number of 2nd kind

Say we have an nxn chessboard from which the squares below the diagonal are removed to obtain a new board $C_n$. The board $C_3$ is shown below. Let the number of ways to place k non-attacking ...
1
vote
1answer
34 views

partitioning of a set with kn members into k subsets such that each subset has n members

we know that $S(n,k)$ is the number of ways we can partition a set with $n$ members to $k$ subsets ( each subset has at least one member). imagine we have a set with $k*n$ members. we want to ...
0
votes
2answers
65 views

Understanding Stirling no of first kind

I was reading about Stirling no of the first kind, so $ \left[ \frac{n}{k} \right] $ represent no of k cycles of n items, so in $ \left[ \frac{4}{2} \right] $ there would be 11 such combinations, of ...
1
vote
1answer
53 views

Stirling number of Second kind generating function

I would like to prove that: $$f_m(x) = \dfrac{x^m}{(1-x)(1-2x)...(1-mx)}$$ Where $$f_m(x) = \sum_{n=0}^{\infty} S(n,m)x^n$$ and $S(n,m)$ is stirling number of 2nd kind Multiplying the recurrence ...
0
votes
0answers
57 views

Tail sums of Stirling numbers of first kind

Let $s(n,k)$ denote the signed Stirling numbers of first kind. Are there any identities or bounds for tail sums $$\displaystyle \sum_{j = k}^n s(n,j)$$ where $k > 2$? Standard identities are $\...
1
vote
1answer
43 views

A recursion similar to the one for Bernoulli numbers

For the Bernoulli numbers $B_m$, there is a recursion: $B_0=1$ and $\sum_{j=0}^{m-1}\binom{m+1}{j}B_j=-(m+1)B_m $ for $m\ge 1$. It is known that $B_{m}=0$ when $m\gt 1$ is odd. Now, ...
1
vote
0answers
31 views

Stirling number and cycles

I was introduced stirling number of first kind [s(n,k)] as number of ways one can arrange n people around k identical tables and permuting them. But coefficent of x^k in the polynomial: x(x+1)(x+2).......
0
votes
1answer
54 views

What's the relation between Stirling numbers and the generating functions?

I just started studying higher combinatorics, but until now in the combinatorial sense I had only seen binomial theorem and coefficients. Therefore, I'm having a lot of difficulty in grasping the ...
1
vote
1answer
124 views

Combinatorial interpretation of explicit formula for Stirling numbers of the second kind

I see that the below formula is the explicit formula of the Stirling numbers of the second kind. I know that the Stirling number of the second kind is the number of ways to partition set of $n$ ...
1
vote
1answer
110 views

Identities about Bell numbers

The $n$-th Bell number equals the number of set partitions of $\{1,2,\dots,n\}$. We set $B_0 := 1$. Prove the following identities: $$B_n = \sum_{k=0}^{n}S_{n,k} \qquad and \qquad B_{n+1} = \sum_{k=0}^...
0
votes
1answer
61 views

Cyclic representation of permutations and Stirling numbers

I have been studying combinatorics lately, and I came across this cyclic representation of permutations and Stirling numbers. I understood some stuff, but other stuff are still unclear to me. For ...
0
votes
2answers
115 views

Number of injective and surjective mappings $f : A \rightarrow B$ for two sets?

Let $A, B$ be two finite sets with $|A| = n$ and $|B| = k$. How many injective mappings $f : A \rightarrow B$ are there? Furthermore, show that the number of surjective mappings $f: A \rightarrow B$ ...
3
votes
5answers
113 views

Prove the identity $x^n = \sum^{n}_{k=0}S_{n,k}(x)_k$

Prove the following identity: $$x^n = \sum^{n}_{k=0}S_{n,k}(x)_k \space \space \space\space\space\space\space\space\space\space\space\space\space (n \geq 0)$$. We are talking clearly about Stirling ...
1
vote
1answer
73 views

Closed form of to calculate variation of Pascal's triangle

So if you have Pascal's triangle, I know you can calculate any value in closed form. 1 1 1 1 2 1 1 3 3 1 .... If we let ...
2
votes
2answers
67 views

Show that $S(n ,k)$…

Show that $$S(n,k) = \sum_{m = k-1}^{n-1} {n-1 \choose m} S(m,k-1) $$ -I was having trouble with this proof in class and my professor suggested to look at it as another proof of the following ...
0
votes
1answer
73 views

Let $s(n,k)$ denote the signless Stirling numbers of the first kind. Prove that…

Let $s(n,k)$ denote the signless Stirling numbers of the first kind. Prove that: $$s(n,2) = (n-1)!(1 + \frac{1}{2} + \frac{1}{3} +...+ \frac{1}{n-1})$$ -I haven't dealt with Taylor series expansion ...
1
vote
1answer
51 views

Prove by induction that $S(n,3) > 3^{n-2}$ for all $n≥6$

Prove by induction that $S(n,3) > 3^{n-2}$ for all $n≥6$ I have done the base case for this problem, using $n=6$ as my base case: $$S(6,3) > 3^{6-2}$$ $$S(6,3) > 81$$ -I am brand new to ...
0
votes
2answers
211 views

Stirling number proof, proving that $s(n, n-2) = {n\choose3} + 3{n\choose4}$

Let $s(n,k)$ denote the unsigned Stirling numbers of the first kind. Prove that $$s(n, n-2) = {n\choose3} + 3{n\choose4} $$ -I had a similar question for the $s(n, n-1)$ case, but unsure of how to ...
1
vote
0answers
69 views

Let $s(n,k)$ denote the unsigned Stirling numbers of the first kind. Prove that…

Let $s(n,k)$ denote the unsigned Stirling numbers of the first kind. Prove that $$s(n, n-1) = {n\choose2} $$ -I am new to Stirling numbers, and looked up some definitions regarding it. I know that ...
0
votes
0answers
75 views

How to relate even and odd number of cycles of permutations of [n] to c(n,k)

I am seeking to show that for $n > 1$, that the number of permutations of $[n]$ with an even number of cycles is equal to the number of permutations with an odd number of cycles using only ...
0
votes
0answers
32 views

An incomplete sum of Stirling numbers of the second kind

Let $n, k, w \geq 1$ be integers with $w < n$ small relative to $n$. Consider the sum $$ \dfrac{1}{n^k} \sum_{j = n - w}^{n-1} j! S(k, j) {n \choose j}, $$ where the $S(k,j)$ are Stirling numbers ...
3
votes
1answer
71 views

A sum involving Stirling numbers of the second kind

For $p \in (0,1)$ and integers $n,k \geq 1$, what is known of the following sum? $$ \sum_{j=1}^k j!S(k, j){n \choose j} p^j. $$ Can we simplify it? Edit: The question in this post: (A combinatorial ...
1
vote
1answer
51 views

A combinatorial sum and identity involving Stirling numbers of the second kind

Let $n, k \geq 1$. Let $a(j), 1\leq j \leq k$, be a sequence of real numbers. Consider the sum $$ \sum_{j=1}^k j! S(k, j) {n \choose j} a(j), $$ where $S(k,j)$ are Stirling numbers of the second kind. ...