`AnalyticComb.CYC`

— Method`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.

`AnalyticComb.I_gf`

— Method`I_gf(z)`

Integers as combinatorial structures

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

object.

`AnalyticComb.MSET`

— Method`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.

`AnalyticComb.PSET`

— Method`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.

`AnalyticComb.SEQ`

— Method`SEQ(z)`

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

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

`AnalyticComb.bin_words_runs_coeff`

— Method`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

`AnalyticComb.bin_words_runs_prob`

— Method`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.

`AnalyticComb.bin_words_with_k_occurences`

— Method`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$)

`AnalyticComb.bin_words_with_k_occurences_constr`

— Method`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$).

`AnalyticComb.catalan_factorial`

— Method`catalan_factorial(n)`

The n_th Catalan number. (EIS A000108)

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

`AnalyticComb.fixed_size_comps`

— Method`fixed_size_comps(n,k)`

Compositions of size n made of k summands,

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

`AnalyticComb.fixed_size_comps_asym`

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

`AnalyticComb.general_trees`

— Method`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}$

`AnalyticComb.longest_run_binary_asym`

— Method`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

`AnalyticComb.partitions_asym`

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

`AnalyticComb.partitions_asym`

— Method`partitions_asym(n)`

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

`AnalyticComb.partitions_gf`

— Method`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.

`AnalyticComb.partitions_max_r`

— Method`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.

`AnalyticComb.primes_composition_asym`

— Method`primes_composition_asym(n)`

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

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

`AnalyticComb.restricted_sum_comp`

— Method`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.

`AnalyticComb.restricted_sum_comp_gf`

— Method`restricted_sum_comp_gf(r)`

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

object.

`AnalyticComb.restricted_sum_part`

— Method`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.

`AnalyticComb.restricted_sum_part_gf`

— Method`restricted_sum_part_gf(r)`

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

object.

`AnalyticComb.stirling_catalan_asym`

— Method`stirling_catalan_asym(n)`

Stirling approximation for n_th Catalan number. (EIS A000108)

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

`AnalyticComb.stirling_factorial_asym`

— Method`stirling_factorial_asym(n)`

Stirling approximation for n! (EIS A000142)

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

`AnalyticComb.triangulations`

— Method`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}$

`AnalyticComb.weighted_bin_runs_coeff`

— Method`weighted_bin_runs_coeff(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_coeff(0.4,0.6,x,15),0:1:15);plot(diff(raw_probs))`

`AnalyticComb.weighted_bin_runs_prob`

— Method`weighted_bin_runs_prob(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`

.

`AnalyticComb.words_without_k_run`

— Method`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.