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.

learn more… | top users | synonyms

3
votes
1answer
56 views

Partial sums of Nicomachus's Triangle rows produce Stirling numbers of the 2nd kind?

I took partial sums of this triangle OEIS A036561 and found Stirling numbers of the 2nd kind. At OEIS A000392, at the mid-point of the comments section, is a conjecture. I think it's what I found. I ...
0
votes
1answer
28 views

Does $\sum_{i = 1}^n S(k, i)i! = n^k$?

Consider the number of ways of ditributing $k$ distinct objects into $n$ distinct boxes, where $k \ge n$. On one hand, we can assign a box to each object. There are $n^k$ ways to do this. On the ...
2
votes
0answers
69 views

Stirling numbers and Power Group Enumeration

The following question is a reference request concerning a derivation of the EGF for the Stirling numbers of the second kind by Power Group Enumeration / Burnside's Lemma, which is $$\sum_{n\ge 0} ...
0
votes
0answers
35 views

proof of equation - generating function, stirling number

Look at following equation: $$\frac{x^n}{(1-x)(1-2x)...(1-nx)} = \sum_{k} {k\brace n}x^k $$ I see that it is product of generating function: $$x^n \cdot \frac{1}{1-x}\cdot \frac{1}{1-2x} ...
2
votes
1answer
73 views

Proving combinatorial identity with the product of Stirling numbers of the first and second kinds

$$ \sum_{k} \left[\begin{array}{c} n\\k \end{array}\right] \left\{\begin{array}{c} k\\m \end{array}\right\} = {n \choose m} \frac{\left( n-1\right)!}{\left(m-1 \right)!}, \quad \text{for } n,m > 0 ...
1
vote
1answer
53 views

Prove the identity involving summation and Stirling numbers of the second kind

Prove the identity $$(e^z-1)^m=m!\sum_{n}^{}{n \brace m}\frac{z^n}{n!}$$ $n\brace m$ stands for Stirling numbers of the second kind. I'm not really sure if $z$ is some special number or just an ...
6
votes
0answers
113 views

stirling numbers and harmonic number identities

Permit me a brief introduction before I state the question, three questions in fact. Inspired by this MSE link I computed the following harmonic sum identities: $$1/6\, \left( {H_{{n}}}^{(1)} \right) ...
1
vote
1answer
44 views

Generalization for Stirling numbers 2nd kind to negative column-indexes?

The exponential generating functions for the Stirling numbers 2nd kind are the n'th powers of $f(x)=\exp(x)-1$ (where this is understood as formal power series, Abramowitz&Stegun, 26.8.12). ...
5
votes
4answers
222 views

An asymptotic term for a finite sum involving Stirling numbers

The question is a by-product at the end of this post. The following asymptotic term will ensure the convergence of some series. $$ \frac{1}{n!} \sum_{k = 1 }^{n } \frac{{n \brack k}}{k+1} = ...
2
votes
1answer
39 views

Asymptotic approximation for the r-associated Stirling numbers of the second kind

It is well know that for fixed $k$ the asymptotic approximation for the Stirling numbers of the second kind is given by $\frac{k^n}{k!}$. Does such simple asymptotic expression also exist for the ...
2
votes
1answer
63 views

Stirling-like sum equal to zero when $k>n$

I need to prove that $$\sum_{r=0}^k\binom{k}{r}(-1)^r r^n=0$$ when $n<k$. I know that the formula above can be easily transformed into the Stirling number of the Second kind formula, which is ...
0
votes
0answers
67 views

Number of set partitions of n elements into k sets with subsets of size r not allowed

This is a generalization of the question Number of ways to partition a set with $n$ elements to $k$ subsets where at least one subset has $r$ elements . At the end of answer for this question, there ...
1
vote
1answer
50 views

Closed form for the Stirling numbers of the second kind.

I have realized through inspection that ${n \brace 2}=2^{n-1}-1$ and I have figured out with the help of Pedro Tamaroff that ${n \brace 3}=\frac{1}{6}(3^{n}-3\cdot2^n+3)$. For what other values of $k$ ...
4
votes
2answers
418 views

What is this notation, similar to the binomial coefficient?

I've come accross this notation: $$\left\{\begin{eqnarray}n\\m\end{eqnarray}\right\}$$ The only other info I have about this notation is that $\left\{\begin{eqnarray}4\\2\end{eqnarray}\right\}=7$ ...
0
votes
1answer
47 views

Stirling number of the second kind recurrence relations

I am interested to understand why the following recurrence relations of the Stirling number so the second kind hold using counting arguments ...
0
votes
1answer
56 views

Stirling Number of the Second Kind (intuition for formula)

