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$ non-empty subsets.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Closed-form solution to the recurrence

Context In a game players are divided into two groups, A and B. Players in A know identities of all players whereas players in B only know the identity of himself. In the first round Group A ...
4
votes
1answer
48 views

Proof of identity relating Prime-counting function and Stirling numbers of the second kind

In his famous 1973 paper Gallagher showed that the distribution of prime numbers in short intervals tends to a Poisson distribution. To do it he uses in one step: $$\sum_{n \leq N}(\pi (n+h)-\pi(n))^{...
-1
votes
1answer
64 views

How to determine the a(n) of the following sequence ? $ 6,48,384,3280,30420…$ [closed]

I hope to determine a formula for the nth term of the following sequence : $$ \textbf{6 , 48 , 384, 3280, 30420, 307188, ...}$$ I noticed that \begin{align*} 6 &= 3 \times 1 \times \tfrac{4}{2} \\ ...
0
votes
0answers
28 views

What kind of terms dominate this summation? : Specific question

Here is my summation term. $\Sigma_{l=0}^{np}\langle e_{1}|f_{1}\rangle^{l}\langle e_{1}|f_{2}\rangle^{np-l} \langle e_{2}|f_{1}\rangle^{nq-l} \langle e_{2}|f_{1}\rangle^{n(1-q)-np+l} {nq\choose l} {n(...
0
votes
0answers
67 views

A $partition$ of a number $n$ is defined as an unordered tuple of positive integers $a_1,a_2,\dots,a_k$ such that $n = a_1 + a_2+\dots+a_k$.

A partition of a number $n$ is defined as an unordered tuple of positive integers $a_1,a_2,\dots,a_k$ such that $n = a_1 + a_2+\dots+a_k$. Note that values can repeat within the tuple. For example, (1,...
0
votes
1answer
51 views

How to prove the following facts of Stirling Numbers (2) [closed]

Here is the Question :- Given r,n∈Z with 0≤n≤r , the Stirling number S(r,n) of the second kind is defined as the number of ways in distributing r distinct objects into n boxes such that no box is ...
0
votes
1answer
47 views

How to prove the following facts of Stirling Numbers (1) [closed]

Here is the Question :- Given $r,n \in \mathbb{Z}$ with $0 \leq n \leq r$ , the Stirling number $s(r,n)$ of the first kind is defined as the number of ways to arrange $r$ distinct objects into $n$ ...
1
vote
2answers
43 views

An approximation of the ordered Bell numbers

So my problem is the following: I have $n$ ice-cream flavors and I must rank them, allowing that I can place more than one flavor in some ranks. So for example if I have 4 flavors, I can put in the ...
0
votes
1answer
24 views

Range of $m,n$ in $\sum_{j=0}^{m}{m\brace j}\binom{n}{j}j!=n^{m}$

A well-known identity related to Stirling numbers of the second kind states: $$\sum_{j=0}^{m}(-1)^j{m\brace j}j!=(-1)^m$$ I know the formula: $$\sum_{j=0}^{m}{m\brace j}\binom{n}{j}j!=n^{m}\tag{I}$$ ...
2
votes
1answer
53 views

Proof of $\sum_{n\ge0}^{ }n^{m}z^{n}=\sum_{j=0}^{m}{m+1\brace j+1}\frac{\left(-1\right)^{m-j}j!}{\left(1-z\right)^{j+1}}$

Wikipedia states that Stirling numbers of the second kind satisfy the following relation: $$\sum_{n\ge0}^{ }n^{m}z^{n}=\sum_{j=0}^{m}{m+1\brace j+1}\frac{\left(-1\right)^{m-j}j!}{\left(1-z\right)^{...
2
votes
3answers
88 views

Combinatorial proof of ${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$

It's known that Stirling numbers of the second kind satisfy the following relation: $${n\brace k}= \frac{k^{n}}{k!}-\sum_{r=1}^{k-1}\frac{ {n\brace r}}{\left(k-r\right)!}$$ However I have not ever ...
0
votes
0answers
22 views

How do I derive the formula S(G,k)=S(G+e,k)+S(G/e,k)?

I found this in a paper from Auburn University and they just state it but do not derive it. I would like to know how to derive it. I'm fairly certian that e is edges in the graph G, but I don't know ...
0
votes
1answer
49 views

Use combinatorial reasoning to show that Stirling number

Use combinatorial reasoning to show $\begin{Bmatrix} n\\ n-2 \end{Bmatrix} = \binom{n}{3} + 3\binom{n}{4}.$ The Stirling number is the number of permutation of n into $n-2$ parts.
1
vote
1answer
47 views

Stirling Numbers of first kind $s(n,k)$

Stirling Numbers, $s(n,k)$ are defined as the permutation of $[n]$={$1,2,...,n$} of having $k$ cycles, why is it/how can you prove $s(n,1)=(n-1)!$ and $s(n,n)=1$ and $s(n,k)=s(n-1,k-1)+(n-1)s(n-1,...
1
vote
0answers
58 views

A summation involving stirling numbers of the first kind

I'm finding a probability related to graphs (It's $\frac{Q(n)}{n}$). $$Q(n) = 1 + \frac{n-1}{n} + \frac{(n-1)(n-2)}{n^2}+ ... + \frac{(n-1)(n-2)...1}{n^{n-1}} = \sum_{k=1}^n \frac{n!}{(n-k)! n^k}$$ ...
1
vote
0answers
55 views

Stirling number of the first kind summation

I'm calculating some probability and confronted such an exotic summation: $$ \sum_{k=1}^{n} \begin{bmatrix} k+c\\ k \end{bmatrix} $$ where $\begin{bmatrix} k+c\\ k \end{bmatrix}$ is unsigned ...
2
votes
1answer
84 views

Stirling number of the first kind Identities

Question: Let ${h_n}$, from n=0 to n=infinity, denote any sequence of real numbers. For n = 0,1,2, ... and using $g_n= \sum_{k=0}^n S(n, k)*h_k$, where $S(n, k)$ is a Stirling number of the second ...
2
votes
1answer
27 views

Proving Assymptotic tight bound on $\lg(n!)$ is equivalent to $n\lg(n)$ without using Stirling's Approximation.

So, how I did it is by expanding $f(n)=\lg(n!)$ to first \begin{align} \lg(n!) &= \lg(n(n-1)(n-2)\cdot\ldots\cdot2\cdot 1)\\ &=\lg(n)+\lg(n-1)+\lg(n-2)+...+\lg(1)\\ n\lg(n) &\geq \lg(...
1
vote
1answer
21 views

Stirling number identity related to balls and boxes

I recently posted a question regarding placing $6$ distinguishable balls into $4$ indistinguishable boxes. In summary I feel somewhat certain that the solution to that question is $$\sum_{r=0}^{4}S(6,...
0
votes
2answers
71 views

Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$ [closed]

Prove $6\begin{Bmatrix} n\\ 3 \end{Bmatrix}+6\begin{Bmatrix} n\\ 2 \end{Bmatrix}+ 3\begin{Bmatrix} n\\ 1 \end{Bmatrix}=3^n$ I need a combinatorial proof of this identity. The right hand side must be ...
0
votes
2answers
27 views

Stirling numbers of the second kind formulae

We want to determine the number of ways that 10 distinct pieces of candy can be placed into 2 identical bags with each bag getting at least 1 piece. As we know the answer is $S(10,2)$, where $S$ ...
3
votes
1answer
64 views

Provide a combinatoric proofs of following identities (Stirling numbers)

a) $$\sum_{k=1}^{m}k {n+k\brace k} ={ n+m+1 \brace m}$$ It seems that we are supposed to check the number of divisions of $[n+k]$ into $k$ sets and then pick one of those sets. However, I'm at a loss ...
3
votes
1answer
157 views

Finite sums involving Stirling number of first kind

I would like simplify the following doble sum $$ \sum_{k=m}^n\,s(n,k)\,x^k\sum_{s=m}^k\,(-1)^{k+s}\,s(k,s)\begin{pmatrix}s\\m\end{pmatrix}\,y^{s-m}$$ with $s(n,k)$ the Stirling numbers of first ...
0
votes
1answer
36 views

Sum with Stirling numbers of first kind

I have problems with proving this equation: $$ \sum_{k=0}^n s_1(n,k)\cdot 2^{k} = (n+1)!$$ where $s_1(n,k)$ is the Stirling number of first kind.
3
votes
1answer
73 views

A three-parameters identity involving Stirling numbers of both kinds

Let $n, m, k $ be three natural numbers, ${n \brack k}$ and ${n \brace k}$ the Stirling numbers of first and second kind respectively. We have: $$ \tag{*} {n-1 \choose m}{n-m \brack k}= \sum_i (-...
0
votes
0answers
22 views

Finite sum involving Stirling number of first kind and Pochhammer symbol

I'm trying to find a closed form of $$\sum_{m=0}^n\,s(n,k)\,(\alpha)_m\,z^m$$ where $(\alpha)_m$ means pochhammer symbol and $s(n,k)$ are the Stirling numbers of first kind. I've had a look in ...
0
votes
1answer
38 views

Prove $\text{L}(n,k)\le{n\brace k}$ without induction

Define $$ \text{L}(n,k):=\frac{1}{2}\left(k^{2}+k+2\right)k^{\left(n-k-1\right)}-1$$ Then :$$\text{L}(n,k)\le{n\brace k}$$ Where $1 \le k \le n-1$ and $n \in \mathbb N_{\ge2}$ and ${n\brace k}$ ...
1
vote
1answer
58 views

Given a set of $n$ elements, how many partitions in $k $ subsets have at least size $x$.

How do you do fellow Stackers, recently I've beeen studying combinatorics and surprise surprise, failing at it. My questions is probably pretty simple, in fact, it can be considered a duplicate of [...
0
votes
0answers
38 views

Prove $\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$

How it can be shown that: $$\left(m-2\right){2m-3\brace m-1}>m{2m-3\brace m}$$ For $ m>2$. Where ${n\brace m}$ denotes Stirling numbers of the second kind. Using the recurrence ${n\brace m}={...
1
vote
1answer
76 views

Prove the lower bound $\binom{n}{k-1} \le {n\brace k}$

A famous and simple lower bounds for Stirling numbers of the second kind is as follows: $$\binom{n}{k-1} \le {n\brace k}$$ I tried to prove that using the relation $${n\brace k}=\frac{1}{k!}\sum_{j=...
0
votes
1answer
45 views

is $K^N$ an upper bound for $S_2(N,K)$ Where $S_2$ denotes the Stirling Number of the Second Kind?

My thoughts: Consider an array of $N$ characters, $C$, such that C= [$c_1$, $c_2$, ..., $c_N$]. Now, the structure of a $K$-partition of $C$ can be represented as a corresponding array of $K$ ...
0
votes
2answers
56 views

A problem in Brualdi's Combinatorics about computing Stirling Numbers

I am studying Introductory Combinatorics from Richard Brualdi but I am unable to think about a solution for this problem in exercises. Problem is: Compute the Stirling number of second kind $...
1
vote
1answer
38 views

A summation with Stirling numbers of the Second kind

Can the following sum be evaluated? $$\sum\limits_{k=1}^{n-1}\binom{n}{n-k}\left( n-k\right) !S\left( n,n-k\right) \left( \frac{k-1}{k}\right) ^{k}$$ where $S(n,m)$ is the Stirling number of the ...
0
votes
1answer
46 views

Unable to prove a relation which Stirling Numbers of 2nd kind must satisfy

I am trying exercises of Richard Brualdi Introductory Combinatorics and I am unable to think about this question in exercise of Chapter 8 . Prove that Stirling numbers of 2nd Kind satisfy S(n, n-2) = ...
0
votes
1answer
103 views

Summation of signless Stirling numbers of first kind

This is from Discrete mathematics and its application by Kenneth H Rosen The signless Stirling number of the first kind $c(n,k)$ where $k$ and $n$ are integers with $1\leq k\leq n$, equals the ...
4
votes
1answer
38 views

Dividing 12 people into any number of groups, such that person A and B are not in the same group?

In how many ways can you divide 12 people into any number of groups, such that person A and B are not in the same group? I am trying to solve this question and so far I am thinking of this in terms ...
14
votes
2answers
333 views

A Vandermonde Identity for Stirling Numbers?

I'm facing the problem of trying to express a quantity in the simplest possible way (it is, using the least possible number of sum symbols). $$ \sum_{j=0}^{n} \sum_{\ell=0}^m \frac{1}{j!}\binom{b+j}{...
1
vote
1answer
38 views

What is the reasoning behind Stirling number $S(n,2)$?

The answer that was given in class was $(2^n -2)/2$. I think it's trying to use the theorem that the number of $k$-digit strings that can be formed over $n$ element set is $n^k$. Or, I think it ...
3
votes
2answers
79 views

Combinatorial proof for Touchard's congruence

Bell number denoted $B_n$ is the number of ways to partition a set with cardinality $n$ into $k$ indistinguishable sets , where $0\le k\le n$ It's known that Bell numbers obey Touchard's Congruence ...
0
votes
0answers
30 views

A formula for $r$-fold sums of powers of integers

Let $m \geq 1$ be a fixed integer. There are classical well-known formulas for the sum $\sum\limits_{k=0}^{n} k^{m}$ involving Bernoulli polynomials and/or Stirling numbers. For instance I am ...
1
vote
1answer
47 views

Distribution into different groups if blank groups are not permissible

The number of ways in which $n$ different things can be distributed into $r$ different groups if blank groups are not allowed is: $r^n-{}^rC_1(r-1)^n+{}^rC_2(r-2)^n-\cdots+(-1)^{r-1}.{}^rC_{r-1}$ The ...
2
votes
2answers
68 views

Stirling Numbers of the Second Kind Proof

Prove that \begin{align*} \sum_{n=1}^\infty S(n,n-2)x^n=\dfrac{x^3(1+2x)}{(1-x)^5} \end{align*} My guess is that I have to take the LHS and simply it, as well as take the RHS and simplify ...
3
votes
1answer
76 views

integral representation for $\sum_{k=0}^{x}k^{p}$

How the following integral representation can be derived? $$\sum_{k=0}^{x}k^{p}=\int_{0}^{x+1}B_{p}\left(t\right)dt=\frac{B_{p+1}\left(x+1\right)-B_{p+1}}{p+1}$$ I know Faulhaber's formula which is ...
1
vote
0answers
53 views

Asymptotic Expansion of MGF of squared Poisson - Touchard Polynomials and Second stirling number

What is the asymptotic expansion of the following expression as $\theta \to 0^+$? Alternatively, what is the asymptotic expansion of the MGF $M(\theta)$ of the squared Poisson(1) as $\theta \to 0^+$? ...
1
vote
2answers
85 views

Number of ways to partition a set with cardinality at least $k$ into $k$ nonempty subsets.

How many ways are there to partition an $n$-element set where $n \geq k$ into $k$ nonempty subsets? According to the formula provided here, the answer is $\dfrac{1}{k!}\displaystyle\sum_{i=0}^k (-1)^...
1
vote
1answer
55 views

generating function for Bell polynomial

How it can be proved that : $$\sum_{n=0}^{ ∞}B_{n}\left(x\right)\frac{t^{n}}{n!}=e^{x\left(e^{t}-1\right)}$$ Where $B_n$ is the $n^{th}$ complete Bell polynomial. I know that $$\sum_{n=k}^{∞ }S\left(...
2
votes
1answer
127 views

Formula for computing the coefficients of Bell polynomial

I'm working on Bell polynomials and have learned some of its properties, but I've never seen any formula for calculating the coefficient in Bell polynomials. My trying to find these coefficients was ...
1
vote
1answer
93 views

Balls into Bins: probability that b bins have at least m balls

Consider the standard balls into bins problem, with $n$ balls uniformly randomly thrown into $k$ bins. What is the probability that exactly $b$ bins have at least $m$ balls? This is a generalization ...
0
votes
1answer
52 views

I'm confused about the identity of Stirling numbers: $s(n,k) = k!S(n,k)$

I'm a little bit confused about this identity between Stirling numbers of the first and second kind, because from it you can derive that: $s(n,k) = k!S(n,k) = k!(S(n-1,k-1) + kS(n-1,k)) = k(k-1)!S(n-...
3
votes
2answers
67 views

Stirling numbers: Show that $S(n+1, r)=rS(n, r)+S(n, r-1)$.

I know that the Stirling numbers of the second kind are the number of partitions of an $n$-set with $r$ non-empty parts, and that they can be denoted $S(n,r)$. How would I then show $S(n+1, r)=rS(n, ...

1
2 3 4 5
10