Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [stirling-numbers]

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.

1
vote
2answers
24 views

Counting Surjections with Inclusion-Exclusion

Compute the number of surjective functions $f : [10] → [5]$ using the I/E principle. With Stirling numbers of the second kind, we can obtain the answer with the following way $S(10,5)5!$. How I can ...
4
votes
1answer
38 views

Show that $p_{n} \geq 1- \exp{(-n(n-1)/730)}$

On the issue of the birthday paradox,Let $p_{n}$ be the probability that in a class of $n$ at least $2$ have a their birthdays on the same day (exclude $29$ Feb). Use the inequality $1-x \leq e^{-x}$ ...
1
vote
1answer
72 views

How many partitions of a set $S$ into $K$ different subsets of size $k_1, k_2, k_3,\cdots, k_K$?

I want to code a program to solve a variation of the salesman problem but I am encountering some difficulties. The idea is that I have $S$ points (customers) I'd wish to visit and I always depart and ...
0
votes
0answers
56 views

How to write $\left(x\frac{d}{dx}\right)^n $ in terms of Stirling numbers of the first kind?

How to write $\left(x\frac{d}{dx}\right)^n $ in terms of Stirling numbers of the first kind $\begin{bmatrix} n \\ m \end{bmatrix}$? I know that we can write the above in terms of Stirling numbers of ...
6
votes
1answer
211 views

Closed form for product of Stirling numbers of the second kind

What does the following expression evaluate to: \begin{equation} \sum\limits_{k=1}^n \dbinom{n}{k} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \end{...
1
vote
0answers
53 views

Product of Stirling numbers of second kind

What does the following expression evaluate to: \begin{equation} k! \begin{Bmatrix} n \\ k \end{Bmatrix} \cdot k! \begin{Bmatrix} n \\ k \end{Bmatrix} \end{equation} We know that $k! \begin{Bmatrix}...
0
votes
1answer
50 views

Summation of Stirling numbers of second kind

Evaluate: \begin{equation} n^{n-\ell} \cdot \sum\limits_{k=1}^\ell \dbinom{n}{k} k! \begin{Bmatrix} \ell \\ k \end{Bmatrix} \end{equation} I used my primitive math skills along with the some ...
0
votes
1answer
28 views

Proving Stirling numbers

a) Prove $\sum_{k=0}^{n} s(n,k) = n!$, for all $n\in \mathbb{N}$. So my idea was to start with induction over $n\\$. Base case: $n=1$ $\sum_{k=0}^{1}s(1,k)=s(1,0)+s(1,1) = 0+1=1 =1!$ Inductive ...
3
votes
2answers
99 views

Summation of: (binomial coefficients * Stirling numbers of the second kind)

Problem: Simplify the following equation: \begin{equation} \sum\limits_{k=1}^n \dbinom{n}{k} \begin{Bmatrix} n\\ k \end{Bmatrix} k! \end{equation} A solution: I am aware of the following relation: \...
1
vote
3answers
51 views

How can we write the expansion of $\frac{e^t(e^t-1)^{n-1}}{(e^t+1)^{n+1}}.$

How can we write the expansion of $$\frac{e^t(e^t-1)^{n-1}}{(e^t+1)^{n+1}}.$$ I know that $$\frac{1}{(e^t+1)^{n+1}}=\sum_{k=0}^\infty (-1)^k \binom{n+k}{k} e^{kt}.$$ Could you please give me an ...
0
votes
1answer
40 views

how does sqrt(n)/n equal 1/sqrt(n)?

I'm working through a probability book where the following is stated (chapter 3): Definition 3.3 Let $a_n$ and $b_n$ be two sequences of numbers. We say $a_n$ is asymptotically equal to $b_n$, ...
4
votes
3answers
57 views

An identity involving binomial coefficients and Stirling numbers of both kinds

I calculated, using Mathematica, that for $4\leq k \leq 100$, $$ \sum_{j=k}^{2k} \sum_{i=j+1-k}^j (-1)^j 2^{j-i} \binom{2k}{j} S(j,i) s(i,j+1-k) = 0,$$ where $s(i,j)$ and $S(i,j)$ are Stirling numbers ...
2
votes
0answers
34 views

Orthogonality of Stirling numbers - simplify a variant thereof