The Stirling number of the second kind is the way of putting $n$ objects into $k$ nonempty boxes. I would like to understand the right hand side of this equation by a counting argument $$S(n,k) = ...
1
vote
2answers
60 views

How do I show the following identify where c(n , k) represent unsigned stirling numbers of the first kind?

I need to show the following identity but I don't know where to start. $ c(n+1, m+1) = \sum_{k=0}^{n} c(n, k) \binom{k}{m} $
5
votes
1answer
113 views

Nonattacking rooks on a triangular chessboard

Given an $n \times n$ chessboard from which the squares above the diagonal have been removed, find the number of ways to place $k$ non-attacking rooks on this board. I believe the answer to be ...
2
votes
0answers
56 views

number of ways to split n distinguishable objects into k indistinct sets - allowing for sets with 0 objects

After throughout searching both on this site and others I cannot seem to find a good explanation of how to solve this problem. I understand that if the objects are indistinguishable then it is a ...
1
vote
3answers
85 views

Proof on a property of Stirling Numbers of the first kind

How should i proceed to prove that the sum of every odd stirling number on a row is n!/2? $$\sum\limits_{k=1|k=odd}^n s(n,k)=\frac{n!}{2}$$
1
vote
0answers
48 views

Can this sum be shown to be zero? $\sum_k \left[ {m+1} \atop k \right]{ k+n \brace m}(-1)^{m+k} = 0$

I thought it was easy but not quite. If it can be shown it will give another proof of a formula I found. Here $m$ nad $n$ are non-negative integers. I would like the following to be (hopefully ...
4
votes
3answers
188 views

$\Delta^d m^n =d! \sum_{k} \left[ m \atop k \right] { {k+n} \brace m + d}(-1)^{m+k}$ Is this a new formula?

(EDIT: The variable $z$ is changed to $d$ so as not to be confused with generating function notation) I have derived this formula involving the Stirling numbers that I now feel confident is correct ...
0
votes
1answer
37 views

Understanding relation between Product and Summation Notation

So I am given the following: $n = \sum_{i=1}^{k}m_{i}$ I am also given $x = \sum_{i=1}^{k}log(m_{i}) = log\prod_{i=1}^{k}m_{i}$ I was only given the first part, however I believe that is a ...
2
votes
1answer
65 views

Stirling numbers of first kind over multiset

Given a multiset $M = \{ 1^{a_1} , 2^{a_2} ,\ldots , k^{a_k} \}$ where $N = \sum_j a_j$ $f(M, r)$ denotes the number of permutations of the multiset $M$ that have exactly $r$ strongly outstanding ...
2
votes
1answer
99 views

Ways to put $5$ balls in $3$ boxes if each box must contain at least $1$ ball.

How many ways can you put $5$ balls in $3$ boxes if each box must contain at least one ball? I've some doubts about this issue, I think the solution is related to the second kind of Stirling ...
0
votes
1answer
47 views

Stirling, asymptote of $n^2+n-1\choose n$

I need to find the asymptote of $n^2+n-1\choose n$. any idea? I used the Stirling formula for $n!$ but I found an unexpected final answer.
4
votes
1answer
79 views

Finite sum related to Stirling numbers

I am wondering if there is a closed form solution for the following sum: $$ \sum _{k =0}^{n-1} \frac{(-1)^{k} (n-k)^{n+1} }{(k+1)(k+2)}\binom{n}{k}. $$ If the the factors $(k+1)(k+2)$ in the ...
2
votes
1answer
135 views

Bins and balls model - filling first bins [close]

We have $n$ bins and $m$ balls. I want to compute the probability that in the first $k$ bins, $q$ of them will be non-empty. I can throw $m$ balls into $n$ bins in $n^m$ ways. Using Stirling ...
1
vote
0answers
33 views

Counting Chains of Bounded Types

You have pearl of 3 types. Type 1 pearl can be of color from 1 to X. Type 2 pearl can be of color from X+1 to X+Y Type 3 pearl can be of color from X+Y+1 to X+Y+Z. You have unlimited supply of ...
0
votes
1answer
72 views

Relation between Binomial coefficient and Stirling number of second type

Is that true, that for every n,k such that $$k>1$$ we have the inequality $${n \choose k} \leq {n \brace k}$$?
1
vote
2answers
110 views

Deriving a formula for the number of ways to partition a set

I'm working on a question below: Let $H(n,k)$ denote the number of ways to partition a set with $n$ elements into $k$ subsets of the same size. Derive a formula for $H(n,k)$. Thanks in advance ...
0
votes
1answer
48 views

Proof for identity for bell numbers

How can I proof this identity for bell numbers? $$B_n = \sum_{k=0}^n S(n,k)$$ Is it possible without using the recurrence relation?
2
votes
1answer
87 views

What is the family of generating functions for the *rows* of this Stirling-number matrix for whose columns they are $\exp(\exp(x)-1)-1 $?

Remark: I give much background because it might significantly help to find an idea how to generate a solution I'm analyzing properties of a certain infinite matrix $U$, for whose columns we ...
2
votes
1answer
142 views

Stirling numbers of second type [duplicate]

How can I do a combinatoric proof that for Stirling number of second type the equality if true: $${n\brace k} = \frac{1}{k!}\sum_{i=0}^{k}{k \choose i}i^n(-1)^{k-i}$$
0
votes
0answers
52 views

Number of Singleton Blocks in Set Partition

I'm interested in some general information on the following question: Consider the collection of partitions of an $n$-set into $m$ blocks as a uniform probability space. Let $X$ be the random ...
2
votes
0answers
33 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
2
votes
1answer
33 views

What distribution do the rows of the Stirling numbers of the second kind approach?

In wikipedia about the Pascal triangle: Relation to binomial distribution "When divided by 2n, the nth row of Pascal's triangle becomes the binomial distribution in the symmetric case where p = 1/2. ...
2
votes
1answer
69 views

What is the asymptote for the positions of the largest Stirling numbers of the second kind?

The infinite lower triangular array of Stirling numbers of the second kind starts: $$\begin{array}{llllllll} 1 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} ...
2
votes
1answer
136 views

