Documentation contents

Script File

exp-generating-series.at

some help with exponential generating series, which are lazily computed
formal series in $X^n/n!$ for $n\in\N$, with integer coefficients
Source
atlas-scripts/exp-generating-series.at (177 lines)
Definitions
13
Loads
Loaded by
none of the other all.at files

Definitions in source order

we can reuse |sum| from lazy_lists for addition of exponential series
but for multiplication we need a modification:
L9

exp_multiply

L13exp_multiply (inf_list f, inf_list g) = inf_list

exp_mult

L26exp_mult (inf_list f, int k, inf_list g, int l) = inf_list
the same, but start in degrees |k,l|, and return only relevan part

exp_divide

L40exp_divide (inf_list f, inf_list g) = inf_list

exp_diff

L56exp_diff (inf_list f) = inf_list

exp_substitute

L58exp_substitute (inf_list g) = (inf_list->inf_list)
f->f[X:=g]

exp_comp_inverse

L81exp_comp_inverse (inf_list g) = inf_list
e.g., exp_comp_inverse([0,1,-1].extend_0) solves $f-f^2/2=X$
L102

sin

L106sin : series((int n): let(q,r)=n\%2 in if r=0 then 0 else (-1)^q fi)
we can now define some trigonometric functions here; exp is just |ones|

cos

L107cos : exp_diff(sin)

tan

L108tan : exp_divide(sin,cos)

count_permutations_with_cycles

L114count_permutations_with_cycles ([int] L) = inf_list
for instance to count permutations with allowed cycles of distinct lengths
given in a list |L|, one can compute $\exp(\sum_{l\in L}{X^l\over l})$,
which by the property of the exponential can be done as follows

also in this file at line 156

exp_of_exponential_series

L127exp_of_exponential_series (inf_list S) = inf_list
Here is more general exponentiation
we must avoid having |memoize| inside |@ inf_node:| body
L143

count_permutations_with_cycles

L156count_permutations_with_cycles (inf_list allowed_cycles) = inf_list
as an example of using |exp_of_exponential_series|, consider the question of
counting permutations with a condition on the cycle length, but which is not
given by a finite list of allowed cycles (for example, any odd length cycles
are allowed). This would require an infinite product to be made in
|count_permutations_with_cycles|, and indeed infinite products can be dealt
with. But the product comes from in infinite sum under the |exp| operator, so
instead we can just produce an exponential generating series and then apply
|exp_of_exponential_series| to it. We do this here, where the argument is an
|inf_list|, supposed strictly increasing and of positive integers, that
describes the set of allowed cycle lengths.

also in this file at line 114

derangement_numbers

L175derangement_numbers : count_permutations_with_cycles(series((int n):n+2))
for example here is how to count derangements without the alternating formula
also try <number_theory.at, then |count_permutations_with_cycles(primes)|
L177

Generated from atlas-scripts at commit 7e1b958 (2026-09-17).