Tagged Questions

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

1
vote
0answers
48 views

Maximizing Stirling numbers of the second kind

In Stanley's Enumerative Combinatorics, there is a question on Chapter $1$ which goes as follows: Let $S(n,k)$ denote a Stirling number of the kind (ie, $S(n,k)$ is the number of ways to to ...
1
vote
2answers
44 views

Estimating the behavior for large $n$

I want to find how these coefficients increase/decrease as $n$ increases: $$ C_n = \frac{1}{n!} \left[(n+\alpha)^{n-\alpha-\frac{1}{2}}\right]$$ with $\alpha=\frac{1}{br-1}$ and $0\leq b,r \leq 1$. ...
0
votes
1answer
40 views

Combinatorial proof of an identity of Striling number of first kind

I can prove this identity using induction but i was looking for a combinatorial proof for this identity regarding stirling numbers of first kind. How should i proceed? Where, Thanks in advance.
0
votes
0answers
21 views

Primality of Stirling numbers of second kind

Apart from the Mersenne primes $M_p=2^p-1=S(p+1,2)$, and the four primes $S(n,4)$ where $n$ is given in http://oeis.org/A100958, are there other Stirling numbers of the second kind $S(n,k)$ which are ...
-1
votes
0answers
35 views

Uniform Convergence and exponential inequality to demonstrate Stirling's formula.

If $0<R\leq\sqrt n$ and $Z_{k} \sim exp(1)$ are independent and identically distributed as prove that $$P\left[\left|\dfrac{Z_{1}+Z_{2}+\cdots +Z_{n} -n}{\sqrt n }\right|\leq R\right] \geq 1- ...
1
vote
1answer
24 views

Total no. of partitions of $A$ using stirling no. of $2^{\text{nd}}$ kind

My notes describe Stirling numbers of $2^{\text{nd}}$ kind as : Given non-negative integers $r,n$ the stirling numbers of $2^{\text{nd}}$ kind denoted by are defined as: no. of ways of distributing ...
3
votes
1answer
90 views

Partial sums of Nicomachus' 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 ...
1
vote
1answer
34 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
81 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
46 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
89 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
59 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
121 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
46 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
240 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
44 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
64 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
96 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
59 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
421 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
59 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
64 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
68 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
131 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
64 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
89 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
49 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
193 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
41 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
69 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
113 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
49 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
85 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
139 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
34 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
77 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
116 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
54 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
92 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
156 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
55 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
35 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
73 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
147 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
516 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
80 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
353 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
55 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
100 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 - ...