CYC(z,max)
CYC(z,u,max)

Cycle operator (Pólya logarithm).

Defined as $A = CYC(B) \implies A(z) = \sum_{1}^{\infty} \frac{\phi(k)}{k} log \frac{1}{1-z^k}$, or with marker $u$ for number of components: $A(z, u) = \sum_{1}^{\infty} \frac{\phi(k)}{k} log \frac{1}{1 - u^k z^k}$. Returns a SymPy :Sym object.

MSET(z,max)
MSET(z,u,max)

Multiset operator (Pólya exponential operator).

Defined as $A = MSET(B) \implies A(z) = exp(\sum_{1}^{\infty} \frac{1}{k} B(z^k))$, or with marker $u$ for number of components: $A(z, u) = exp(\sum_{1}^{\infty} \frac{u^k}{k} B(z^k))$. Returns a SymPy :Sym object.

PSET(z,max)
PSET(z,u,max)

Powerset operator (modified Pólya exponential operator).

Defined as $A = PSET(B) \implies A(z) = exp(\sum_{1}^{\infty} \frac{(-1)^{k-1}}{k} B(z^k))$, or with marker $u$ for number of components: $A(z, u) = exp(\sum_{1}^{\infty} \frac{(-1)^{k-1} u^k}{k} B(z^k))$. Returns a SymPy :Sym object.

SEQ(z)
SEQ(z, u)

Sequence operator (Pólya quasi-inverse operator).

Defined as $A = SEQ(B) \implies A(z) = \frac{1}{1 - B(z)}$, or with marker $u$ for number of components: $A = SEQ(uB) \implies A(z, u) = \frac{1}{1 - u B(z)}$ (Flajolet & Sedgewick, Fig. III.7, p. 170).

bgf_moments(bgf::Function, n::Integer)
bgf_moments(bgf::SymPy.Sym, n::Integer; z=SymPy.symbols("z"), u=SymPy.symbols("u"))

Compute exact analytical moments (mean, var, std, and total weight/count count) at size n from a Bivariate Generating Function (BGF) $A(z, u)$ where $z$ marks size and $u$ marks a combinatorial parameter $\chi$.

Uses Proposition III.2 of Flajolet & Sedgewick (Analytic Combinatorics, p. 158):

• $\mathbb{E}_n(\chi) = \frac{[z^n] \partial_u A(z, u)|_{u=1}}{[z^n] A(z, 1)}$
• $\mathbb{E}_n(\chi(\chi - 1)) = \frac{[z^n] \partial_u^2 A(z, u)|_{u=1}}{[z^n] A(z, 1)}$
• $\mathbb{V}_n(\chi) = \mathbb{E}_n(\chi(\chi - 1)) + \mathbb{E}_n(\chi) - \mathbb{E}_n(\chi)^2$

Returns a NamedTuple: (mean = ..., var = ..., std = ..., count = ...).

I_gf(z)

Integers as combinatorial structures

$I(z)= \sum_{n \geq 1} z^n = \frac{z}{1-z}$. Returns a SymPy :Sym object.

fixed_size_comps(n,k)

Compositions of size n made of k summands,

${C_n}^{k} = {n-1 \choose k -1}$

fixed_size_comps_asym(n,k)

Asymptotics for compositions of size n made of k summands,

${C_n}^{k} \sim \frac{n^{k-1}}{(k-1)!}$

partitions_asym(n,tau)

Asymptotics for partitions of size n whose summands lie in the arbitrary finite set $\tau$ (tau).

tau must be an array of integers. ${P_n}^{T} \sim \frac{1}{\tau} \frac{n^{r-1}}{(r-1)!}$

partitions_asym(n)

Asymptotics for partition of integers (EIS A000041) by Hardy and Ramanujan, later improved by Rademache

partitions_gf(z,max)

Generating function for integer partitions.

Defined as $P(z) = \prod_{m = 1}^{\infty} \frac{1}{1-z^m}$ Returns a SymPy :Sym object. Use SymPy.series to obtain counts(EIS A000041): SymPy.series(partitions_gf(z,10),z,0,8) for n up to 8.

partitions_max_r(n,r)

Number of partitions of size n whose summands lie in the set {1, 2, ... , r}

n must be an integer and r is the maximum value in the set of summands.

primes_composition_asym(n)

Asymptotics for composition of n into prime parts (EIS A023360).

$B_{n} \sim 0.30365 * 1.47622^n$

restricted_sum_comp(n,r)

Number of compositions of n with components in the set {1,2,..,r}.

r = 2 yields Fibonnaci numbers (EIS A000045): $F_{n} = F_{n-1} + F_{n-2}$. r>2 yields generalized Fibonacci numbers.

restricted_sum_comp_gf(r)

Generating function for compositions with restricted summand. Returns a SymPy :Sym object.

restricted_sum_part(n,r)

Number of partitions with components in r with restricted summand n.

n must be an integer and r must be a set of integers, like in r = [1,5,10,25] , n = 99.

restricted_sum_part_gf(r)

Generating function for partition with restricted summand. Returns a SymPy :Sym object.

catalan_factorial(n)

The n_th Catalan number. (EIS A000108)

Calculated using factorials. $C_{n} = \frac{(2n)!}{(n+1)!n!}$

general_trees(n)

The number of general trees, given by (n-1)_th Catalan number. (EIS A000108)

