Intereting Posts

Subjects studied in number theory
Correspondences $f: X \to 2^Y$
Prove that every element of a finite group has an order
probability question (“birthday paradox”)
Show that $(1+\frac{x}{n})^n \rightarrow e^x$ uniformly on any bounded interval of the real line.
Is there a name for the group of complex matrices with unimodular determinant?
Finding a pair of functions with properties
Let $H$ be a normal subgroup of index $n$ in a group $G$. Show that for all $g \in G, g^n \in H$
Huffman optimal code
The value of $\sqrt{1-\sqrt{1+\sqrt{1-\sqrt{1+\cdots\sqrt{1-\sqrt{1+1}}}}}}$?
there exist infinite many $n\in\mathbb{N}$ such that $S_n-<\frac{1}{n^2}$
Coefficient of det($xI+A$)
Finding the basis of a null space
Min/max of a continuous function
Show that this function is entire

In a race there are n horses.In the race more than one horse may get the same position. For example, 2 horses can finish in 3 ways.

- Both first
- horse1 first and horse2 second
- horse2 first and horse1 second

In how many ways,the race can finish so that a particular horse can never be first.If f(n) is the number of ways, is there any recurrence relation to get f(n).

- Why $0!$ is equal to $1$?
- Prove $\sum_{k=0}^{58}\binom{2017+k}{58-k}\binom{2075-k}{k}=\sum_{k=0}^{29}\binom{4091-2k}{58-2k}$
- Finding coefficient of generating function
- Deriving the formula for the Möbius function?
- If $|A| > \frac{|G|}{2} $ then $AA = G $
- Lattice paths and Catalan Numbers

- Cover $\mathbb{R}^3$ with skew lines
- How many entries in $3\times 3$ matrix with integer entries and determinant equal to $1$ can be even?
- Combinatorics - How many numbers between 1 and 10000 are not squared or cubed?
- Proof of $k {n\choose k} = n {n-1 \choose k-1}$ using direct proof
- $x_1+x_2+\cdots+x_n\leq M$: Cardinality of Solution Set is $C(M+n, n)$
- Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges.
- Thue-Morse sequence cube-freeness proof from the Book
- Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.
- (Combinatorial) proof of an identity of McKay
- Sum of matrix vector products

Let $g(h,p)$ be the number of ways that $h$ horses can be ordered in $p$ positions. Then consider introducing an extra horse: it go in one of the $p$ existing positions of $h-1$ horses or in one of the gaps between the positions or before or after all the $p-1$ positions of $h-1$ horses. This leads to the recurrence $$g(h,p)= kg(n-1,p)+kg(n-1,p-1)$$ starting at $g(1,p)=0$ except $g(1,1)=1$. This gives a table of numbers which are in fact factorials multiplied by Stirling numbers of the second kind.

So for $h$ horses, the number of possibilities is the sum of these, e.g. $\displaystyle G(h)=\sum_{p=1}^h g(h,p)$. These are called Fubini numbers or ordered Bell numbers.

But you want to exclude a particular horse from being first alone or equal first. The number of cases where it would be first alone among $h$ horses is equal to the total number of cases with $h-1$ horses and (assuming there is more than one horse) the number of cases where it would be equal first among $h$ horses is also equal to the total number of cases with $h-1$ horses. So subtract these from the total with $h$ horses to get $$f(h)=G(h)-2G(h-1)$$ and for the special case of $h=1$ see that obviously $f(1)=0$ since the single horse must come first.

**Possible Outline**: Let $N(n)$ be the number of possible positions for $n$ horses (not worrying about making sure that one doesn’t come in first). Define $N(0)=1$. Let’s start counting $N(1) = 1$ clearly. $N(2) = 3$ since both could tie for first, horse A could win and B lose, or B wins and A loses. $N(3) = {{3}\choose{0}}N(0) + {{3}\choose{1}}N(1) + {{3}\choose{2}}N(2)$ because we have that of the $n=3$ horses, we can rearrange the $k = 0, 1, 2$ horses that don’t win in $N(k)$ ways.. Continuing you will find that $$N(n) = \sum\limits_{k=0}^{n-1} {{n}\choose{k}} N(k).$$ Now, if you ask how many of those $N(n)$ arrangements have it so that horse A doesn’t win, it seems you will find $$f(n) = N(n) – 2N(n-1)$$ where $2N(n-1)$ is the number of ways where horse A does win. Indeed, there are $N(n-1)$ ways to arrange the $n-1$ horses that aren’t horse A if horse A is the unique winner, and there are $N(n-1)$ ways to arrange the horses that aren’t horse A if horse A is not the unique winner.

Let’s say there’re $n$ horses and we don’t want horse *pony* to be the first.

Let’s first define $g(k,n)$ which is the number of all possibilities for the $n$ horses to take positions, and they all got ranks from $1$ to $k$. $g(k,n)$ is exactly equal to $k^n – k\times (k-1)^n + \binom k 2 \times (k-2)^n – \dots = \sum_{i=0}^{k}{(-1)^i \binom k i (k-i)^n}$ by inclusion-exclusion principle.

Now the problem is easy. First order the other $n-1$ horses, and take the position of *pony* at last. If the other $n-1$ horses take rank from $1$ to $k$ their are $2k-1$ possible position for *pony* not to be on the first. Therefore, $f(n)=\sum_{k=1}^{n-1}{(2k-1)g(k,n-1)} = \sum_{k=1}^{n-1}{\Big( (2k-1)\sum_{i=0}^{k}{(-1)^i \binom {k} i (k-i)^{n-1}}\Big)}$

- Some co-finite subsets of rational numbers
- Why does $\sin^{-1}(\sin(\pi))$ not equal $\pi$
- Factorize polynomial over $GF(3)$
- Solving the Diophantine Equation $2 \cdot 5^n = 3^{2m} + 1$ over $\mathbb{Z}^+$.
- Uses of ordinals
- On Boyd et al.'s convergence analysis of ADMM: Why do we need the convexity assumption?
- polynomial converges uniformily to analytic function
- The adjoint of finite rank operator is finite rank
- What is so special about triangles?!
- How to compute homography matrix H from corresponding points (2d-2d planar Homography)
- What are or where can I find style guidelines for writing math?
- Ramification in a tower of extensions
- Proving a set is uncountable
- categorical interpretation of quantification
- Describing the ideals for which $\operatorname{dim}_F(F/I) = 4$