Questions tagged [stirling-numbers]

There are two kinds of Stirling numbers. Stirling numbers of the first kind ${n\brack k}$ count the number of ways to arrange $n$ objects into $k$ cycles. Stirling numbers of the second kind ${n\brace 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
0 answers
23 views

Stirling number expressed as a polynomial

I need to solve this problem : Let $p$ be an odd number. Show that there exist a polynomial $Q_p$ such that for every natural number $n$, $S_p(n) = Q_p\left(\frac{n(n+1)}{2}\right)$ I tried to solve ...
user avatar
  • 13
3 votes
2 answers
55 views

Proving an identity relating the number of linearly ordered partitions to Stirling numbers

For $n,k\in N_0$, let $L(n,k)$ be the number of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly ordered subsets. I want to prove that for $n,k\in N_0$, $L(n,k)=\sum_{i=0}^nc(n,...
user avatar
3 votes
1 answer
76 views

Inequality involving Stirling numbers of the first kind

For every $n\geq1$, there is some $f(n)$ such that for the Stirling numbers of the first kind we have: $c(n,0)<c(n,1)<...<c(n,f(n)-1)\leq c(n,f(n))>c(n,f(n)+1)>...>c(n,n)$ Moreover, $...
user avatar
  • 61
0 votes
0 answers
43 views

Cycles in stirling cycle numbers example

I was reading about Stirling cycle numbers which count the permutations of $n$ objects that have just $k$ cycles. An example I read mentioned the $6$ permutations of $3$ objects are classified as: $1$ ...
user avatar
  • 1,507
4 votes
1 answer
92 views

proof sum of power using Stirling number

question is prove $$ 1^{k} + 2^{k} + 3^{k} + \dots + n^{k} = \sum_{i=1}^{n} S(k,i) \cdot i! \cdot {{n+1}\choose{i+1}} $$ In my opinion, LHS means number of functions from X to Y (X has 'k' element and ...
user avatar
  • 53
0 votes
0 answers
40 views

Finding the number of ways of posting six letters in three letter boxes such that no letter box remains empty.

Find the number of ways of posting six letters in three letter boxes such that no letter box remains empty. This question already has answers here. But my doubt is in the following method. $$^6C_3\...
user avatar
  • 5,236
2 votes
0 answers
51 views

Even generating function with Stirling numbers of the second kind

Is there a known closed form for the following generating function? $$ \sum_{n=0}^{\infty}\sum_{k=0}^{n} \frac{S(n, k)}{(2n) !}x^{2n}y^k $$ If we had $n!$ at the denominator instead, this would simply ...
user avatar
1 vote
0 answers
46 views

Finding sum of Stirling numbers (signed) of the first kind $\sum_{k=0}^n s(n,k)$

Compute $\sum_{k=0}^n s(n,k)=\sum_{k=0}^n (-1)^{n-k}{n\brack k}$. From definition, it's clear than the sum of the unsigned Stirling numbers is: $$\sum_{k=0}^n {n\brack k}=n!$$ But I'm stucked at $\...
user avatar
1 vote
1 answer
52 views

How would you use Stirling numbers to partition a n unique objects, into m unique subsets, with minimum cardinality of 2 for each subset?

For example, how would one go about partitioning 10 numbered balls into 4 numbered boxes, such that each box contains at least 2 balls?
user avatar
1 vote
0 answers
34 views

Is there a recurrence in the lower index of the Stirling numbers of the lower kind? [closed]

Is there a recurrence that relates $S(n,k)$, the Stirling number of the second kind, to $S(n,k-1)$ so that you can compute $S(n,k)$ without changing the upper index?
user avatar
1 vote
1 answer
75 views

prove that $\sum_{k=0}^{n}S(n,k)(x)_k=x^n$

my attempt: assume there are a teacher decided to buy $n$ different types of chocolate and present it as a reward to the students who will give a correct answer to one of the questions. The number of ...
user avatar
2 votes
1 answer
94 views

Coupon Collector's Problem and Stirling numbers of the second kind: rationale

I have basic notions of probability and combinatorics, but I hadn't heard of Stirling numbers (or I forgot them 😐) until I recently fell into the Coupon Collector's Problem, and into the formula for ...
user avatar
1 vote
1 answer
60 views

range of r parameter of second kind r-Stirling numbers

My question is about second kind r-Stirling numbers. Here are two important papers about it. https://www.sciencedirect.com/science/article/pii/0012365X84901614#:~:text=The%20r%2DStirling%20numbers%E2%...
user avatar
  • 411
0 votes
1 answer
40 views

In how many different ways can persons A,B,C,D and E be seated around two equal round tables so that no table remains empty?

Persons A and E never sit at the same table. I'm guessing you could describe this in terms of Stirling numbers but I'm basically lost from there. My guess is that it's s(5,2) - the number of ...
user avatar
1 vote
1 answer
37 views

Limit involving Stirling numbers of the first kind

This question arose whilst working on this problem. Let $\ \left[{n\atop k}\right]\ $ denote the $\ (n,k)-$th Stirling number of the first kind. Define $$ f(n) = \left[{n\atop 1}\right] r\ +\ \left[{n\...
user avatar
0 votes
1 answer
57 views

Evaluating $\lim_{n\to\infty}\frac{1}{n+1}(\omega+\nu)^{(n+1)}z^\nu{_2F_1}(1,\omega+\nu+1;n+2;1-z)$

I recently found a proof for the following sum \begin{align*} S_n & =\sum_{k=0}^n\mathcal S_n^{(k)}(\Phi(z,-k,\omega)-z^\nu\Phi(z,-k,\omega+\nu))\\ & =\frac{1}{n+1}(\omega+\nu)^{(n+1)}z^\nu{...
user avatar
0 votes
0 answers
25 views

How do you convert negative integer powers to falling powers?

Is there a systematic way to convert $x^{-n}$ to falling powers for positive $n$? i.e. something like Stirling numbers, but that works when the exponent is negative.
user avatar
1 vote
1 answer
63 views

Proof/disproof of conjecture involving noncentral Stirling numbers of the second kind

I have a conjecture I am looking at involving the noncentral Stirling numbers of the second kind (for explanation of these numbers, see e.g., Koutras 1982). I'm having some difficulty proving it. I'...
user avatar
  • 3,858
0 votes
1 answer
119 views

Formula for Stirling numbers expressed with Bernoulli numbers?

Is there a formula which expresses any of the Stirling numbers (1st or 2nd kind) in terms of the Bernoulli numbers? For example, here is the reverse $$ B_k=\sum_{m=0}^{k} (-1)^m \frac{m!}{m+1}\sigma(k,...
user avatar
1 vote
1 answer
68 views

Line up objects in each box after using Stirling number of second kind?

If I have n distinct objects and k identical boxes, I can use Stirling number of second kind to distribute them in every posible way so that every box contains atleast one object. I would like to know ...
user avatar
0 votes
0 answers
56 views

What is $\lim_{t \to 0} \left[ {k \atop t} \right] \zeta(t+1) $?

As per this question, I'm trying to evaluate $$\sum_{k=2}^{\infty} \big{(} \zeta(n)^{2}-1 \big{)} = -\sum_{m=2}^{\infty} \frac{H_{-\frac{1}{m}}}{m}. $$ Here, $H_{x}$ is a generalized Harmonic number. ...
user avatar
  • 5,027
0 votes
1 answer
49 views

Combinatorial interpretation of an identity for expressing Stirling number of the second kind using binomial coefficients

Consider the identities as follows (Graham, Knuth, and Patashnik, Concrete Mathematics, Sec.6.2, p.271), $${x\brace x-2}={x+1\choose4}+2{x\choose 4}$$ and $${x\brace x-3}={x+2\choose6}+8{x+1\choose6}+...
user avatar
  • 604
0 votes
1 answer
58 views

Stirling Numbers of the Second Kind: Combinatorial Proof

Prove that $$1!\cdot S(n, 1) + 2!\cdot S(n, 2) + \cdots + k!\cdot S(n,k) = k^n,$$ where $k!\cdot S(n,k)$ represents the number of ways to place $n$ distinct objects into $k$ distinct boxes. Answer: ...
user avatar
  • 233
1 vote
1 answer
53 views

Order of central moments for Binomial distribution

Suppose $X\sim \operatorname{Bin}(n,p_n)$ (binomial distribution) with $p_n\to 0$ and $np_n\to \infty$. Then $$\limsup_{n\to\infty} \frac{\mathbb{E}\left[(X-np_n)^{2k}\right]}{(np_n)^k}<\infty, \...
user avatar
  • 513
1 vote
1 answer
54 views

At an event , If there are m actors, n singers and r tables , find the number of ways you can place the guests. (tables are alike)

So the question asks us to find the total arrangements possible given the no. of singers, actors and tables given the fact that - A table can have either only singers or only actors, not both. No ...
user avatar
2 votes
1 answer
198 views

Find closed formula for the exponential generating function of sequence counting permutations with 2 cycles.

Find a closed formula for the exponential generating function of $\{c(n,2)\}_{n\geq2}$, that is the sequence counting permutations of length $n$ that consist of $2$ cycles. My approach: The ...
user avatar
  • 121
1 vote
1 answer
70 views

definition of stirling numbers

Here is a definition without partition about Stirling numbers of second kind. "Let $S(n,k)$ be Stirling numbers of second kind. $1 \leq k \leq n$, and let $k$ and $n$ be positive integers. Let $h(...
user avatar
  • 411
1 vote
1 answer
43 views

A calculation about the sum of the product of Binomial and Stirling numbers of the first kind

I have came to a calculation about the sum of the product of Binomial and Stirling first numbers as following $$ \sum_{i=0}^{2k-j}\binom{2k}{i}(-1)^{i}s(2k-i,2k-i-j)~\text{for}~j=0,1,2,\ldots,k-1, ~\...
user avatar
1 vote
1 answer
61 views

Alternating sum of numbers of surjective functions

Let $S(n,k)$ denote the number of surjective functions from $\lbrace1,2,...,n\rbrace$ onto $\lbrace1,2,...,k\rbrace$. I am sure that $$S(n,n) - S(n,n-1) + S(n,n-2) - ... +(-1)^{n-1}S(n,1) = 1$$ Have ...
user avatar
0 votes
1 answer
44 views

Inequality with Stirling numbers of second kind

I have to prove that, $\forall n\geq 1$, $\forall 1\leq k\leq n$, $$ \frac{k^{n}}{k^{k}}\leq S(n,k)\leq \frac{k^{n}}{k!} $$ The second inequality, is quite obvious for me, as $k!\cdot S(n,k)$ is the ...
user avatar
1 vote
1 answer
34 views

How to relate the number of all applications $X\to Y$ with the Stirling numbers of the second kind?

I am studying Stirling numbers of the second kind, and I have just saw why $S(n,k)=\frac{1}{k!}\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{n}$ (knowing that $\sum_{j=0}^{k-1}(-1)^{j}{k\choose j}(k-j)^{...
user avatar
1 vote
2 answers
66 views

Does the (Stirling number of the second kind) equality ${2n\brace 2} = 2^{2n-1}-1$ hold?

I filled in from the definition of a Stirling number of the second kind that the following holds. $${2n\brace 2} = \frac{1}{2} \sum_{i=0}^{2} (-1)^i \binom{2}{i} (2-i)^{2n}$$ And I've visually ...
user avatar
  • 1,306
2 votes
2 answers
78 views

How to show this identity $\prod_{q=1}^k\frac{1}{1-qz}=\sum_{j=1}^{k}jz\prod_{q=1}^j\frac{1}{1-qz}+1$ avoiding a proof by induction

When looking at a nice problem regarding Stirling numbers of the second kind a challenge was to show the validity of \begin{align*} \color{blue}{\prod_{q=1}^k\frac{1}{1-qz}=\sum_{j=1}^kjz\prod_{q=1}^j\...
user avatar
2 votes
2 answers
86 views

Prove that $\left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}}$

Question I want to prove the following well known expression for Stirling Numbers of the Second Kind: $$ \left\{{n+k+1}\atop{k}\right\}=\sum_{i=1}^{k}{i\left\{{n+i}\atop{i}\right\}} $$ My Solution ...
user avatar
1 vote
1 answer
76 views

Prove that $\left\{{n+1}\atop{k+1}\right\}=\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}}$

Question I want to prove the following well known expression for Stirling Numbers of the Second Kind: $$ \left\{{n+1}\atop{k+1}\right\}=\sum_{i=k}^{n}{\left(k+1\right)^{n-i}\left\{{i}\atop{k}\right\}} ...
user avatar
6 votes
1 answer
140 views

How to pronounce Stirling Numbers of Second Kind ${n\brace k}$?

The Stirling Numbers of the Second Kind, ${n\brace k}$, count the number of ways to partition an $n$-element set into $k$ unlabeled non-empty parts and are rather useful for several introductory ...
user avatar
  • 71.2k
0 votes
2 answers
50 views

Stirling numbers of the first kind explicit product in reverse for $|s(n,k)|$?

I'm trying to find an explicit number theory definition of the Stirling numbers of the first kind in reverse as $|s(n,k)|$ not $|s(n,n-k)|$, not the way it's usually written. Here is the typical ...
user avatar
2 votes
0 answers
29 views

Distributing balls into bins for large numbers: approximating probabilities

Distributing $n$ balls into $m$ bins with $n > m$, I want to calculate the probability that at least one box will be empty. If I'm not mistaken, that should be $$p_{m} = 1 - \frac{m! S_n^{(m)}}{m^n}...
user avatar
0 votes
1 answer
98 views

Number of surjections and generating function

knowing that the number of surjections $N_m\to N_n$ is (using the principle of inclusion exclusion): $\displaystyle\sum_{i=0}^n (-1)^i\binom{n}{i} (n-i)^m$ furthermore, we know the connection with ...
user avatar
1 vote
1 answer
113 views

A formula for $1^m+2^m+3^m+\ldots+n^m$ using binomial coefficients [duplicate]

It is known that $$ \sum_{k=1}^{n}k^1=\binom{n+1}{2} $$ and $$ \sum_{k=1}^{n}k^2=\binom{n+1}{2}+2\binom{n+1}{3} $$ Is there a formula for $$ \sum_{k=1}^{n}k^m, $$ where $m$ is a positive integers, ...
user avatar
  • 4,316
4 votes
2 answers
105 views

Approximation of Stirling numbers of the second kind ${2n \brace n}$

I want an approximation of ${2n \brace n}$ as $n\to\infty$, also ${\cdot\brace\cdot }$ is the Stirling numbers of the second kind. Right now, I know an evaluation \begin{equation} {2n \brace n}=O\left(...
user avatar
1 vote
1 answer
88 views

Why is the following not $S(n,3)$ where $S(n,k)$ is a Stirling number of the second kind? (almost solved)

In an attempt to relate the number of partitions of integers to that of partitions of distincts objects I stumbled, in the particular case of $k:=3$, on the following sum $$\sum_{\genfrac{}{}{0pt}{1}{...
user avatar
  • 2,955
1 vote
0 answers
51 views

Can I make this combinatorial proof work?

I'm trying to come up with a combinatorial proof that $$x^{\overline{n}} = \sum_{k = 0}^n s(n, k)x^k$$ where $s(n,k)$ is the stirling number of the first kind. Now, $x^{\overline{n}}$ counts the ...
user avatar
1 vote
2 answers
187 views

Combinatorial arguments for two stirling numbers

I'm trying to use combinatorial arguments to find simple formulas for $\begin{Bmatrix} n\\ 2 \end{Bmatrix}$ and $\begin{Bmatrix} n\\ n-2 \end{Bmatrix}$ I've used combinatorial arguments to prove ...
user avatar
  • 795
2 votes
3 answers
106 views

What's a formal definition of cycles that will allow me to prove this identity?

On page 261 of chapter 6 in Concrete Mathematics, the authors gesture towards the following proof of the identity $$\sum_{k = 0}^n \left[\begin{array}{l} n \\ k \end{array}\right] = n!$$ where the $\...
user avatar
1 vote
2 answers
291 views

Discrete mathematics - ternary strings.

Let n be a natural number, n≥3. A ternary string is a sequence of n symbols that has some of the digits 0, 1, 2. In other words, a ternary string is a n-permutation with a repetion of the set {∞⋅0,∞⋅1,...
user avatar
  • 33
2 votes
1 answer
106 views

Ordinary Generating Function For the Unsigned Stirling numbers of the First Kind

On Wikipedia Here, the exponential generating function $$\sum_{n=k}^{\infty}{(-1)^{n-k}{n\brack k}\frac{z^n}{n!}}=\frac{1}{k!}(\log(1+z))^k$$ is given, where ${n\brack k}$ is the unsigned Stirling ...
user avatar
  • 176
0 votes
0 answers
63 views

Number of equivalence relations by using Stirling number of the second kind

I am using bell number to find the number of equivalence relations. While doing so i used the general formula for Stirling number of the second kind $$S(n,k)=\frac{1}{k!}\sum_{i=0}^k (-1)^i \binom{k}{...
user avatar
  • 125
0 votes
1 answer
110 views

Expected number of cycles in random permutations

Draw at random a permutation $\pi$ in the set of permutations of $n$ elements, $S_n$, with probability, $$ P(\pi)= \frac{N^{L(\pi)}}{ \sum_{\pi \in S_n} N^{L(\pi)} }, $$ where $ L(\pi)$ is the number ...
user avatar
0 votes
0 answers
46 views

Summation ofProduct of r-Stirling numbers of the second kind

I would like to simplify this block \begin{equation} \sum_{k=2}^{m-1}\binom{m}{k}S(k+1,3)S_{3}(m-k+3,1+3) \qquad \qquad (1) \end{equation} where, $$ n\in \mathbb {N} $$ and \begin{equation} S(k+1,3)...
user avatar

1
2 3 4 5
13