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

2
votes
0answers
13 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
49 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
40 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
158 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
27 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
54 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
53 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 ...
-2
votes
1answer
70 views

Stirling's approximation to birthday problem

a) What is the probability that in a group of N people, at least two share a birthday? Solved. P = 1 - 365!/[(365)^n. (365-n)! b) Use Stirling's approximation Ln (n!) = n ln(n) - n for large n to ...
0
votes
1answer
38 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
62 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
114 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
23 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
62 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
77 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
38 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
61 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
112 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
39 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
27 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
29 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
62 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
121 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
348 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
69 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
260 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
51 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
97 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
120 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 ...
6
votes
1answer
186 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
143 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
60 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
49 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
46 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
95 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
126 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
199 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
95 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
40 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
169 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, ...
2
votes
2answers
87 views

Stirling Binomial Polynomial

Let $\{\cdot\}$ denote Stirling Numbers of the second kind. Let $(\cdot)$ denote the usual binomial coefficients. It is known that $$\sum_{j=k}^n {n\choose j} \left\{\begin{matrix} j \\ k ...
2
votes
1answer
112 views

Important numbers in Combinatorics

I recently went through some important numbers like the Stirling and Bell number for calculation of partitions /equivalence relations. I was wondering if someone can help me get a list of important ...
5
votes
2answers
116 views

Evaluating $\int_0^1 \frac{\ln^n x}{(1-x)^m} \, dx$

On another forum someone asked to show that for $n > m-1$ and $m \ge 2$, $$\int_0^1 \frac{\ln^n x}{(1-x)^m} \ dx = (-1)^{n+m-1} \frac{n!}{(m-1)!} \sum_{j=1}^{m-1} (-1)^j s(m-1,j) \zeta(n+1-j) $$ ...
18
votes
3answers
438 views

Combinatorial proof of a Stirling number identity.

Consider the identity $$\sum_{k=0}^n (-1)^kk!{n \brace k} = (-1)^n$$ where ${n\brace k}$ is a Stirling number of the second kind. This is slightly reminiscent of the binomial identity ...
2
votes
1answer
152 views

I just don't see what I do wrong - number of surjections seems higher than number of functions.

EDIT: Answer added. I haven't slept much lately and I've been raging on this thing for a couple hours now. I really hope some people here can have the same obsession/rage and will help me out. I ...
-1
votes
1answer
101 views

Sum with Stirling numbers

Show that for each $n>1$ $$\sum\limits_{k=1}^{n-1} \frac{(n-1)!}{(k-1)!}S(n,n-k) = (n-1)^n $$ where $S(n,m)$ is the Stirling number of the second kind.
0
votes
1answer
114 views

Stirling numbers. Combinatorial proof.

Please, help! What is the combinatorial proof of the following identity about signless Stirling numbers of the first kind, $c(n,k)$. $$\binom {i+j}{j} c(n,i+j) = \sum\limits_{k=0}^{n} \binom nk ...
1
vote
0answers
266 views

A recurrence relation for Stirling numbers (2nd kind)

It is well-known that the Stirling numbers of the second kind satisfy the following (vertical) recurrence relation: $$\sum\limits_{r=k}^n \binom{n}{r}S\left( r,k\right) =S\left( n+1,k+1\right) $$ ...
1
vote
1answer
81 views

Determining Stirling number

In the first part of the question I was asked to find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ (a fixed constant) distinct ...
2
votes
1answer
138 views

Stirling Number Identities [duplicate]

If $$\sum_{k=0}^nS(n,k)=B(n)\;,$$ the bell number, then does $$\sum kS(n,k)=B(n+1)-B(n)\;?$$