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
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
L13
exp_multiply (inf_list f, inf_list g) = inf_listexp_mult
L26
exp_mult (inf_list f, int k, inf_list g, int l) = inf_listthe same, but start in degrees |k,l|, and return only relevan part
exp_divide
L40
exp_divide (inf_list f, inf_list g) = inf_listexp_diff
L56
exp_diff (inf_list f) = inf_listexp_substitute
L58
exp_substitute (inf_list g) = (inf_list->inf_list)f->f[X:=g]
exp_comp_inverse
L81
exp_comp_inverse (inf_list g) = inf_liste.g., exp_comp_inverse([0,1,-1].extend_0) solves $f-f^2/2=X$L102
sin
L106
sin : 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
L107
cos : exp_diff(sin)tan
L108
tan : exp_divide(sin,cos)count_permutations_with_cycles
L114
count_permutations_with_cycles ([int] L) = inf_listfor 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
L127
exp_of_exponential_series (inf_list S) = inf_listHere is more general exponentiation
we must avoid having |memoize| inside |@ inf_node:| bodyL143
count_permutations_with_cycles
L156
count_permutations_with_cycles (inf_list allowed_cycles) = inf_listas 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
L175
derangement_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).