Intereting Posts

How to prove $\forall Y \subset X \ \forall U \subset X \ (Y \setminus U = Y \cap (X \setminus U))$?
Infinite intersection between a arbitrary set of integers and a set of floor powers
Checking if the Method of Moments and Maximum Likelihood Estimators are biased and/or consistent
Integrating $\rm x^ae^{-bx}$.
Create function F() from Points
What is the solution of cos(x)=x?
Prove $\frac{|a+b|}{1+|a+b|}<\frac{|a|}{1+|a|}+\frac{|b|}{1+|b|}$.
If $a$ is a real number then is $\sqrt{a^2}$ equal to $a$ or plus minus $a$?
Two players placing coins on a round table with the goal of making the last move
What is the inverse cycle of permutation ?
Recognizing and Using Chaitin's Constant
Does there exist a matrix $P$ such that $P^n=M$ for a special matrix $M$?
Prove that, for $p > 3$, $(\frac 3p) = 1$ when $p \equiv 1,11 \pmod{12}$ and $(\frac 3p) = -1$ when $p \equiv 5,7 \pmod{12}$
How to calculate gradient of $x^TAx$
Prove that if $\sum a_n$ converges, then $na_n \to 0$.

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.

- Graph Theory book with lots of Named Graphs/ Graph Families
- Proof of existance of Eulerian cycle in directed graph
- Cover times and hitting times of random walks
- How does Tree(3) grow to get so big? Need laymen explanation.
- Prove that an algorithm that generates a stable set of a graph can be used in any graph for generating a stable set of maximum cardinal.
- Prove that a simple planar bipartite graph on $n$ nodes has at most $2n-4$ edges.

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$

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}$).

- Trees whose complement is also a tree
- Ramsey Number R(4,4)
- Rank of an interesting matrix
- Edge-coloring of bipartite graphs
- What structure does the set of all the matchings in a graph have?
- How many directed graphs of size n are there where each vertex is the tail of exactly one edge?
- Shortest Path with odd number of “Green” vertices
- How many possible DAGs are there with $n$ vertices

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)}$$

- Example of a non-separable normal extension
- $a^m+k=b^n$ Finite or infinite solutions?
- Question about soluble and cyclic groups of order pq
- For two problems A and B, if A is in P, then A is reducible to B?
- What are the differences between rings, groups, and fields?
- Solution Technique to Optimize Sets of Constraint Functions with Objective Function that is Heaviside Step Function
- For what value of $(a+b)$ will all roots of $f(x)=x^4-8x^3+ax^2+bx+16$ be positive?
- Prove that: $ \cot7\frac12 ^\circ = \sqrt2 + \sqrt3 + \sqrt4 + \sqrt6$
- Order of $\phi(g)$ divides the order of $g$
- Proof that the sum of two Gaussian variables is another Gaussian
- What did Johann Bernoulli wrong in his proof of $\ln z=\ln (-z)$?
- Radii of convergence for complex series
- Simplifying $\sum_{i=0}^n i^k\binom{n}{2i+1}$
- Why is $\mathfrak{sl}(n)$ the algebra of traceless matrices?
- Show that $\det{(A + sxy^*)}$ is linear in $s$