Edit on GitHub

Combinatorial functions

This section is about basic combinatorial functions that arise in the context of counting problems. Usually, there are indirect ways of counting—like closed formulas—instead of having to explicitly create the list of objects in question. More special combinatorial functions that count objects we have implemented (e.g. restricted partitions) are discussed in the respective sections.

Nemo.bell — Function
bell(n::T) where T<:Union{Int,fmpz}

The n-th Bell number Bₙ. This counts the number of partitions of an n-element set.

The implementation is the one from Nemo which in turn uses the one from FLINT.

Refences

  1. Wikipedia, Bell number
  2. The On-Line Encyclopedia of Integer Sequences, A000110
source
Base.binomial — Function
binomial(n::T, k::T) where T<:Union{Int,fmpz}

The binomial coefficient ${n \choose k}$. This counts the number of k-element subsets of an n-element set.

For type fmpz the implementation is the one from Nemo which in turn uses the one from FLINT.

Refences

  1. Wikipedia, Binomial coefficient
source
JuLie.catalan — Function
catalan(n::fmpz)
catalan(n::Integer)

The n-th Catalan number Cₙ. This counts all sorts of things, e.g. the number of expressions containing n pairs of parentheses which are correctly matched.

The computation simply uses the formula

\[C_n = \frac{1}{n+1}{ 2n \choose n} \;.\]

Refences

  1. Wikipedia, Catalan number
  2. The On-Line Encyclopedia of Integer Sequences, A000108
source
JuLie.euler — Function
 euler(n::fmpz)
 euler(n::Integer)

The n-th Euler number. The implementation is a wrapper to FLINT.

References

  1. Wikipedia, Euler numbers
  2. The On-Line Encyclopedia of Integer Sequences, A122045
source
Base.factorial — Function
factorial(n::T) where T<:Union{Int,fmpz}

The factorial of n. This counts the number of permuations of n distinct objects.

For type fmpz the implementation is the one from Nemo which in turn uses the one from FLINT.

Refences

  1. Wikipedia, Factorial
  2. The On-Line Encyclopedia of Integer Sequences, A000142
source
JuLie.lucas — Function
lucas(n::fmpz)
lucas(n::Integer)

The n-th Lucas number. The implementation is a wrapper to the function in GMP.

References

  1. Wikipedia, Lucas number
  2. The On-Line Encyclopedia of Integer Sequences, A000032
source
JuLie.stirling1 — Function
stirling1(n::fmpz, k::fmpz)
stirling1(n::Integer, k::Integer)

The Stirling number S₁(n,k) of the first kind. The absolute value of S₁(n,k) counts the number of permutations of n elements with k disjoint cycles. The implementation is a wrapper to the function in FLINT.

References

  1. Wikipedia, Stirling numbers of the first kind
  2. The On-Line Encyclopedia of Integer Sequences, A008275
source
JuLie.stirling2 — Function
stirling2(n::fmpz, k::fmpz)
stirling2(n::Integer, k::Integer)

The Stirling number S₂(n,k) of the second kind. This counts the number of partitions of an n-element set into k non-empty subsets. The implementation is a wrapper to the function in FLINT.

References

  1. Wikipedia, Stirling numbers of the second kind
  2. The On-Line Encyclopedia of Integer Sequences, A008277
source