Stirling numbers satisfy the following orthogonality condition. For $k<n$: $$ \sum_{i=k}^n S(n,i) s(i,k)=0,$$ where $s(i,k)$ and $S(n,i)$ are Stirling numbers of the first and second kind, ...
2
votes
1answer
59 views

References/Proof of the conjectured identity for the Stirling permutation number $\left\{{n\atop n-k}\right\}$

While working with a combinatorics problem, I conjectured that $$ \left\{{n \atop n-k }\right\}=\sum_{p=0}^{k-1}\bigg\langle\!\!\bigg\langle{k\atop k-1-p}\bigg\rangle\!\!\bigg\rangle \binom{n+p}{2k}, ...
0
votes
1answer
70 views

Recurrence relation for Stirling numbers of the second kind

I was solving a recurrence relation for Stirling numbers of the second kind: $$S(n,k)=kS(n-1,k)+S(n-1,k-1)$$ For $k=1$ or $k=n\ $ $ \ S(n,k)=1$ For $k=0$ or $k>n\ $ $\ S(n,k)=0$ Substitution ...
0
votes
1answer
41 views

Recursion $I_{n+1} = I_n + nI_{n-1}$ for the amount $I_n$ of the involutions in $S_n$

A permutation $\pi \in S_n$ is an involution, when $\pi^2 = \text{id}$. How can one show for the amount $I_n$ of the involutions in $S_n$ the following recursion: $$I_{n+1} = I_n + nI_{n-1}$$ ...
3
votes
2answers
69 views

Where can I find a proof, that $s(n+1,k+1) = \sum_{i = 0}^{n} \binom{i}{k}s(n,i)$?

In our Combinatorics Script it is written, that $$s_{n+1,k+1} = \sum_{i = 0}^{n} \binom{i}{k}s_{n,i}$$ for $n,k \in \mathbb{N}$. The problem is that I can't find a combinatorial proof for that, not ...
2
votes
4answers
180 views

Number of ways to divide n people into k groups with at least 2 people in each group

I'm trying to figure out the number of ways to divide n people into k groups with at least 2 people in each group. Should I first decide a recurrence relation of the number? I don't know how I could ...
0
votes
0answers
28 views

Proof Stirling equality

Proof that $k^n = \sum_{j=1}^{k}\binom{k}{j}j!S(n,j)$ To justify this last equality you have to consider, firstly, that if $X$ and $Y$ are two sets with $n$ and $k$ elements, respectively, then ...
2
votes
0answers
39 views

Stirling number congruence $S\left(n, \frac{p-1}{2}\right) \pmod{p}$

