# Singularities in Pascal Triangle

I try to compute the numbers in the Pascal Triangle, but on some positions (X,Y), the pascal triangle has 0, instead of the sum of P(X, Y-1) + P(X-1, Y-1) , each time when X is in relation R with Y. For example, I want P(X,Y) = 0 when R(X,y) is defined as "X is prime and Y = 2*X".

Obviously, if I am asked to compute the Pascal Triangle, I do not recursivelly compute the sums for each pair, but I compute the combinations(X,Y).

I wish to ask whether the methods of analytic combinatorics can help to solve this problem -- to find the values using some analytical formula instead of recurrence, or ad-hoc methods.

ps: EDIT TO CLARIFY

I want to compute the function c defined so:

if R(i,j):
c[i][j] = 0
else:
c[i][j] ← c[i-1][j-1] + c[i-1][j]

and at limits as the pascal triangle.


where R is a relation of i and j, whatever R may be.

As you can see, this function is almost identical with Pascal triangle (it counts the number of paths from (0,0) to (i,j) -- but I contraint it not to pass over the position (i,j)).

EDIT:

Can you write a generating function that can model this problem ? I never solved a problem of analytic combinatorics of this difficulty, and my only question is if somebody can help me how to write a generating function , which can be computed fast (if possible).

-
Not so clear about what you want. – eccstartup Jun 30 '13 at 12:07
Are you asking for a way of computing the $y$'th entry of the $x$'th row of the Pascal triangle? By the binomial theorem, that entry is simply given by a binomial coefficient. – fuglede Jun 30 '13 at 12:14
OK, so, you are trying to compute a function of two variables, $P(m,n)$, and you insist that if $m$ is prime and $n=2m$ then $P(m,n)=0$ --- but you need more than that to specify your function. It seems that you also want $P(m,n)=P(m,n-1)+P(m-1,n-1)$ when that's not ruled out by the first consideration, but do you also want some boundary conditions? You don't have a function without them. – Gerry Myerson Jun 30 '13 at 13:05
I edited the question to clarify your points. Thanks for questions. – alinsoar Jun 30 '13 at 13:18
You still didn't set any boundary conditions. Think about the Fibonacci numbers: $x_{n+1}=x_n+x_{n-1}$ isn't enough, you need $x_1$ and $x_2$. For the usual Pascal triangle, you need the 1s at the ends of the rows. What are your boundary conditions? – Gerry Myerson Jul 1 '13 at 11:15

Here is the question I think you are trying to ask:

For nonnegative integers $m$, $n$, how many lattice paths are there from $(0,0)$ to $(m,n)$, each step going one to the right or one up, if you're not allowed to go through some particular point $(i,j)$.

And what's wanted by way of an answer is a simple formula that does not require working through all the steps of a recursion.

Without the restriction, the answer is (as OP knows) $m+n\choose m$. So, we just have to subtract all the paths that go to $(m,n)$ by way of $(i,j)$, and that's $${i+j\choose i}{m+n-i-j\choose m-i}$$ So, the answer is $${m+n\choose m}-{i+j\choose i}{m+n-i-j\choose m-i}$$

Now it seems OP may be interested in paths that avoid not just one point but all the points satisfying some relation $R(i,j)$. It should be possible to extend the formula to this case via the Principle of Inclusion-Exclusion.

-
A special case was discussed at math.stackexchange.com/questions/78109/… – Gerry Myerson Jul 2 '13 at 10:40
Exactly: this is the problem I want to solve. There are many zeros, not only 1 :). For 1 point, and 2 points, it is clear how to do. I have a case with N points, N could be very large. – alinsoar Jul 2 '13 at 10:56
As I tried to say in initial post, I need a general case, and my question is whether there is some advanced method (of analytic combinatorics -- integrals, derivatives, etc) , because I also solved the problem via _brute-force_ with the computer. – alinsoar Jul 2 '13 at 10:59
It seems to me that with $N$ points to avoid you may need to do $2^N$ computations, which will not be feasible. I suspect you are out of luck. – Gerry Myerson Jul 2 '13 at 11:00
And the position of points (id.est the relation) can vary, it is not fixed. – alinsoar Jul 2 '13 at 11:01