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
0answers
22 views

Isolate term in combinatoric inequality

I am trying to isolate $\Delta k$ to the left of the expression below to find for which values of $\Delta k$ the expression is positive. I have an intuition that it should be true for all $\Delta k>...
1
vote
2answers
39 views

Unsigned Stirling number of the first kind summation

I'm solving a question and I confronted with this summation: $A_n = \sum _{k=1}^n\left(n-k\right)\begin{bmatrix} n\\ k \end{bmatrix}$ Where$ \begin{bmatrix} n\\ k \end{bmatrix}$ is unsigned Stirling ...
-6
votes
0answers
22 views

Evaluating limits by using Stirling's approximation [closed]

Let $a_1,a_2,a_3,\dots,a_n,\dots$ be a sequence of real numbers with $a_{n+1}=a_n+\sqrt{1+a_n^2}$ and $a_0=0$. Prove that $\lim\limits_{n \to \infty} \frac{a_n}{2^{n-1}}=\frac4\pi$. So I tried ...
-1
votes
0answers
42 views

Prove identity $\sum_{k}{n\brack k}{k\brace m}=\binom{n}{m}\frac{(n-1)!}{(m-1)!}$ [duplicate]

I'm looking for a proof of this identity: $$ \sum_{k}{n\brack k}{k\brace m}=\binom{n}{m}\frac{(n-1)!}{(m-1)!} $$ I'm looking especially for a combinatorial proof (if such exists), but different method ...
0
votes
2answers
66 views

Closed form of $\sum_{k=1}^{n} s(n, k) k x^{k}=?$

My question is $$\sum_{k=1}^{n} s(n, k) k x^{k}=?$$ $s(n, k)$ are Stirling numbers of the first kind. Here is a reference for second kind of stirling numbers. Formula for $\sum_{k=0}^n S(n,k) k$, ...
0
votes
0answers
39 views

Stirling unsigned numbers of first kind, identity.

I would like to find a combinatorial proof of the following formula, concerning Stirling numbers of first kind (unsigned): $$s(n+1,k+1)=\sum_{j=k}^n \frac{n!}{j!} s(j,k).$$ Has anyone an idea? Thank ...
0
votes
0answers
28 views

Finding a function such a partition of a set contains $x$, $y$, $x+y$ for some two elements [duplicate]

Prove that there exists a function $f: \mathbb{N} \to \mathbb{N}$ such that a partitioning of $\{1,2,...,f(n)\}$ into $n$ classes will have some $x,y$ such that $x$, $y$ and $x+y$ all belong to the ...
0
votes
1answer
30 views

Rising factorial stirling numbers from the recurrence

I have seen a proof that the recurrence of the unsigned stirling numbers of the first kind can be derived from the rising factorial definition. That is, $s(n,k)$ are given by the coefficients on $x^k$ ...
0
votes
1answer
36 views

Induction proof with Stirling numbers of the second kind

I'm having trouble understanding this exercise from Bóna's book "A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory" It says: Let m be a fixed positive integer. ...
3
votes
2answers
80 views

Show that $\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}$

Let $m\le n$ be positive integers. I want to prove the inequality $$\sum_{k=0}^m (-1)^{k+m} \binom{m}{k} \left(\frac{k}{m}\right)^n \le \binom{n}{m} \frac{m!}{m^m}.$$ I have tried direct algebraic ...
4
votes
3answers
155 views

Stirling number relation

Let $S(k,n)$ denote the Stirling number, i.e. the number of ways to partition $k$ distinguishable objects into $n$ indistinguishable blocks. Then consider $S(n+r,n)$ for some fixed $r$, how can I show ...
0
votes
1answer
44 views

Problem about counting partitions

The number $f(n)=B(n)-\sum_{k=1}^n B(n-k) {n \choose k}$ counts certain partitions of $[n]$.Which partitions? From Wiki, The Bell numbers satisfy a recurrence relation involving binomial coefficients:...
1
vote
1answer
39 views

Show that for every natural number $n$ there is equality - Stirling numbers of the second kind [closed]

