0

Is there recurrence relation for combinatorial objects which have root on right-hand side? I found that formula for problem in this question is of such type and want to find similar formulas and methods to obtain them and corresponding area of combinatorics. Example of triangle of numbers (from simple variant of mentioned question):

    [1]    
    [1, 4]    
    [1, 9, 16]    
    [1, 16, 49, 64]    
    [1, 25, 121, 225, 256]    
    [1, 36, 256, 676, 961, 1024]

In it $A[x][y] = A[x-1][y-1] + A[x-1][y] + 2*\sqrt{A[x-1][y-1] * A[x-1][y]}$

DSblizzard
  • 903
  • Can you give us more details of what you wish to find out? – Sean Roberson Jul 20 '17 at 18:11
  • You mean like this: https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression, the Fibonacci numbers given by a formula involving $\sqrt{5}$? – Hans Lundmark Jul 20 '17 at 18:12
  • That depends on what you mean by "combinatorial objects", what you mean by "closed form formula", what you mean by "have root" and what you mean by "right-hand side." Depending on your answers to those, the answer is probably "obviously yes," a simple example being something like "Let $T(n)$ be the number of layers needed to stack $n$ objects into a pyramid-like shape." Whether any of the examples which have roots are "interesting" to you is another question entirely. – JMoravitz Jul 20 '17 at 18:12
  • @Hans Lundmark: Sorry, I meant recursion, not closed form. – DSblizzard Jul 20 '17 at 18:16
  • Related question: https://math.stackexchange.com/questions/124560/how-to-approach-2-dimensional-recurrence-relations – DSblizzard Jul 20 '17 at 19:18

1 Answers1

1

The numbers $A[x,y]$ are the squares of the number of OEIS sequence A008949 which has the same recursion as Pascal's triangle for binomial coefficients. So, if you let $A[x,y]:=T[x,y]^2$, then $T[x,y]=T[x-1,y-1]+T[x-1,y]$ and the "radical" disappers. We can rewrite the recursion as $A[x,y]=A[x-1,y-1]+A[x-1,y]+2T[x-1,y-1]T[x-1,y]$ using $T[,]$.

This does not answer your question, but it is unlikely that the recurrences you want exist.

Somos
  • 35,251
  • 3
  • 30
  • 76