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.

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 ...