Show that for every natural number $n$ there is equality: $$\left\{ n\atop 3\right\} = \frac{3^{n-1}-2^n+1}{2}$$ To prove this equality use equality $${{n+1}\brace{m+1}} = \sum_{k=0}^{n}{n\choose k}...
3
votes
0answers
94 views

Is there a closed form of $\sum_{k=1}^{n} \frac{|S_{1}(n,k)|}{k!}z^{k} $?

So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind: $$ \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)_{n} = \prod_{k=0}^{n-1} (z+k) , $$ and $$ \...
1
vote
1answer
44 views

What is $\sum_{n} |S_{1} (n,k)| x^{n} $?

I'm trying to find out what the generating sum in the question title amounts to. So far, I've found the following related results (see p. 5 of this paper): $$ \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)_{n}...
4
votes
2answers
104 views

How to prove an identity involving a finite sum of binomial coefficients

I’m struggling to prove this identity $\displaystyle\sum_{m=1}^{n}{\left(\binom nm\frac{{{\left( -1 \right)}^{m-1}}n!}{m} \right)}=\sum_{m=0}^{n-1}{\frac{n!}{n-m}}$. I do understand that it equals $\...
1
vote
0answers
54 views

Where am I misunderstanding this formula for Stirling numbers

Wkipedia says to count surjections with inclusion exclusion for this formula for the stirling numbers:$${n\brace k}={\frac {1}{k!}}\sum _{{j=0}}^{{k}}(-1)^{{k-j}}{k \choose j}j^{n}$$ I get that for $...
1
vote
1answer
33 views

Equivalence relations and Stirling numbers

Show that there are $\sum_{k=1}^{n}S_{n, k}$ equivalence relations on an n-element set. The numbers Sn,k are Stirling numbers of the second kind. I am learning discrete mathematics from different ...
2
votes
0answers
36 views

Show that the Stirling numbers of the second kind satisfy the recurrence:

I need help satisfying this recurrence. Thanks in advance! Show that the Stirling numbers of the second kind satisfy the recurrence: S(k,n) = $\sum_{i=1}^k S(k-i, n-1) {k-1 \choose i-1}$ I think a ...
0
votes
1answer
38 views

Stirling Numbers of second kind recurrence

