A combinatorics library for Julia
Clone or download
mschauer Merge pull request #75 from JuliaMath/ti-s-pull-request/9b1294d6
Make partitions type-stable (deconflicted)
Latest commit 8d95714 Oct 17, 2018

README.md

Combinatorics

Combinatorics Combinatorics Build Status Coverage Status Codecov

A combinatorics library for Julia, focusing mostly (as of now) on enumerative combinatorics and permutations. As overflows are expected even for low values, most of the functions always return BigInt, and are marked as such below.

This library provides the following functions:

  • bellnum(n): returns the n-th Bell number; always returns a BigInt;
  • catalannum(n): returns the n-th Catalan number; always returns a BigInt;
  • combinations(a): returns combinations of all order by chaining calls to Base.combinations(a,n);
  • derangement(n)/subfactorial(n): returns the number of permutations of n with no fixed points; always returns a BigInt;
  • doublefactorial(n): returns the double factorial n!!; always returns a BigInt;
  • fibonaccinum(n): the n-th Fibonacci number; always returns a BigInt;
  • hyperfactorial(n): the n-th hyperfactorial, i.e. prod([i^i for i = 2:n]; always returns a BigInt;
  • integer_partitions(n): returns a Vector{Int} consisting of the partitions of the number n.
  • jacobisymbol(a,b): returns the Jacobi symbol (a/b);
  • lassallenum(n): returns the nth Lassalle number An defined in arXiv:1009.4225 (OEIS A180874); always returns a BigInt;
  • legendresymbol(a,p): returns the Legendre symbol (a/p);
  • lucasnum(n): the n-th Lucas number; always returns a BigInt;
  • multifactorial(n): returns the m-multifactorial n(!^m); always returns a BigInt;
  • multinomial(k...): receives a tuple of k_1, ..., k_n and calculates the multinomial coefficient (n k), where n = sum(k); returns a BigInt only if given a BigInt;
  • multiexponents(m,n): returns the exponents in the multinomial expansion (x₁ + x₂ + ... + xₘ)ⁿ;
  • primorial(n): returns the product of all positive prime numbers <= n; always returns a BigInt;
  • stirlings1(n, k, signed=false): returns the (n,k)-th Stirling number of the first kind; the number is signed if signed is true; returns a BigInt only if given a BigInt.
  • stirlings2(n, k): returns the (n,k)-th Stirling number of the second kind; returns a BigInt only if given a BigInt.
  • nthperm(a, k): Compute the kth lexicographic permutation of the vector a.
  • permutations(a): Generate all permutations of an indexable object a in lexicographic order.

Young diagrams

Limited support for working with Young diagrams is provided.

  • partitionsequence(a): computes partition sequence for an integer partition a
  • x = a \ b creates the skew diagram for partitions (tuples) a, b
  • isrimhook(x): checks if skew diagram x is a rim hook
  • leglength(x): computes leg length of rim hook x
  • character(a, b): computes character the partition b in the ath irrep of Sn