0
votes
0answers
16 views

The number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit ...
1
vote
0answers
20 views

Ehrhart Polynomials Modulo Prime Integers

Are there any results known about computing Ehrhart Polynomials modulo prime integers?
2
votes
1answer
58 views

Lattice Path Spaces.

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to ...
0
votes
0answers
24 views

Finding integer vectors in the column space of a matrix

Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given. Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$ ...
1
vote
1answer
49 views

Counting sum of lattice points

Assume a set $S$ with $|S|$ entries. Indeed, $S$ is the set of lattice points inside a $k$-sphere. Assume $V=S\oplus S$ where $\oplus$ is the Minkowski sum of two sets. Do you know any lower bound on ...
2
votes
1answer
94 views

number of lattice points in an n-ball

I have faced a problem in my work and I will appreciate any hint/reference as I am not much into the lattice problems. Assume an n-dimensional lattice $\Lambda_n$ with generator matrix $G$. Note that ...
0
votes
0answers
20 views

Show transformation of lattice paths is a bijection

How do I show that the transformation (switching head and tail of a path) is indeed a bijection from lattice paths with excess k to lattice paths with excess k-1. I need to describe the inverse ...
12
votes
2answers
358 views

Show $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ by block-walking interpretation of Pascal's triangle

A combinatorial proof for the identity $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$ is the following "committee" argument, which seems the most common. There are $\binom{n}{k}$ ...
3
votes
1answer
94 views

Bounding the density of finite coprime sets

I am currently running into a problem related to coprime numbers. Consider a set of $d$-dimensional integer vectors, $z \subset \mathbb{Z}^d$ such that each component $z_i$ is bounded by another ...
0
votes
1answer
21 views

What's the maximum number of sums of $ak_1,..,ak_m, b\ell_1,…,b\ell_m$ needed to solve for $a$ or $b$?

Given a set of integer multiples of $a$ and $b$, $ak_1,..,ak_m, b\ell_1,...,b\ell_m$, what is the maximum number of finite sums of the multiples you can create such that no sum of all multiples of $a$ ...
0
votes
2answers
394 views

Lattice Paths from $(1, 1) \to (x, y)$

Moderator Note: This is a current contest question on Brilliant.org. Let $S$ be the set of $\{(1,1), (1,−1), (−1,1), (1,0), (0,1)\}$-lattice paths which begin at $(1,1),$ do not use the same ...
1
vote
2answers
549 views

Monotonic Lattice Paths and Catalan numbers

Can someone give me a cleaner and better explained proof that the number of monotonic paths in an $n\times n$ lattice is given by ${2n\choose n} - {2n\choose n+1}$ than Wikipedia I do not understand ...
2
votes
0answers
43 views

When does a simplex have an interior lattice point?

Given $r$ vectors $v_1, \dots, v_r$ in $\mathbb{Z}^n$, is there an easy way (in terms of the entries of the $v_i$) to determine if there is a point of $\mathbb{Z}^n$ in the interior of the simplex ...
0
votes
2answers
164 views

Counting lattice points interior to a polygon

If I define an integer lattice $\Lambda \subseteq \mathbb{Z}^2$ with a basis given by $$\omega_{1} = a \hat{i} + b\hat{j}, \;\;\; \omega_{2} = -b \hat{i} + a\hat{j}$$ How can I count how many lattice ...
2
votes
2answers
3k views

Lattice paths and Catalan Numbers

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a ...
4
votes
2answers
207 views

Guaranteeing an integer lattice point centroid

My question is this: Writing $n(4)$ to be the minimum number of integer lattice points in the plane so that some four of them must determine an integer lattice point centroid, show that $n(4)=13$. I ...
2
votes
2answers
188 views

A problem involving the lattice grid.

Suppose that $22$ points are arbitrarily chosen from a $7\times 7$ lattice grid. We are to prove that there exists at least one rectangle in any $4$ points chosen from the above $22$. A general ...
2
votes
0answers
51 views

A certain labeling of lattice points on the plane [duplicate]

Possible Duplicate: A stronger version of discrete “Liouville’s theorem” Let each lattice point of the plane be labeled by a positive real number . Each of these numbers is the arithmetic ...
0
votes
1answer
314 views

Proving Binomial Identities Using Bijections To Lattice Paths

How can I derive a bijection to show that the following equality holds? $2\displaystyle\sum\limits_{j=0}^{n-1} \binom{n-1+j}{j} = \binom{2n}{n}$ In class, we've been deriving bijections using ...
1
vote
1answer
147 views

Number of matrices with weakly increasing rows and columns

I'm curious as to how many matrices there are of size $m \times n$ with elements of the set $\{1, \ldots , k\}$ such that each row and column is weakly increasing? The answer should be expressable as ...
2
votes
1answer
135 views

Bounding the number of integer solutions of the following inequality

Let $r\geq 1$ be a real number, $-1\leq x\leq 1$ a real number and $y>2$ a real number. We consider this data to be fixed. How can I obtain an upper bound on the number of $(a,b,c,d)\in ...
0
votes
1answer
52 views

If E is a subset of a lattice closed under addition then is the intersection of E with the opposite of some translate finite?

this seems intuitive to me but I'm struggling to prove it (is it false?). Let $E$ be a subset of a lattice (free abelian group of finite rank) closed under addition, containing the origin and such ...
3
votes
1answer
2k views

How can I find the number of the shortest paths between two points on a 2D lattice grid?

How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this? Eg. The shortest path between ...
3
votes
1answer
280 views

Closest point to line in lattice

Given an $n$ x $n$ integer grid, I look at all possible lines through two grid points and I am interested in the minimum distance from any grid point (not on the line) to any line. I my guess is that ...
1
vote
1answer
695 views

Lattice Paths to $(2n, 2n)$ that do not go through $(n,n)$

I know that from the origin to $(x,y)$ there are $${x+y \choose x} = {x+y \choose y}$$ Lattice paths. The question is finding the number of paths from the origin to $(2n, 2n)$ not passing through ...
0
votes
1answer
379 views

Lattice Paths Question

You know, how we can have lattice paths, where we can move either one block north, or one block east, and we have the find all the possible ways of reaching the point (x.y) from (0,0). That is ...
4
votes
1answer
244 views

Proving this identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$ using lattice paths

How can I prove the identity $\sum_k\frac{1}{k}\binom{2k-2}{k-1}\binom{2n-2k+1}{n-k}=\binom{2n}{n-1}$? I have to prove it using lattice paths, it should be related to Catalan numbers The $n$th ...
8
votes
1answer
336 views

“Center-of-Mass” of lattice polygons (generalization of Pick's theorem)

Call a polygon with integer coordinates (in the Euclidean plane) a 'lattice polygon'. Pick's Theorem allows you to efficiently compute the number of lattice points inside this polygon given just its ...
2
votes
1answer
128 views

Mathematical Results from Counting Points in Lattices

I'm preparing a talk on lattice point enumeration in polytopes (Ehrhart-Macdonald Theory), and I'd like to have an introduction with a few motivational problems/results which arise from the ...