While learning the stirling numbers of second kind, we see a recursive relation : $$S(n, r) = S(n-1, r-1) + k\cdot S(n-1, r)$$ And we get its solution as : $$S(n, r) = (1/{r!})[r^n - C(r,1)\cdot (r-1)^...
6
votes
1answer
137 views

Is there a standard compact notation for $k!{n\brace k}$?

Is there a standard compact notation for the numbers $$ ?(n,k)=\sum_{i=0}^k(-1)^i\binom ki(k-i)^n\equiv k!{n\brace k} $$ where ${n\brace k}$ is the Stirling number of the second kind? In ...
5
votes
0answers
71 views

Is this combinatorics derivation correct?

On the Wikipedia I found the following formula: $ x^m = \sum\limits_{k=1}^{m+1} \left \{ \begin{array}{cols} m+1 \\ k \end{array}\right \} (x-1)^{\underline{k-1}} \,\,\,\,\,\, (1) $ See: https://en....
3
votes
2answers
116 views

Difference of the Stirling cycle numbers and the Stirling set numbers

Denote by $\left\langle\!\! \left\langle k\atop j\right\rangle\!\! \right\rangle$ the second-order Eulerian numbers A340556. Define $$ \left| n\atop k\right| = \sum_{j=0}^k \left( \binom{n + j - 1}{...
0
votes
1answer
33 views

Number of bits in a stirling number

I know that the number of bit required for $N!$ is $\Theta(n\log n)$ by the stirling approximation. But what is the number of bits required for a stirling number of the first kind of the form $\left[\...
2
votes
1answer
96 views

An associated Stirling number identity related to the second-order Eulerian numbers.

A similar Stirling number identity representing the second-order Eulerian numbers can be found at this question. We denote the associated Stirling cycle numbers as $\left[\!\left[ n\atop k\right] \! \...
0
votes
1answer
25 views

Stirling Numbers of the first kind diagonal closed form, understanding indexing.

So for the signed stirling numbers of the first kind, I wanted a formula for the diagonals On Wikipedia they describe the formula as the below. I don't quite understand how the indexing works for the ...
1
vote
1answer
27 views

Is this Inclusion-Exclusion: $m$ balls colored $n$ colors such that each color is represented?

Suppose you have $m$ balls each of which can be colored by $n<m$ different colors, and your paint cans are unlimited. I want to count the number of ways that you can color balls such that each ...
4
votes
1answer
144 views

A Stirling number identity representing the second-order Eulerian numbers.

Graham, Knuth, and Patashnik give in CMath a thorough introduction to the Stirling numbers. On table 250 and table 251, they compile two pages of Stirling number identities. Of course, there are many ...
5
votes
2answers
128 views

Limiting Sum including Stirling numbers

I would like to simplify the following summation including $S(m,n)$, Stirling numbers of the Second kind. $\begin{gather*}\\ && \frac{1}{n^{n+1}}\sum_{k=1}^{n-1}\binom{n}{n-k}S\left( n,n-k\...
1
vote
2answers
50 views

Numerically evaluate a series involving Stirling numbers of the second kind

How can I numerically evaluate the following for $n$ above one million: $$ \sum_{k>=n} \sum_{i=0}^{n-1} (-1)^i {{n-1}\choose{i}} \left( \frac{n-1-i}{n} \right)^{k-1} k (k+1)$$? I have tried ...
2
votes
1answer
44 views

Recurrence relation for Stirling number of first kind with a minimum value

As it states in Wikipedia: Stirling numbers of the first kind count permutations according to their number of cycles. And the recurrence relation is as follows: $\left[{n+1\atop k}\right] = n \left[{n\...
2
votes
2answers
83 views

Summation including Stirling numbers of the second kind

I would like to show the following: (I am pretty sure it is correct but was not able to prove it.) $\begin{eqnarray*} &&\sum_{j=1}^{n}j\binom{n}{j}S\left( n,j\right) j! =n(n^n-(n-1)^n) \\ &...
6
votes
3answers
171 views

Compact formula for the $n$th derivative of $f\left(\sqrt{x+1}\right)$?

I'm interested in a general formula for $$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big].$$ In particular, Fàa di Bruno's formula gives $$\frac{d^n}{dx^n}\Big[f\left(\sqrt{x+1}\right)\Big]=\sum_{k=...
2
votes
1answer
101 views

A combinatoric identity involving Eulerian and Stirling numbers

Let $$ A_{n}(x)=\sum_{k=0}^{n}\left\langle\begin{array}{l} n \\ k \end{array}\right\rangle x^{n-k} $$ Eulerian Polynomials and $$ \left\langle\begin{array}{l} n \\ k \end{array}\right\rangle $$ are ...
0
votes
0answers
20 views

Proof of $S_{n,r} = \frac{1}{r!} \sum_{k=0}^r (-1)^{r-k} \binom{r}{k} k^n$ with inclusion-exclusion principle [duplicate]

For $n, r \in \mathbb{N}$, $(X_1, ...,X_r)$ is an ordered partition of $[n]$ in $r$ non-empty sets, if $X_1,..., X_r$ are disjoint and non-empty subsets of $[n]$ for which it holds that $X_1 \cup .....
1
vote
1answer
60 views

Combinatorics - Counting Something Similar to Unsigned Stirling Numbers of the First Kind

I want to count something similar to unsigned Stirling numbers of the first kind. Can someone tell me what math describes the quantity I'm interested in? Suppose I have $n$ people numbered $1, 2, ..., ...
1
vote
1answer
68 views

Show that the number of ways of splitting a set with $n$ elements into $k$ non-empty subsets is equal to $x^n$'s coefficient in a series

The series evaluates to (could not put it in the title): $$\frac{x^{k}}{(1-x)(1-2x)...(1-kx)}$$ I tried to come up with something. A solution would probably require a use of the geometric series ...
3
votes
1answer
43 views

Ambiguous solution on arranging $6$ people on $3$ indistinguishable tables.

If there must be at least one person in each table, in how many ways can $6$ people be seated around three circular tables? (We assume tables are indistinguishable) This problem was an introductory ...
1
vote
1answer
46 views

Further Stirling number series resummation

\begin{equation} \sum_{m=1}^\infty\sum_{n=1}^\infty (-1)^{n } \frac{S_m^{(3)}}{m! n}(-1 + u)^{(m + n - 1)} (\frac{x}{-1 + x})^m \end{equation} Note: $S^{(3)}_m$ belongs to the Stirling number of the ...
0
votes
1answer
54 views

A problem on Stirling numbers of second kind.

In this section, there were four cases, the 4 combinations of distinguishable and identical balls and cells. I could understand [Distinguishable balls and cells] and [identical balls and ...
1
vote
1answer
26 views

Putting 10 distinguishable people into 2 groups so that no group is empty

In how many ways can we put 10 distinguishable people into 2 groups so that no group is empty? Order does not matter in a group and groups are not named. So I've done some research and people seem to ...
0
votes
0answers
38 views

Stirling number series resummation

\begin{equation}\sum_{m=1}^{\infty}\frac{a_1^3 S_m^{(3)} (u-1)^{m-1} \left(\frac{x}{x-1}\right)^m}{m!}\end{equation} Does somebody know the result of this resummation? Note: $S_m^{(3)} $ belongs to ...
0
votes
0answers
76 views

General expression of a triangle sequence

\begin{gather*} \frac{1}{4} \\ \frac{1}{4} \quad \frac{1}{4} \\ \frac{11}{48} \quad \frac{1}{4} \quad \frac{11}{48} \\ \frac{5}{24} \quad \frac{11}{48} \quad \frac{11}{48} \quad \frac{5}{24} \\ \frac{...
5
votes
2answers
93 views

An identity for $\binom{-1/2}{n}$

I would like to show the formula $$\forall n \in \mathbb{N},\quad\sum_{p=0}^n \binom{n}{p} \frac{(-1)^p}{p!} \prod_{k=0}^{p-1} \left(n+\frac{1}{2} + k\right) = \binom{-1/2}{n} \, , $$ which is true ...
3
votes
1answer
121 views

Combinatorial proof of a nice expression for Stirling numbers of second kind

While answering a question I came across the following nice identity: $$ \sum_{1\le k_1\le k_2\le\dots\le k_n\le m}\prod_{1\le i \le n}k_i={n+m \brace m}, $$ where ${n+m \brace m}$ refers to the ...
3
votes
1answer
109 views

A combinatorial identity involving Stirling numbers of the second kind

Answering a recent question I came across the following interesting identity: $$ \sum_{k=0}^m\binom mk{n+k+1 \brace k+1}k!=\sum_{k=0}^m\binom mk (-k)^{m-k}(k+1)^{n+k}. $$ Is there a simple way to ...
0
votes
1answer
61 views

Stirling number of the 2nd kind with pigeonhole theorem

I have just learnt Stirling number of the 2nd kind and I was also given a hint that this involves the pigeonhole theorem, but I have no idea how to approach this question. Any help would be much ...
0
votes
1answer
90 views

Partial sum of Stirling numbers of the second kind with falling factorial

Let $S_n = \{ 1, 3, ... \}$ be the set of odd numbers not greater than $n$ and $(x)_n$ be the falling factorial $x(x-1)\cdots(x-n+1)$. I am interested in the following partial sum: $$ \sum_{i \in S_n} ...
2
votes
1answer
314 views

Faulhaber formula from geometric series and operators?

As shown in this post, $$ \sum_{k=1}^n x^k = x \sum_{k=1}^{n} \binom{n}{k} (x-1)^{k-1}$$ For RHS, notice $x= \left(1+( x-1) \right)$ and using this we get, $$ \sum_{k=1}^n x^k = \sum_{k=1}^{n} \binom{...
0
votes
2answers
83 views

10 ball as put in 7 boxes randomly. What is the probability that at least one box is empty?

My solution: First, put one ball at each box and then distribute the remaining 3 balls in 7 boxes. $p=1-\frac{\binom{9} {3} }{\binom{16}{10}}$ Is this correct? Or? $p=1-\frac{\binom{10} {7} 7!7^3}{7^{...

1
2 3 4 5
12