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

4
votes
2answers
60 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} = ...
1
vote
0answers
17 views

Bound the expression with Stirling approx.

I already compute 2 expressions of one problem, but they are so complicated as below. My prof requests me to reduce them or upper bound them by Stirling approximation but I have not succeeded. 1/ ...
2
votes
1answer
30 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
42 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
38 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
38 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
410 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
42 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
45 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
57 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} $
4
votes
1answer
101 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
45 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
80 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
47 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
178 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
34 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
60 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
86 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
45 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
75 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
131 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
30 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
70 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
98 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
43 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
75 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
127 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
47 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
29 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
31 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
66 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
131 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
407 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
75 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
299 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
52 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
133 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
217 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
152 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
64 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 : ...
1
vote
1answer
55 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
49 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 ...
1
vote
1answer
101 views

Derangements basic practice question

practice questions not Homework I have problems with this questions that I have answers for but cant understand how the answer was derived. Q.1. In how many ways can the integer $1,2,3,...10$ be ...
8
votes
1answer
145 views

Counting subsets of lattice points

Let $n\ge 2$, and consider the set of $\binom{n}{2}$ lattice points in the interior of the triangle with vertices $(0,0)$, $(0,n+1)$ and $(n+1,n+1)$. For $r\le \binom{n}{2}$, let $f(n,r)$ be the ...
10
votes
2answers
263 views

Generating function with Stirling's numbers of the second kind

It's very easy to prove that: $$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)...(1-nz)}$$ But this generating function looks very pretty, so my question is: does this identity have some ...
0
votes
1answer
97 views

Generating The Series

This is related to an ongoing event. It involves generating the following series : http://oeis.org/A008826 The generating Function as given in the above link is : ...
0
votes
1answer
42 views

Relation between stirling numbers

Is there a relation between $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ and $$ \genfrac\{\}{0pt}{}{n-1}{n-3} $$ Like the first one can be obtained from the second one by adding something?
2
votes
1answer
45 views

Stirling numbers with $k=n-2$

Is there a more general method of calculating: $$ \genfrac\{\}{0pt}{}{n}{n-2} $$ Like for :$$ \genfrac\{\}{0pt}{}{n}{n-1} $$ we can use $nC_2 $
2
votes
0answers
173 views

Figuring out expression to give a integer sequence

Here given is a sequence from OEIS. The sequence is triangle of coefficients from fractional iteration of e^x - 1. Few terms are: 1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, ...