CYC(z,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}$. Returns a SymPy :Sym object.

I_gf(z)

Integers as combinatorial structures

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

MSET(z,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))$. Returns a SymPy :Sym object.

PSET(z,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))$. Returns a SymPy :Sym object.

SEQ(z)

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

Defined as $A = SEQ(B) \implies A(z) = \frac{1}{1 - B(z)}$.

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$).

catalan_factorial(n)

The n_th Catalan number. (EIS A000108)

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

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)!}$

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}$

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

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.

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}$

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.