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:
