py3nt.polynomial package

Submodules

py3nt.polynomial.binomial module

Binomial functions and expansions

py3nt.polynomial.binomial.binomial_coefficient(n: int, k: int) → int

Calculate a binomial coefficient directly. Use \(\binom{n}{k}=\dfrac{n(n-1)\cdots (n-k+1)}{1\cdots k}\)

Parameters:

• n (int) – A non-negative integer.

• k (int) – A non-negative integer.

Returns:

Value of \(\binom{n}{k}\).

Return type:

int

Raises:

ValueError – If \(n\) or \(k\) is negative.

py3nt.polynomial.binomial.generate_binomial_coefficients(n: int) → ndarray

Generate binomial coefficients \(\binom{i}{j}\) for \(0\leq j\leq i\leq n\) Use Pascal’s rule to generate the coefficients.

Parameters:

n (int) – A non-negative integer.

Returns:

A numpy 2d-array with the coefficients.

Return type:

np.ndarray

py3nt.polynomial.binomial.homogeneous_binomial(a: int, b: int, n: int) → int

Calculate the homogeneous binomial: \(a^{n-1}+a^{n-2}b+\ldots+b^{n-1}\). We do not use \(\frac{a^{n}-b^{n}}{a-b}\). This can easily run into overflow issue.

If \(f(n)=\frac{a^{n}-b^{n}}{a-b}\), then \(f(n+1)=(a+b)f(n)-ab \cdot f(n-1)\).

If the companion matrix is

\[\begin{split}C = \begin{pmatrix} a+b & -ab\\ 1 & 0 \end{pmatrix}\end{split}\]

then

\[\begin{split}\begin{pmatrix} f(n)\\ f(n-1) \end{pmatrix} = C^{n-2} \begin{pmatrix} a+b\\ 1 \end{pmatrix}\end{split}\]

We use matrix exponentiation to calculate \(C^{n-2}\) in \(O(log{n})\).

Parameters:

• a (int) – An integer.

• b (int) – An integer different than a.

• n (int) – A positive integer.

Returns:

Value of \(a^{n-1}+a^{n-2}b+\ldots+b^{n-1}\).

Return type:

int

Raises:

ValueError – If \(n\) is not positive or \(a=b\).

Module contents