Calculated using binomial coefficients. $G_n = C_{n-1} = \frac{1}{n} {2n - 2 \choose n - 1}$

stirling_catalan_asym(n)

Stirling approximation for n_th Catalan number. (EIS A000108)

$C_{n} \sim \frac{4^n}{\sqrt{\pi n^3}}$

stirling_factorial_asym(n)

Stirling approximation for n! (EIS A000142)

$n! \sim \sqrt{2 \pi n} {\frac{n}{e}}^{n}$

triangulations(n)

The number of triangulations, given by the n_th Catalan number. (EIS A000108)

Calculated using binomial coefficients. A maximal decomposition of the convex (n + 2)-gon defined by the points into n triangles. $T_n = C_{n-1} = \frac{1}{n+1} {2n \choose n}$

bin_words_runs_coeff(r;n_tot=200)

Taylor series coefficient from generating function for binary words (when p=q=prob(a)=prob(b)) that never have more than r consecutive identical letters.

The number of binary words that never have more than r consecutive identical letters is found to be (set α = β = r). n_tot defaults to 200, according to the example in Flajolet & Sedgewick pag. 52

bin_words_runs_prob(k,n)

Returns probablity associatied with k-lenght double runs (or either $a$s or $b$s) in a sequence of size n (when p=q=prob(a)=prob(b)).

$W ∼= SEQ(b) SEQ(a SEQ(a) b SEQ(b)) SEQ(a).$ For instance, if n=5 and k=2, the probability of obtaining strings such as bbaab and aabba.

bin_words_with_k_occurences(k,n)

The set L of binary words that contain exactly k occurrences of the letter b

$L = SEQ(a){(b SEQ(a))}^k \implies L(z) = \frac{z^k}{{(1-z)}^{k+1}}$ For instance, among binary words with 10 letters, there are 210 words with 4 $b$s. ($[z^{10}]L(z) = 210$)

bin_words_with_k_occurences_constr(k,n,d)

The set L of binary words that contain exactly k occurrences of the letter b, constrained by the maximum distance d among occurrences

$L^{[d]} = SEQ(a){(b SEQ_{<d}(a))}^{k-1}(b SEQ(a))$.

For instance, among binary words with 10 letters, there are 45 words with 4 $b$s in which the maximum distance between $b$s is 2 (e.g.aaabababab) ($[z^{10}]L^{[2]}(z) = 45$).

longest_run_binary_asym(n)

Asymptotics for the average of the longest run of $a$s in a random binary string of length n.

$\log_2 n$ . For instance, a random binary word with 10 letters (e.g. baaabababb) will present, on average, $3.32...$ consecutive $a$s

weighted_bin_runs_bgf(p, q, l, z, u; mode="count_ge")

Weighted Bivariate Generating Function (BGF) $W(z, u)$ for consecutive runs in binary words of Bernoulli trials with probabilities $p$ and $q$, where $z$ marks sequence length $n$ and $u$ marks a run parameter (Flajolet & Sedgewick, Sections I.4 & III.3):

• mode="count_ge" (default): $u$ marks the number of maximal runs of length $\ge l$: $W(z, u) = \frac{1 + (u - 1) p^l z^l}{1 - (p + q)z - (u - 1) q p^l z^{l+1}}$
• mode="length_ge": $u$ marks the total number of elements belonging to maximal runs of length $\ge l$ (the numerator of RQA Determinism / Laminarity): $W(z, u) = \frac{1 + \beta(z, u)}{1 - qz(1 + \beta(z, u))}$, where $\beta(z, u) = \frac{pz - p^l z^l}{1 - pz} + \frac{(upz)^l}{1 - upz}$
• mode="count_eq": $u$ marks the number of maximal runs of exact length $l$: $W(z, u) = \frac{1 + (u - 1) p^l z^l (1 - pz)}{1 - (p + q)z - (u - 1) q p^l z^{l+1} (1 - pz)}$
• mode="double_count_ge": $u$ marks the number of maximal runs of either outcome ($p$ or $q$) of length $\ge l$.

weighted_bin_runs_moments(p, q, l, n; mode="count_ge")

Exact analytical moments (mean, var, std, count) for run statistics in a weighted binary sequence of length n with probabilities p and q and run threshold l, obtained by differentiating weighted_bin_runs_bgf at $u = 1$.

See weighted_bin_runs_bgf for available mode options ("count_ge", "length_ge", "count_eq", "double_count_ge").

weighted_bin_runs_prob(p,q,l,n)

Weighted model for consecutive runs in binary words.

Probablity of the absence of l-runs among a sequence of n random trials with probabilities p and q. $[z^{n}] \frac{1 - p^l z^l}{1 - z + q p^l z^{l+1}}$. Use diff over output values to obtain a probability distribution. For n=15, p=0.4 and q=0.6: raw_probs = map(x->weighted_bin_runs_prob(0.4,0.6,x,15),0:1:15);plot(diff(raw_probs))

weighted_bin_runs_pval(p,q,l,n)

p-value obtained from a one-tailed based on the exact distribution using the weighted model for consecutive runs weighted_bin_runs_coeff.

words_without_k_run(k,n;m=2)

OGF of words without k consecutive occurrences of a designated letter for an alphabet of cardinality m (defaults to binary words: m=2).

$\frac{1 - z^k}{ 1 - mz + (m-1)z^{k+1} }$ For instance, if n=4 and k=3, these words are not counted: aaab, baaa, aaaa.