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

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
3
votes
2answers
78 views

Finite sum involving Stirling numbers

I am trying to evaluate the following finite sum: $$ \sum_{h=0}^{m}\binom{m}{h}2^{m-h}S(h,k-r)S(m-h,r),\qquad 0\leq r\leq k\leq m, $$ where $S(n,k)$ is the Stirling number of the second kind. Can ...
2
votes
1answer
45 views

Find closed form formula for $c(n,n-4)$.

Find closed form formula for $c(n,n-4)$. Where $c(n,k)$ are signless stirling numbers of first kind. I need help.This is my last question all others problems of my exercise I have solved this is ...
1
vote
5answers
68 views

Find closed formula for $S(n,n-4)$.

Find closed formula for $S(n,n-4)$. These are stirling numbers of 2nd kind. My attempt: I uses the recurrence relation $$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$ ...
1
vote
1answer
32 views

fixed length of permutaions cycles

How much permutations has only 10 cycles, but three of them has length 3 and seven of them has length 7?
2
votes
1answer
79 views

Prove the summation involving Stirling numbers of the first kind

I have been trying to prove or disprove this for 2 days now, but i don't even know where to begin. $$ 1 = \sum_{m=1}^{n} \sum_{k=1}^{n} \frac{x^{n-m}(-1)^{n-k-m} \left[\matrix ...
2
votes
0answers
38 views

My (divergent) summation of the zetas with sets of cofactors give systematically errors of simple integer differences. What am I missing?

This is a "fiddling" in a small project of mine with which I'm concerned from time to time for three years now. I try to focus on the core of the problem, please ask if more context is needed. ...
1
vote
0answers
65 views

Primality of Stirling numbers of second kind (again)

This question follows a previous one on the primality of Stirling numbers of the second kind ${n \brace k}$. Gerry indicated a paper on the topic. In this paper it is shown that for ${n \brace k}$ to ...
1
vote
1answer
31 views

Stirling numbers of the second kind — a series-expansion typo?

In H. S. Wilf's generatingfunctionology, (1.6.8) describes: $$ A_n(y) = \sum_k \begin{Bmatrix}n-1\\k-1\end{Bmatrix} y^k + \sum \begin{Bmatrix}n-1\\k\end{Bmatrix} y^k $$ $$ = yA_{n-1}(y) + \left( y ...
1
vote
0answers
60 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 ...
2
votes
2answers
50 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
57 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
34 views

Primality of Stirling numbers of second kind

Apart from the Mersenne primes $M_p=2^p-1=\begin{Bmatrix}p+1\\2\end{Bmatrix}$, and the four primes $\begin{Bmatrix}n\\4\end{Bmatrix}$ where $n$ is given in http://oeis.org/A100958, are there other ...
1
vote
1answer
32 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
102 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
38 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
95 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
52 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
100 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
66 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
135 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
50 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). ...
7
votes
4answers
264 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
53 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
68 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
115 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
66 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
424 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
65 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
78 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
73 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
183 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
81 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
95 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
50 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
198 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
45 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
71 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
135 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
50 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
88 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
143 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
82 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
135 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
59 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
95 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
188 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}$$
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
38 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. ...