Proof of summation of Stirling's Numbers of the first kind

"Stirling's number of the first kind $s(n,k)$ is the number of permutations of ${1,2,...,n}$ with $k$-cycles. Prove that $n! = \sum s(n,k)$ (from k = 1 to $\infty$) " After checking a the first few ...
2
votes
1answer
466 views

Distribution of distinct balls in identical boxes

how can I derive a formula for the number of distributions of $n$ different balls in $k$ identical boxes. Where $\mathbf{empty\ box}$ is allowed. I know this is equivalent to finding the number of ...
2
votes
0answers
78 views

Asymptotic of Stirlings numbers of the first kind

I am trying to find some asymptotic expression for the unsigned stirling numbers of the first kind. Lets denote them by $|s(n,k)|$, and suppose that $k$ is fixed. So far I have tried using the fact ...
5
votes
1answer
328 views

Combinatorial Proof for Series of Stirling Numbers & Binomial Coefficients

I am struggling with the following question from an assignment for an introductory course to combinatorics. Show, by means of a combinatorial argument, that the following holds: ...
0
votes
1answer
54 views

How to solve this using using stirling approx?

I have a relation $log(n!)=\Theta(n\log n)$ . And i really don't know how to reduce this using using stirling approx. ? But do know and tried with few logrithmic property like " Even if its ...
0
votes
1answer
99 views

How does one prove this equation?

How does one prove the following equation , I am getting confused about this, I can't seem to find any proving technique, I tried plugging in the Stirling's formula for factorials but to no avail - ...
6
votes
1answer
140 views

Simple approximation to a sum involving Stirling numbers?

I have also posted this question at http://mathoverflow.net/questions/141552/simple-approximation-to-a-sum-involving-stirling-numbers#141552. I have an exact answer to a problem, which is the ...
8
votes
2answers
225 views

Stirling number

I am trying to evaluate the following finite sum: $$ \sum_{k=1}^{n}(-1)^{k}(k-1)!S(n-1, k-1)(\sum_{i=0}^{k-1}H_{i}), $$ where $S(n, k)$ are the Stirling's numbers of the second kind and $H_{i}$ ...
5
votes
1answer
155 views

Combinatorial proof for an identity about Stirling cyclic numbers

Solving through Lovász' Combinatorial Problems and Exercises I found an exercise asking me to prove two identities: $$ \sum_{k = 0}^n {n \brace k} (x)_n = x^n $$ $$ \sum_{k = 0}^n \left[ n \atop k ...
2
votes
2answers
68 views

How to find Stirling coefficient of the second order ?

Can someone please explain how can I find the coefficient of the Stirling number of the second kind for S(8,k) ? After checking here , I found that : ...
2
votes
1answer
57 views

Stirling numbers practice question 1

This is a practice question and not HW Q. Let $A=\{1,2,3,4,5,6,7\}$ and $B=\{v,w,x,y,z\}$. Determine the number of functions $f:A \longrightarrow B$ where a) $f(A)=\{v,x\}$ Ans. $2!*S(7,2)$ I ...
1
vote
1answer
50 views

derangements basic practice question 2

This is not HW just a practice question from the text. Q.. (NOTE: I find that both part a and b say the same thing but the answers are different) Ten women attend a business luncheon. Each women ...