Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

I ask if the analytic combinatorics can help, instead of using ad-hoc mathematical ideas.

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

share|improve this question
    
Not so clear about what you want. –  eccstartup Jun 30 '13 at 12:07
1  
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
show 3 more comments

1 Answer

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.

share|improve this answer
    
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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.