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
45 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
82 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
49 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
26 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
29 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
58 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
36 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
49 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
39 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
22 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
51 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
94 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
88 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
51 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
81 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
110 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
54 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 ...
1
vote
2answers
61 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
65 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
42 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
1answer
88 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
58 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
56 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
27 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
53 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
43 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
28 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
38 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
40 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 ...
4
votes
1answer
69 views

An identity on Stirling number of the first and the second kind.

I have a difficulty in proving the identity $\sum_{i=k}^n S(n+1,i+1)s(i,k) = \binom{n}{k}$ where $s(n,k)$ is the stirling number of the first kind and $S(n,k)$ is the stirling number of the second ...
3
votes
2answers
47 views

Mathematical induction and Stirling numbers

I want to find a formula for the following series $$ \sum_{i=1}^m {m \choose i} i! S(n,i)$$ Where $S(n,m)$ is the Stirling numbers of the second kind. Now I evaluated this series at $m=1,2,3$ for ...
3
votes
0answers
60 views

Factorial of a large number and Stirling approximation

I'm trying to approximate the factorial of a large number with large precision. I know one can use the the Stirling approximation to do that with the formula: $$\sqrt{2\pi x} ...
1
vote
1answer
46 views

Stirling’s approximation and Big O

How to prove that $2n \choose n$ = $\frac{2^{2n}}{\sqrt{\pi n}}(1 + O(1/n))$ using Stirling’s approximation? I know how to prove that $2n \choose n$ = $\frac{2^{2n}}{\sqrt{\pi n}}$ but I am having ...
0
votes
1answer
151 views

How many ways to distribute n distinct objects into r groups when only 1 group is allowed to be empty?

This one is hurting my brain. How many ways are there to distribute n distinct objects into r distinct groups of arbitrary sizes, when only one particular group is allowed (but not required) to be ...
0
votes
1answer
79 views

Identity involving Stirling numbers of second kind $S(n,k)$ and $k$-compositions of $n$

I'm trying prove the following identity $$S(n,k)=\sum_{(\alpha_1,\cdots,\alpha_k)}1^{\alpha_1-1}2^{\alpha_2-1}\cdots k^{\alpha_k-1},$$ where the sum ranges over the $k$-compositions of $n$. I ...
1
vote
1answer
156 views

Generating function of a polynomial sequence

Using Wolfram Alpha, I find that the first 6 members $p_j(x)$, $0\leq j\leq 5$, of the polynomial sequence happen to be the first 6 non-zero coefficients of the Maclaurin series of ...
0
votes
0answers
29 views

Find the limit using Stirlings Approximation $\lim \limits_{n\to\infty}(\frac{n^n}{n!})$ [duplicate]

Stirlings Apprx according to my textbook: $$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n \left(1+\frac{1}{12n}+\epsilon(n)\right)$$ where $\epsilon(n)$ is $O(1/n^2)$ Not sure how to do ...
3
votes
0answers
35 views

What do the Stirling numbers of the first kind have to do with polylogarithms?

On a whim, I had decided to look into ways of evaluating series of the form $$\sum_{n\ge1}\frac{1}{n^k2^n}$$ which I learned has a more general form in terms of polylogarithms: ...
1
vote
2answers
64 views

Why is $\binom{2n}{n} \asymp \Theta \big(\frac{2^{2n}}{\sqrt{n}}\big)$?

I saw this statement : $$\binom{2n}{n} \asymp \Theta \bigg(\frac{2^{2n}}{\sqrt{n}}\bigg) \asymp \Theta\bigg(\frac{4^n}{\sqrt{n}}\bigg)$$ How did we go from the first statement to the second? I tried ...
1
vote
0answers
81 views

Stirling numbers of the second kind, general formula

I found out about the Stirling numbers (first and second) when I studied a way to smooth the factorial function. This is the way I want to define them. Approach the factorial $(1+n)!$ as a product and ...
0
votes
1answer
35 views

Simplify the formula for the number of distributions leaving none of the $n$ cells empty

I'd like to help with the following problem: $$ \binom{x}{r-1} + \binom{x}{r} = \binom{x+1}{r} \tag{8.6}\label{8.6} $$ 7. Let $A(r, n)$ be the number of distributions leaving none of the n cells ...
0
votes
0answers
66 views

Finding closed form for this summation

recently i have beeen asking alot of questions about summations, But this one is actually quite interesting: $$ \sum_{j=k}^n j! 2^{k-2j} \left({2j-k-1 \choose j-1} - {2j-k-1 \choose j}\right){n \brack ...
1
vote
0answers
85 views

Stirling number Combinatorics. Summation .

$$ \sum_{k=0}^n \left\{ {n\atop k} \right\} *(x)_k = x^n $$ is well known . What if the k-th term of LHS summation is divided by $q^k$ where $q$ is some positive constant, What about $$ ...
5
votes
1answer
129 views

Stirling transform of $(k-1)!$

While reading about combinatorial mathematics, I found this article about the Stirling transform which caught my attention. So, if I wanted to find the Stirling transform of, for instance, $(k-1)!$, ...
0
votes
1answer
43 views

How to show that the displaying numbers of a onto function is k!S(n,k)?

Let it be $A$,$B$ sets that $|A|$=$n$, $|B|$=$k$ and $|A|>|B|$. How to show that the displaying numbers of an onto function $f$:$A$ $\rightarrow$ $B$ is: $\begin{Bmatrix} n \\ k\end{Bmatrix}$$k!$ ...
0
votes
1answer
41 views

Counting functions and stirling numbers

Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}. |A|=m, |B|=n. where k $ \le n, k \le m $ |S|=$ {n \choose k} $ S(m,k) k!. where S(m,k) are the striling numbers of the second kind. What I can't ...
1
vote
1answer
115 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
1
vote
1answer
49 views

Falling power of a sum in terms of falling powers of the terms

I am trying to come up with an expression for $(x+y)^{\underline{n}}$ in terms of $x^{\underline{r}}$ and $y^{\underline{r}}$. I tried for $n=2$ and $n=3$ and it looks like binomial expansion holds, ...
0
votes
1answer
78 views

Some proofs regarding Stirling numbers

I would like you to help me to prove two proofs correlated with Stirling numbers (the first one includes Stirling numbers of the second kind and the second one I guess Stirling numbers of the second ...
4
votes
4answers
117 views

Proof of an equation involving Stirling numbers of the second kind

I found this equation involving Stirling numbers of the second kind on Math World: $$\sum\limits_{m=1}^n (-1)^m(m-1)!\,S(n,m)=0 \ .$$ However, I do not know why this is true. I am looking for a proof ...