ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 08 Jun 2022 03:09:52 +0200recurrence relationhttps://ask.sagemath.org/question/62494/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()Wed, 18 May 2022 14:32:15 +0200https://ask.sagemath.org/question/62494/recurrence-relation/Answer by Max Alekseyev for <p>I have the following recurrence relation (which gives the cycle index of the symmetric group), where $a_k$ are just indeterminates:</p>
<p>$Z_0 := 1, \quad Z_n := \frac1n \sum_{k=1}^n a_k Z_{n-k} \quad \forall n>0$</p>
<p>I tried the following, but it doesn't work:</p>
<pre><code>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)
</code></pre>
<p>What am I doing wrong?</p>
<p><strong>Edit</strong>: Based on dan_fulea's answer, I found a way how to put <code>a</code> inside <code>Z(n)</code>:</p>
<pre><code>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()
</code></pre>
https://ask.sagemath.org/question/62494/recurrence-relation/?answer=62770#post-id-62770First, 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
Wed, 08 Jun 2022 03:09:52 +0200https://ask.sagemath.org/question/62494/recurrence-relation/?answer=62770#post-id-62770Answer by dan_fulea for <p>I have the following recurrence relation (which gives the cycle index of the symmetric group), where $a_k$ are just indeterminates:</p>
<p>$Z_0 := 1, \quad Z_n := \frac1n \sum_{k=1}^n a_k Z_{n-k} \quad \forall n>0$</p>
<p>I tried the following, but it doesn't work:</p>
<pre><code>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)
</code></pre>
<p>What am I doing wrong?</p>
<p><strong>Edit</strong>: Based on dan_fulea's answer, I found a way how to put <code>a</code> inside <code>Z(n)</code>:</p>
<pre><code>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()
</code></pre>
https://ask.sagemath.org/question/62494/recurrence-relation/?answer=62496#post-id-62496I 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".
Wed, 18 May 2022 15:11:05 +0200https://ask.sagemath.org/question/62494/recurrence-relation/?answer=62496#post-id-62496Comment by Thrash for <p>I tried:</p>
<pre><code>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()
</code></pre>
<p>Then:</p>
<pre><code>for n in [0..5]:
print(f'Z({n}) = {Z(n)}')
</code></pre>
<p>delivers:</p>
<pre><code>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
</code></pre>
<p>Which are the differences? First, the $a$-variables are a constant w.r.t. the loop, so just put it outside.
Then the used <code>sum</code> method is the sum for the elements of a given list. Please compare:</p>
<pre><code>sage: sum([1, 4, 6, 10, 111])
132
sage: var('k,n');
sage: sum(binomial(n, k), k, 1, n)
2^n - 1
</code></pre>
<p>The first sum is the sum of a list, known in the moment of applying <code>sum</code> on it. It is a python-specific function. The second <code>sum</code> is a symbolic sum, an invention of sage & CO - and we need the summation to be done w.r.t. specific variables <code>k,n</code> to be introduced as such in advance, and this <code>sum</code> makes sense only for "known symbolic formulas". </p>
https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62515#post-id-62515OK, 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]`).Thu, 19 May 2022 00:36:13 +0200https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62515#post-id-62515Comment by Thrash for <p>I tried:</p>
<pre><code>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()
</code></pre>
<p>Then:</p>
<pre><code>for n in [0..5]:
print(f'Z({n}) = {Z(n)}')
</code></pre>
<p>delivers:</p>
<pre><code>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
</code></pre>
<p>Which are the differences? First, the $a$-variables are a constant w.r.t. the loop, so just put it outside.
Then the used <code>sum</code> method is the sum for the elements of a given list. Please compare:</p>
<pre><code>sage: sum([1, 4, 6, 10, 111])
132
sage: var('k,n');
sage: sum(binomial(n, k), k, 1, n)
2^n - 1
</code></pre>
<p>The first sum is the sum of a list, known in the moment of applying <code>sum</code> on it. It is a python-specific function. The second <code>sum</code> is a symbolic sum, an invention of sage & CO - and we need the summation to be done w.r.t. specific variables <code>k,n</code> to be introduced as such in advance, and this <code>sum</code> makes sense only for "known symbolic formulas". </p>
https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62513#post-id-62513How 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]`.Thu, 19 May 2022 00:24:30 +0200https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62513#post-id-62513Comment by Thrash for <p>I tried:</p>
<pre><code>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()
</code></pre>
<p>Then:</p>
<pre><code>for n in [0..5]:
print(f'Z({n}) = {Z(n)}')
</code></pre>
<p>delivers:</p>
<pre><code>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
</code></pre>
<p>Which are the differences? First, the $a$-variables are a constant w.r.t. the loop, so just put it outside.
Then the used <code>sum</code> method is the sum for the elements of a given list. Please compare:</p>
<pre><code>sage: sum([1, 4, 6, 10, 111])
132
sage: var('k,n');
sage: sum(binomial(n, k), k, 1, n)
2^n - 1
</code></pre>
<p>The first sum is the sum of a list, known in the moment of applying <code>sum</code> on it. It is a python-specific function. The second <code>sum</code> is a symbolic sum, an invention of sage & CO - and we need the summation to be done w.r.t. specific variables <code>k,n</code> to be introduced as such in advance, and this <code>sum</code> makes sense only for "known symbolic formulas". </p>
https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62507#post-id-62507Thank 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`.Wed, 18 May 2022 22:04:59 +0200https://ask.sagemath.org/question/62494/recurrence-relation/?comment=62507#post-id-62507