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.
0
votes
1answer
23 views
$\sum\binom{n}{a_1}\prod\limits_{p=2}^{k}\binom{n-a_{p-1}}{a_p-a_{p-1}}=k!{n+1\brace k+1}$
We have
$$\sum\limits_{0\leqslant a_1<a_2<\cdots<a_k<n}\binom{n}{a_1}\prod\limits_{p=2}^{k}\binom{n-a_{p-1}}{a_p-a_{p-1}}=k!{n+1\brace k+1}$$
where instead of $\{a_1,a_2,\cdots,a_k\}$ we ...
4
votes
3answers
91 views
Stirling numbers of second kind, but no two adjacent numbers in same part.
Update: The problem has been solved. @Phicar and I individually give two transformation from $h\rightarrow S$ and $S\rightarrow h$, and they are inverse of each other. Any other explanation or ...
1
vote
1answer
34 views
Stirling Number 1st kind in polynomial expression
I came across the following proofwiki page: https://proofwiki.org/wiki/Definition:Stirling_Numbers_of_the_First_Kind/Signed
In definition 2, author states that:
Signed Stirling numbers of the ...
0
votes
2answers
20 views
Stirling Number Generating Function Relationship
In "Generatingfunctionology" by Herbert Wilf, there is a section where he derives explicit formulas for Stirling numbers. (Please see images below).
I'm wondering how he arrives at the relationship ...
1
vote
2answers
76 views
Explicit formulas for Stirling numbers of second kind
I have seen some recursive formulas for Stirling I and II kind but I am especially interested in explicit formulas.
I was thinking and get:
$$ \left\{ {m \atop n} \right\} = \sum_{k_i>0 \wedge ...
0
votes
0answers
35 views
Distribute m=17 cards to n=7 entities
Every entity must receive at least 2 cards and all cards have to be distributed. Only the cards and not the entities are distinguishable. My approach was as follows:
Since every entity has to receive ...
5
votes
1answer
106 views
Pretty $p^2$-congruences involving Stirling numbers of the both kinds
Let $p$ an odd 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 = \prod_{j=0}^{n-1}(x+j)$$
$$ ...
0
votes
2answers
47 views
How many equivalence relations on S have exactly 3 equivalence classes?
Let S = {1,2,3,4,5,6,7,8}. How many equivalence relations on S have exactly 3 equivalence classes?
The only idea I have is to use the formula for Stirling numbers of the second kind, which seems like ...
1
vote
1answer
28 views
Formula for the total number of partitions
I am trying to tackle the following exercise from
Norman L. Biggs, Discrete Mathematics , p.91
Suppose we are given a partition of the $n$-set $X$ into $k$ parts, and we delete the part containing ...
2
votes
1answer
79 views
General formula for $\dfrac{d^n}{dx^n}e^{f(x)}$ vs. integer composition or Stirling Numbers 2nd kind
Differentiating $\dfrac{d^n}{dx^n}e^{f(x)}$, the coefficients look rather familiar (ignoring the $n!$ in front) for each combination of derivatives of various orders:
$$\begin{array}{c}
1 \\
1 & 1 ...
1
vote
1answer
27 views
How do I notate a polynomial with Stirling coefficients and what properties do I need to prove it?
I have a group of polynomials where each term increases in degree and has coefficients that appear as Stirling numbers of the second kind:
$1: 1 \\
2: 1+x \\
3: 1+3x+x^2 \\
4: 1+7x+6x^2+x^3 \\
5: 1+...
1
vote
2answers
74 views
Computing $S(n,3)$, Stirling number of 2nd kind
To compute this I used the fact that $S(n,2) = 2^{n-1}-1$ and used the recurrence relation $S(n,k) = kS(n-1,k) + S(n-1,k-1)$, and used induction to get that $S(n,3)=\dfrac{3^{n-1}+1}{2}-2^{n-1}$.
But ...
0
votes
0answers
29 views
A Sum Involving the Stirling Numbers of the Second Kind
This problem is proposed for programming purpose. I'd like to ask how to calculate $\sum_{a=2}^{M}\sum_{n=a}^{N}a!{n\brace a}$ modulo $p$ efficiently, where $M \leq 10^6$, $M \leq N<10^{10}$, $p$ ...
1
vote
2answers
49 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
41 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
81 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
225 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
56 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
58 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
117 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
52 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
51 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
60 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
37 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
63 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
90 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
47 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
71 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
306 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
29 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
46 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
38 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
42 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
64 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
53 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
45 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
62 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
36 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
53 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
113 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
68 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
44 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
66 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
42 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
50 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
130 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
156 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
109 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 ...
