Ask Your Question

recurrence relation

asked 2022-05-18 14:32:15 +0200

Thrash gravatar image

updated 2022-05-19 00:41:44 +0200

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
        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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2022-05-18 15:11:05 +0200

dan_fulea gravatar image

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


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


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

edit flag offensive delete link 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.

Thrash gravatar imageThrash ( 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].

Thrash gravatar imageThrash ( 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]).

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

answered 2022-06-08 03:09:52 +0200

Max Alekseyev gravatar image

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:

def Z(n):
    R.<a> = InfinitePolynomialRing(QQ)
    if n==0:
    return sum( a[k] * Z(n-k) for k in (1..n) ) / n
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2022-05-18 14:32:15 +0200

Seen: 215 times

Last updated: Jun 08 '22