0
$\begingroup$

This is related to an ongoing event. It involves generating the following series : http://oeis.org/A008826

The generating Function as given in the above link is :

A(n,x) = Sum{ Stirling2(n,k) * A(k,x) * x } for k : 0 to n-1

where stirling2(n,k) is : http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

I have made a simple loop to calculate the small A[n,k] :

for(int k = 0;k<n;k++)
    a(n,x) += stirling(n,k)*a(k,x)*x;

where stirling(n,k) is calculated by

stirling(n,k) = (stirling(n-1,k)*k)+stirling(n-1,k-1)

i have set

stirling(0,0) = 1
stirling(i,0) = stirling(0,i) = 0
A(1,i) = 1

The values of the Stirling Numbers being generated are correct. But the values for A(n,x) being generated do not match http://oeis.org/A008826/table

The output I am receiving is :

1       1       1       1       1   
1       2       3       4       5   
4       14      30      52      80  
32      198     606     1364    2580    
436     4722    20568   60004   139380

Did I get the function wrong ? Why isn't my output matching the one given in the link ? Am I interpreting the GF incorrectly ?

EDIT

I was finally able to calculate A(n;x) for small as well as large numbers. My final recurrence relation has come down to :

F(n) = A(n)*B(n) + (nC2 * F(n-1))

Last step to solve the recurrence relation :)

$\endgroup$
3
$\begingroup$

You're on the right track; you are just interpreting the a(n,x) incorrectly. The a(n,x) are polynomials - and the numbers in (n-1)st row of the triangular array are the coefficients by x, x^2, ... , x^n in a(n,x).

For instance, the polynomial a(4,x) is x+13x^2+18x^3, corresponding to the third row (namely 1 13 18) of the triangular array.

$\endgroup$
  • $\begingroup$ Understood. It makes a lot more sense now :) $\endgroup$ – Kyuubi Jun 15 '13 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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