# recurrence relation

I have the following recurrence relation (which gives the cycle index of the symmetric group), where $a_k$ are just indeterminates:

$Z_0 := 1, \quad Z_n := \frac1n \sum_{k=1}^n a_k Z_{n-k} \quad \forall n>0$

I tried the following, but it doesn't work:

def Z(n):
if n == 0:
return 1
else:
a = var(','.join('a%s'%(i+1) for i in range(n)))
return 1/n*sum(a[k-1]*Z(n-k),k,1,n)


What am I doing wrong?

Edit: Based on dan_fulea's answer, I found a way how to put a inside Z(n):

def Z(n):
if n == 0:
return 1
a = var(','.join(f'a{k}' for k in [0..n]))
return 1/n * sum([ a[k] * Z(n-k) for k in [1..n] ]).expand()

edit retag close merge delete

Sort by ยป oldest newest most voted

I tried:

a = var(','.join(f'a{k}' for k in range(10)))

def Z(n):
if n == 0:
return 1
return 1/n * sum([ a[k-1] * Z(n-k) for k in [1..n] ]).expand()


Then:

for n in [0..5]:
print(f'Z({n}) = {Z(n)}')


delivers:

Z(0) = 1
Z(1) = a0
Z(2) = 1/2*a0^2 + 1/2*a1
Z(3) = 1/6*a0^3 + 1/2*a0*a1 + 1/3*a2
Z(4) = 1/24*a0^4 + 1/4*a0^2*a1 + 1/8*a1^2 + 1/3*a0*a2 + 1/4*a3
Z(5) = 1/120*a0^5 + 1/12*a0^3*a1 + 1/8*a0*a1^2 + 1/6*a0^2*a2 + 1/6*a1*a2 + 1/4*a0*a3 + 1/5*a4


Which are the differences? First, the $a$-variables are a constant w.r.t. the loop, so just put it outside. Then the used sum method is the sum for the elements of a given list. Please compare:

sage: sum([1, 4, 6, 10, 111])
132
sage: var('k,n');
sage: sum(binomial(n, k), k, 1, n)
2^n - 1


The first sum is the sum of a list, known in the moment of applying sum on it. It is a python-specific function. The second sum is a symbolic sum, an invention of sage & CO - and we need the summation to be done w.r.t. specific variables k,n to be introduced as such in advance, and this sum makes sense only for "known symbolic formulas".

more

Thank you very much! I originally wanted to put a inside because depending on n I need a_1,...,a_n. So I thought to get n first by the input and pass that information to the creation of a.

( 2022-05-18 22:04:59 +0200 )edit

How can var(','.join(f'a{k}' for k in [1..n])) be made as a list/tuple in the case n=1 so that a[0] makes sense? Because so far it gives me a1 directly, but I want something like (a1) or [a1].

( 2022-05-19 00:24:30 +0200 )edit

OK, I just do a = var(','.join(f'a{k}' for k in [0..n])) and don't use a0, then I can put that inside Z(n) (with a[k] instead of a[k-1]).

( 2022-05-19 00:36:13 +0200 )edit

First, Sage can compute cycle index out of the box, although it's expressed in terms of symmetric polynomials and so some conversion is needed - for example,

def Z(n):
ind = SymmetricGroup(n).cycle_index()
R.<a> = InfinitePolynomialRing(QQ)
return sum(prod(a[i] for i in t)*c for t,c in ind)


Second, if one wants to implement a recurrence formula, it's worth to notice that we deal with polynomials here and employ the corresponding algebraic structure. Also, to avoid recomputing the same result over and over again, it's worth to use @cached_function decorator:

@cached_function
def Z(n):
R.<a> = InfinitePolynomialRing(QQ)
if n==0:
return R.one()
return sum( a[k] * Z(n-k) for k in (1..n) ) / n

more