Intereting Posts

Completness and Set of Result of One Set ?!?
Global sections on quasi coherent sheaves on affine scheme
Why do books titled “Abstract Algebra” mostly deal with groups/rings/fields?
Is multiplication the only operation that satisfies the associative, commutative and distributive law?
Local diffeomorphism is diffeomorphism provided one-to-one.
Prove that $2^{n(n+1)}>(n+1)^{n+1}\left(\frac{n}{1}\right)^n\left(\frac{n-1}{2}\right)^{n-1}\cdots \left(\frac{2}{n-1}\right)^{2}\frac{1}{n}$
Use mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes.
Examples of perfect sets.
A problem for the New Year
Why is $\sum_{n=-\infty}^{\infty}\exp(-(x+n)^2)$ “almost” constant?
Cute Determinant Question
Intuitive explanation of variance and moment in Probability
Evaluate $\int_0^1 \frac{\log \left( 1+x^{2+\sqrt{3}}\right)}{1+x}\mathrm dx$
Equation to check if a set of vertices form a real polygon?
Why is the image of a smooth embedding f: N \rightarrow M an embedded submanifold?

Consider an $h \times h$ upright square lattice, where a point is defined by $(x,y)$, $x,y \in [0,h-1]$. A valid path starts from the left boundary, $(0,a)$, $ a \in [0,h-1]$ and ends to the right boundary $(h-1,b)$, $ b \in [0,h-1]$. Allowed moves are:

- Diagonal, such as $(0,0) \rightarrow (1,1)$, or
- To the right, such as $(0,0) \rightarrow (1,0)$.

Vertical movement or any movement to the left is not valid.

What is the total number of all these paths? Its possible to calculate the paths programmatically up to a certain $h$ (after $h=8$ it becomes really slow). I’m looking for a closed form expression. Here are the number of paths for $h=2,\ldots,7$

- Calculating probability with n choose k
- combinations groups question
- Probability of random integer's digits summing to 12
- The probability that each delegate sits next to at least one delegate from another country
- How to distribute $k$ distinct items into $r$ distinct groups with each groups receiving $a (=k-n)$ prizes at most?
- Subset of natural numbers such that any natural number except 1 can be expressed as sum of two elements

Table 1:

- h=2,
**4**paths - h=3,
**17**paths - h=4,
**68**paths - h=5,
**259**paths - h=6,
**950**paths - h=7,
**3387**paths

Now consider we can move on all the diagonal axes. For example consider an $4\times 4$ lattice. From $(0,0)$ we can go to $(1,0)$, $(1,1)$, $(1,2)$ or $(1,3)$. Lets denote these diagonal moves with *$a$-diagonal*. Therefore, $(0,0) \rightarrow (1,0)$ is a $0$-diagonal move, $(0,0) \rightarrow (1,1)$ is a $1$-diagonal move, $(0,0) \rightarrow (1,2)$ is a $2$-diagonal move, $(0,0) \rightarrow (1,3)$ is a $3$-diagonal move, etc.

Denote the set of all paths that start from the left boundary $(0,a)$ and end to the right boundary $(h-1,b)$, $ b \in [0,h-1]$, and have at least one $a$-diagonal move but not an $(a+1)$-diagonal move with $\mathcal{B}_a$. The problem statement is: **Calculate the number of paths in each $\mathcal{B}_0, \mathcal{B}_1,\ldots,\mathcal{B}_{h-1}$**.

(Note that the numbers in Table 1 give $\mathcal{B}_0 + \mathcal{B}_1$). The following table shows the values for $h=2$ to $h=7$:

Any hint on how to approach this would be greatly appreciated.

**Edit**: The movitation for this problem is to calculate the number of piecewise linear functions $f:[0,1]\rightarrow [0,1]$ that have a maximum derivative of 0 (given by $\mathcal{B}_0$), 1 (given by $\mathcal{B}_1$), $\ldots$, $h-1$ (given by $\mathcal{B}_{h-1}$).

- Number of ways to put N indistinct objects into M indistinct boxes
- Maximum no.of edges in a bipartite graph
- Losing at Spider Solitaire
- Maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle
- Proving the total number of subsets of S is equal to $2^n$
- How many values of $2^{2^{2^{.^{.^{.^{2}}}}}}$ depending on parenthesis?
- What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?
- How to teach mathematical induction?
- Product of repeated cosec.
- How many entries in $3\times 3$ matrix with integer entries and determinant equal to $1$ can be even?

The only real difficulty here is producing a nice formula.

Write down a row of $h$ ones: $$1\quad1\quad1\quad\ldots\quad1\quad1\quad1$$

Then write down, under each number, the sum of the two/three numbers directly above or one place to the side: $$2\quad3\quad3\quad\ldots\quad3\quad3\quad2$$

And repeat this $h-1$ times. The final row will sum to the number desired. So you can find even by hand that for $h=8$, the answer is $11814$. Your more general problem can be solved similarly, summing the three/four/five nearest numbers instead.

The OEIS link given in the comments has a few formulas. The first one is in terms of Motzkin numbers, which are themselves quite difficult to give a closed formula for. The simplest recurrence is one by Václav Kotěšovec: $$a_n = \frac{(10n^2-39n+23)a_{n-1}-3(2n^2-n-9)a_{n-2}-9(n-3)(2n-5)a_{n-3}}{(n-1)(2n-7)}$$

- LambertW(k)/k by tetration for natural numbers.
- Proof of $m \times a + n \times a = (m + n) \times a$ in rings
- Proving Injectivity
- Convergence of the series $\sum_ {n\geq1} \frac {(f(n) +P(n)) \pmod {Q(n)}} {D(n)}$
- Isometric Embedding of a separable Banach Space into $\ell^{\infty}$
- Prime factorization knowing n and Euler's function
- General solution of second-order linear ODE
- Union of two vector subspaces not a subspace?
- Normal at every localization implies normal
- Partition of ${1, 2, … , n}$ into subsets with equal sums.
- Need help understanding statement of Van Kampen's Theorem and using it to compute the fundamental group of Projective Plane
- Let $R$ be a commutative ring and let $I$ and $J$ be ideals of $R$. Show $IJ$ is an ideal of $R$.
- What does this theorem in linear algebra actually mean?
- Is $\mathbb{Q}=\{a+bα+cα^2 :a,b,c ∈ \mathbb{Q}\}$ with $α=\sqrt{2}$ a field?
- How to prove a sequence of a function converges uniformly?