For $p$ prime, is there a simple expansion for the Stirling number of the second kind $S(n,k)$, of the form $S\left(n,\frac{p-1}{2}\right) \pmod{p}$? I tried using the explicit expansion $$\left( \...
0
votes
0answers
32 views

Generating function for Stirling numbers

I was searching for generating function for Stirling numbers. I found this link:- Generating function with Stirling's numbers of the second kind It says it's "very easy", but I wasn't unable to ...
2
votes
2answers
40 views

Why is $S_{n,3} = \frac{1}{6}(3^n - 3\cdot2^n+3)$? (Stirling)

Why is $S_{n,3} = \frac{1}{6}(3^n - 3\cdot2^n+3)$? I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$ Where we know $S(n,2)=2S(n-1,2)+1$ We can also see the latter recurrence leads to $S(n,2)=2^{n-1}-1$ So ...
1
vote
1answer
63 views

Find an explicit formula (as explicit as possible) for $a_k$

Let $a_k$ be defined as follows: $$(1+x)^n = \sum_{k=0}^na_k(x)_k$$ where $(x)_k = x(x-1)(x-2)\dots(x-k+1)$. Find a formula that describes $a_k$ as explicitly as possible, in terms of a famous number ...
0
votes
1answer
28 views

Sum involving Stirling's numbers of the second kind

I was reading one book about basic probability theory and came across one problem that caught my attention. Problem description So in the end there is a sum of the form: $\sum_{i=0}^{n} (-1)^{i}\...
1
vote
1answer
40 views

Stirling numbers of the second kind - proof 2

For a fixed integer $k$, how would I prove that $\sum_{n\ge k} \left\{n \atop k \right\} \frac{x^n}{n!}=\frac{1}{k!}(e^x -1)^k $ where $\left\{n \atop k\right\} = k\left\{n-1 \atop k\right\}+\left\{...
1
vote
1answer
47 views

Stirling numbers of the second kind - proof

For a fixed integer k, how would I prove that $$\sum_{n\ge k} \left\{n \atop k\right\}x^n= \frac{x^k}{(1-x)(1-2x)...(1-kx)}.$$ where $\left\{n \atop k\right\}=k\left\{n-1 \atop k\right\}+\left\{n-1 \...
0
votes
1answer
35 views

In how many different ways can 50 children be distributed in 5 identical classrooms

This problem is solved using Stirling numbers of the second kind : We can have empty classrooms If no classroom is empty we get $S(50,5)$ If one classroom is empty we get $ {5}\choose{4 } $ $ S(50,...
2
votes
1answer
48 views

Stirling Numbers of second kind defined in terms of coefficients

Prove that $t^n = \sum_{k=1}^n S(n,k)t^{\underline k}$ where $t^{\underline k}$ denotes the $k$-th falling power $t(t-1)(t-2)\ldots(t-k+1)$ of$~t$. I know that we'll have to use the recurrence ...
1
vote
2answers
108 views

Is there an intuitive explanation for the occurrence of e and pi in Stirling's approximation? - $n!\approx \sqrt{2\pi n} (n/e)^n$

Is there an intuitive explanation for the occurrence of e and pi in Stirling's approximation? $$n!\approx \frac{n^n}{e^n}\sqrt{2\pi n}$$ Any help would be much appreciated.
0
votes
2answers
54 views

Partial sum Stirling number of the first kind with factorial and exponential

I am hoping to compute a closed, or at least more readily computable, form of $$ \frac{1}{n!} \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} k! \ x^k $$ where the brackets represent the unsigned ...
2
votes
0answers
40 views

Stirling numbers Sum

Let $$ a_n(i,j)=\sum_{k=\max(i,j)}^{n}s(n,k) S(k,i) S(k,j), $$ here $s, S$ are the Stirling numbers of the first and second kind. I want to simplify the expression. So far I have got the following \...
4
votes
0answers
63 views

Closed form from recurrence

We have $a(0)=a(1)=1$, $$a(n)=(-1)^{n-1}+2\sum\limits_{k=1}^{n-1}\binom{n}{k}(-1)^{n-k-1}a(k)$$ $$1,1,3,13,75,541,4683,\cdots$$ which has nice closed forms, ex. $$a(n)=\sum\limits_{k=0}^{n}k!{n\brace ...
0
votes
1answer
37 views

How to find a numerical approximation of this sum.

I need to find a good approximation of $S_n$ for big n's. $S_n = \sum_{i=0}^n \frac{n!}{i!(n-i)!}{2^{-n}}\log_2\frac {n!}{i!(n-i)}.$ I've computed this sum using Python on $1\leqslant n\leqslant500$ ...
0
votes
0answers
46 views

Stirling number of the second kind solution from another recurrence

I have been trying to work out this strling number problem using some other recurrence which I had worked on before $P_{n,k}=1 + P_{n-1,k-1}+ P_{n-1,k}$. One solution was... $$P_{n, k}=\sum_{j=1}^{k}{...
4
votes
2answers
126 views

On Stirling Number

Let $H(n,k)$ be the number of sequences $b_1,b_2, \ldots, b_n$ such: that the largest element is $k$, all numbers $1,2,\ldots,k$ do occur, and the first occurrence of $i$ occurs before the first ...
3
votes
2answers
135 views

Rising Factorial and Stirling number of the 1st kind

Is it true that $$(x+1)^{\bar{n}}= \sum_{k \ge 0} \sum _{i=0}^{n} {i \choose k}s_{n,i}\,\,x^k \,\,\,\,?$$ where $s_{n,i}$ is the Stirling number of the first kind and the $\bar{n}$ denote rising ...
3
votes
1answer
107 views

Number of ways to cover a discrete set of $n$ elements into $p$ subsets with $q$ overlaps

I am looking for the general expression for the number of ways to cover a set of $n$ elements into $p$ non-empty subsets sharing exactly $q$ elements (overlaps). As an example, if $n=3$, one way to ...
1
vote
0answers
52 views

A $p$-congruence involving both kinds of Stirling numbers.

Let $g,i,k,n$ be non-negative integers, $p$ a prime number and ${n\brack {k}}$ (resp. ${n\brace k}$) be the Stirling numbers of first (resp. second) kind, such that: $$ \sum_{k\ge0} {{n}\brack {k}}x^k ...
-2
votes
1answer
91 views

Approximation for $n!$

One may notice, $$\displaystyle \sum_{k=1}^n \log k=\log n!$$ Applying Integral test for convergence one can obtain, $$\log \left[\dfrac{e^2}{4}\cdot\left(\dfrac{n}{e}\right)^n\right] \le \...
3
votes
1answer
83 views

Find a generating function for product of Stirling numbers.

What is a close form of the series $$ G_{i,j}(z)=\sum_{p=0}^\infty S(p,i) S(p,j) z^p? $$ Here $S(*,*)$ is the Stirling numbers of the second kind. For $i=1$, since $S(p,1)=1$ the result is well-known ...
1
vote
1answer
50 views

Prove the identity with Stirling numbers.

For arbitrary integer $m, t, s<n$ prove the identity $$ \sum_{i=s+1}^{n}(i!)^2 \left\{ {n \atop i}\right\} \left\{ {m \atop i}\right\} \binom{s}{i}\binom{t}{i}=0, $$ here $\displaystyle \left\{ {...
3
votes
2answers
111 views

Can we provide a good estimation for $(n!)!$?

I was thinking about this $$(n!)!$$ for $n\in\mathbb{N}$. I wanted to find a suitable approximation, or in any case a very good estimation for this. My first idea was to use Stirling ...
5
votes
0answers
77 views

On diophantine equations involving Stirling numbers of the second kind I: the equation ${m\brace k}-{n\brace k}=z^k$ for fixed integers $k\geq 3$

I would like to know the solutions of next diophantine equation(s) involving the sequence of Stirling numbers of second kind ${r\brace s}$, for $1\leq s\leq r$. To create my variant I was inspired in ...
2
votes
1answer
57 views

Stirling Numbers of the Second Kind but for Rising Factorials

We know that, for instance, $$r^3=Ar(r-1)(r-2)+Br(r-1)+Cr+D$$ which can also be written as $$r^3=Ar^\underline{3}+Br^\underline{2}+Cr^\underline{1}+Dr^\underline{0}$$ where $A,B,C,D$ are Stirling ...
1
vote
2answers
546 views

Proving $S(n,n-2) = \frac{n(n-1)(n-2)(3n-5)}{24}.$

I have to prove $$S(n,n-2) = \frac{n(n-1)(n-2)(3n-5)}{24},$$ for Stirling numbers of the second kind. I want to show it via induction on $n$ as he did on this problem: Induction with Stirling ...
1
vote
0answers
40 views

Arithmetic properties of the sequence of Stirling numbers of second kind: a first encounter

In this post I ask two questions in the spirit to explore arithmetic properties of the sequence of Stirling numbers of second kind ${n\brace k}$, for $1\leq k\leq n$. I am inspired in page 198 of [1], ...
1
vote
1answer
64 views

Stirling Formula and random walk

Let $p \in (0,1)$, $N \in \mathbb{N}$ and $X_{1}, ..., X_{N}$ a family of independent random variables with $\mathbb{P}(X_{k}=1)=p, \mathbb{P}(X_{k}=-1)=(1-p)$ for all $k \in \{1, ..., N\}$. It is $S_{...
1
vote
2answers
70 views

Closed form for $\sum\limits_{k=0}^{b}k^na^k$

We can be sure that for $a>1$ $$\sum\limits_{k=1}^{\infty}(-k)^na^{-k}+\sum\limits_{k=0}^{b}k^na^k=a^b\sum\limits_{m=0}^{n}\binom{n}{m}b^{n-m}\sum\limits_{k=0}^{\infty}(-k)^ma^{-k}$$ where $$\sum\...
0
votes
1answer
77 views

What is the relationship between sums of powers of $n$ and the stirling numbers?

Consider the following matrix where the rows are coefficients of sums of powers of $n$: $$\left( \begin{array}{cccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ ...
1
vote
1answer
39 views

Stirling numbers of the second kind for small numbers of partition

I try to do part b of the question below in a manner similar to part a, but still get stuck. Any hints? My attempt: