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
0answers
28 views

Show $\sum_{k=0}^n b_r(n,k) = (r-1)!\frac{x^{\bar{n}}}{(x+1)^{\bar{r-1}}}$ [duplicate]

Let's define $b_r(n,k)$ as $n$-permutations with $k$ cycles where numbers $1\dots r$ belong to one cycle. I tried to first define closed form for $b_r(n,k)$. My idea: We need to put $1 \dots r$ into ...
0
votes
1answer
33 views

stirling numbers of second kind

i am new to combinatorics and just encountered stirling numbers of second kind the book i am using does not provide much info about it except number of ways of distributing "r" distinct objects ...
4
votes
0answers
104 views

Number of ways to arrange $n$ numbers based on their relative values to each other

EDIT I've found a formula to solve this question, but I don't understand the reasoning behind it. Can someone explain this formula? $s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$ $s$ being ...
2
votes
2answers
73 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
139 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
18 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
32 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
45 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
17 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
72 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
35 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
85 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
146 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
46 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
55 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
105 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
62 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
96 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
59 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
55 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
44 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
126 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
111 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
78 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
76 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
52 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
219 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
76 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 ...