Linked Questions

9
votes
5answers
611 views

The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$

A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
3
votes
4answers
913 views

An identity involving Stirling numbers of the second kind and binomial coefficients

Need to prove: $$\sum\limits_{k=0}^{n} \binom nk k^r x^k = \sum\limits_{j=0}^{r} \binom nj j! (1+x)^{n-j} x^j S(r,j)$$ where $S (n, k)$ denotes a Stirling number of second kind, the number of ...
6
votes
4answers
370 views

An identity involving binomial coefficients

Prove the following identity $$\displaystyle \sum_{i+j=m}\frac{(n-1) \binom{ai+n-1}{i} \binom{aj+1}{j}}{(ai+n-1)(aj+1)} = \frac{n\binom{am+n}{m}}{am+n}$$ where $i = 0,1,\cdots,m$ and $m, n$ are ...
6
votes
2answers
503 views

Sum of Stirling numbers of both kinds

Let $a_k$ be the number of ways to partition a set of $n$ elements $orderly$,which means that order of subsets matters, but order of elements in each subset does not. My task: Prove, that$$\sum_{k=...
3
votes
3answers
86 views

Coloring Hats on Cats

Imagine I have $n$ indistinguishable cats and $k$ designs to color the hats on those cats. Consider the case where $k \leq n.$ I want to figure out the number of ways I can color the hats on these ...
4
votes
1answer
302 views

(Average) Number of cycles of length m in permutations on N with k cycles

Suppose we have permutations on $[1,2,...,n]$ that have exactly $k$ cycles (which there are $|s(n,k)|$ of where $s(n,k)$ is the Stirling number of the first kind). What is the average number of ...
2
votes
2answers
388 views

Singletons in coupon collecting problem

There are $n$ types of coupons. All types are equally likely to turn up and each "draw" of a coupon is independent of others. If someone collects coupons until they have a complete set of all the $n$ ...
5
votes
3answers
136 views

binomial expression of a powered term [duplicate]

One answer to a previous question of mine asserted that $$k^2=\binom k2+\binom {k+1}2.$$ I checked that the formula is true. However, it intrigued me. Is there a similar expression for $k^3$? How ...
1
vote
1answer
386 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
4
votes
1answer
98 views

How can we show that $\sum_{k=1}^{n}{2n+2\choose 2k}B_{2k}=n?$

Given the sum $$\sum_{k=1}^{n}{2n+2\choose 2k}B_{2k}=n\tag1$$ Where $B_{2k}$ is Bernoulli number It is quite interesting to me, the answer results in a natural number, how do you go about ...
3
votes
2answers
90 views

Showing that $x^n=\sum_{k=1}^{n}{n\brace k}(x)(x-1)\ldots (x-k+1)$ holds for all numbers, not just positive integers

I just finished proving that this statement holds for all positive integers $r$ (through a combinatorial argument) $$r^n=\sum_{k=1}^{n}{n\brace k}(r)(r-1)\ldots (r-k+1)$$ (where the curly braces ...
2
votes
1answer
118 views

Simplifying my sum which contains binomials

While dealing with compositions (ordered partitions) of integers, I found the following formula for the shifted $m$-generalized Fibonacci numbers (Wikipedia: Generalizations of Fibonacci numbers): $$F(...