Intereting Posts

Prove that there is no integer a for which $a^2 – 3a – 19$ is divisible by 289
Representing natural numbers as matrices by use of $\otimes$
A challenge by R. P. Feynman: give counter-intuitive theorems that can be translated into everyday language
What is a necessary conditions for Urysohn Metrization theorem?
Show that the function is discontinuous in $\mathbb{R}$
The concept of ordinals
Every group is the quotient of a free group by a normal subgroup
How can a = x (mod m) have multiple meanings in modular arithmetic?
If $p,q$ are prime, solve $p^3-q^5=(p+q)^2$.
Example of $\sigma$-algebra
Forming Partial Fractions
Dense subsets in tensor products of Banach spaces
covariance of increasing functions
Good description of orbits of upper half plane under $SL_2 (Z)$
Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$

This is a Homework Question.

I am required to give a Combinatorial proof for the following.

$$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$

- Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
- Show that $\sum\limits_{k=0}^n\binom{2n}{2k}^{\!2}-\sum\limits_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$
- Combinatorial Proof
- Calculating $\sum_{k=1}^nk(k!)$ combinatorially
- Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$
- Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

Hint given is : Show that $n!S(m,n)$ equals the number of onto functions $f\colon A \rightarrow B$ when $ |A|=m$ and $|B|=n. $

There were some other combinatorial proof questions on the assignment which I found easier to do but this one not so much. Could use help.

- Generating function: Probability regarding coin toss
- A binomial identity
- Combinatorics for a 3-d rotating automaton
- How many shapes can one make with $n$ square shaped blocks?
- Prove an identity in a Combinatorics method
- Prove $\sum\limits_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$ (a.k.a. Hockey-Stick Identity)
- Proof of $\sum_{0 \le k \le a} {a \choose k} {b \choose k} = {a+b \choose a}$
- number of combination in which no two red balls are adjacent.
- Coupon Collector Problem - expected number of draws for some coupon to be drawn twice
- Identical balls arrangement in a circle

Let $T$ denote the set of functions from $f:A\to B$ where $|A|=m$ and $|B|=n$ and $$S=\{f\in T \mid f \text{ is surjective}\}$$

If $f$ is surjective, then $f^{-1}(b)$ is non-empty for all $b\in B$. There are $S(m,n)$ many ways, to partition $m$ elements into $n$ non-empty set. For each such partition $A_1,\dots, A_n$, there are $n!$ ways to assign the pre-images $f^{-1}(b_1),\dots,f^{-1}(b_n)$, so

$$|S| = n!S(m,n)$$

Now count the elements of $S$ again in an other way: For each $b\in B$, define

$$M_b = \{ f: A\to B \mid f^{-1}(b)=\varnothing\}$$

Then

$$S = T \setminus\bigcup\limits_{b\in B}M_b$$

Now use the Inclusion-exclusion principle to calculate $|S|$.

- Chinese Remainder theorem with non-pairwise coprime moduli
- Every ideal of an algebraic number field can be principal in a suitable finite extension field
- What are dirichlet characters?
- Every planar graph has a vertex of degree at most 5.
- Intuitive proofs that $\lim\limits_{n\to\infty}\left(1+\frac xn\right)^n=e^x$
- Problem on idempotent finitely generated ideal
- Exponential decay estimate for $(x,t) \in U_T$
- On the meaning of being algebraically closed
- Proving $n! \ge 2^{n-1 }$for all $n\ge1 $by mathematical Induction
- Books on Axiom of Dependent Choices?
- Translation-invariant metric on locally compact group
- What is reductive group intuitively?
- Inverse image of prime ideal in noncommutative ring
- Prove that $\lim_{x \rightarrow 0} \mathrm {sgn} \sin (\frac{1}{x})$ does not exist.
- maximum estimator method more known as MLE of a uniform distribution