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

0
votes
1answer
12 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
26 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
21 views

Stirling number of first kind monotone for a half

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 ...
3
votes
1answer
40 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
12 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
66 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
32 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
32 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
33 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
79 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$ ...
3
votes
2answers
41 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
17 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
39 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 = ...
2
votes
1answer
122 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
31 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
40 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
42 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 ...
0
votes
1answer
48 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
36 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
93 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
56 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, ...
2
votes
5answers
93 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
56 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 ...
1
vote
1answer
40 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
33 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
50 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
55 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
42 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: ...
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
116 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
102 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} = ...
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
110 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 ...
3
votes
5answers
111 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 ...
1
vote
1answer
69 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
66 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
71 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
49 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
182 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
67 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
74 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
68 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
49 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. ...
0
votes
1answer
30 views

Deriving a simple formula for $S(m,2)$

I need to derive a simple formula for $S(m,2)$ and these are the Stirling number of the second kind. My thinking is that we need to count the number of ways to distribute $m$ distinct objects onto ...
1
vote
1answer
41 views

Striling numbers of the first kind $S(m,m-1)$

I want to derive a formula for $S(m,m-1)$ where $S(m,n)$ is the number of ways to seat $m$ people at $n$ circular tables with at least one person at each table, The arrangements at any one ...
2
votes
1answer
46 views

How to give a combinatorial proof for this forumula

I need to give a combinatorial argument that $$S(n,m) = \sum_{i =0} ^{n-1} {n -1 \choose i} S(i,m-1)$$ Where $S(n,m)$ is the Stirling numbers of the second kind. Here is my attempt. Well first ...