Permutations are represented in gp as t_VECSMALL
s and can be input
directly as Vecsmall([1,3,2,4])
or obtained from the iterator
forperm
:
? forperm(3, p, print(p)) \\ iterate through S3 Vecsmall([1, 2, 3]) Vecsmall([1, 3, 2]) Vecsmall([2, 1, 3]) Vecsmall([2, 3, 1]) Vecsmall([3, 1, 2]) Vecsmall([3, 2, 1])
Permutations can be multiplied via *
, raised to some power using
^
, inverted using ^(-1)
, conjugated as
p * q * p^(-1)
. Their order and signature is available via
permorder
and permsign
.
binomial coefficient binom{x}{k}. Here k must be an integer, but x can be any PARI object.
? binomial(4,2) %1 = 6 ? n = 4; vector(n+1, k, binomial(n,k-1)) %2 = [1, 4, 6, 4, 1]
The argument k may be omitted if x = n is a
non-negative integer; in this case, return the vector with n+1
components whose k+1-th entry is binomial
(n,k)
? binomial(4) %3 = [1, 4, 6, 4, 1]
The library syntax is GEN binomial0(GEN x, GEN k = NULL)
.
x-th Fibonacci number.
The library syntax is GEN fibo(long x)
.
If x is a t_INT
, return the binary Hamming weight of |x|. Otherwise
x must be of type t_POL
, t_VEC
, t_COL
, t_VECSMALL
, or
t_MAT
and the function returns the number of non-zero coefficients of
x.
? hammingweight(15) %1 = 4 ? hammingweight(x^100 + 2*x + 1) %2 = 3 ? hammingweight([Mod(1,2), 2, Mod(0,3)]) %3 = 2 ? hammingweight(matid(100)) %4 = 100
The library syntax is long hammingweight(GEN x)
.
Gives the number of unrestricted partitions of
n, usually called p(n) in the literature; in other words the number of
nonnegative integer solutions to a+2b+3c+.. .= n. n must be of type
integer and n < 1015 (with trivial values p(n) = 0 for n < 0 and
p(0) = 1). The algorithm uses the Hardy-Ramanujan-Rademacher formula.
To explicitly enumerate them, see partitions
.
The library syntax is GEN numbpart(GEN n)
.
Generates the k-th permutation (as a row vector of length n) of the
numbers 1 to n. The number k is taken modulo n!, i.e. inverse
function of permtonum
. The numbering used is the standard lexicographic
ordering, starting at 0.
The library syntax is GEN numtoperm(long n, GEN k)
.
Returns the vector of partitions of the integer k as a sum of positive
integers (parts); for k < 0, it returns the empty set []
, and for k
= 0 the trivial partition (no parts). A partition is given by a
t_VECSMALL
, where parts are sorted in nondecreasing order:
? partitions(3) %1 = [Vecsmall([3]), Vecsmall([1, 2]), Vecsmall([1, 1, 1])]
correspond to 3, 1+2 and 1+1+1. The number
of (unrestricted) partitions of k is given
by numbpart
:
? #partitions(50) %1 = 204226 ? numbpart(50) %2 = 204226
Optional parameters n and a are as follows:
* n = nmax (resp. n = [nmin,nmax]) restricts partitions to length less than nmax (resp. length between nmin and nmax), where the length is the number of nonzero entries.
* a = amax (resp. a = [amin,amax]) restricts the parts to integers less than amax (resp. between amin and amax).
? partitions(4, 2) \\ parts bounded by 2 %1 = [Vecsmall([2, 2]), Vecsmall([1, 1, 2]), Vecsmall([1, 1, 1, 1])] ? partitions(4,, 2) \\ at most 2 parts %2 = [Vecsmall([4]), Vecsmall([1, 3]), Vecsmall([2, 2])] ? partitions(4,[0,3], 2) \\ at most 2 parts %3 = [Vecsmall([4]), Vecsmall([1, 3]), Vecsmall([2, 2])]
By default, parts are positive and we remove zero entries unless amin ≤ 0, in which case nmin is ignored and we fix #X = nmax:
? partitions(4, [0,3]) \\ parts between 0 and 3 %1 = [Vecsmall([0, 0, 1, 3]), Vecsmall([0, 0, 2, 2]),\ Vecsmall([0, 1, 1, 2]), Vecsmall([1, 1, 1, 1])] ? partitions(1, [0,3], [2,4]) \\ no partition with 2 to 4 non-zero parts %2 = []
The library syntax is GEN partitions(long k, GEN a = NULL, GEN n = NULL)
.
Given a permutation x on n elements, return its order.
? p = Vecsmall([3,1,4,2,5]); ? p^2 %2 = Vecsmall([4,3,2,1,5]) ? p^4 %3 = Vecsmall([1,2,3,4,5]) ? permorder(p) %4 = 4
The library syntax is long permorder(GEN x)
.
Given a permutation x on n elements, return its signature.
? p = Vecsmall([3,1,4,2,5]); ? permsign(p) %2 = -1 ? permsign(p^2) %3 = 1
The library syntax is long permsign(GEN x)
.
Given a permutation x on n elements, gives the number k such that
x = numtoperm(n,k)
, i.e. inverse function of numtoperm
.
The numbering used is the standard lexicographic ordering, starting at 0.
The library syntax is GEN permtonum(GEN x)
.
Stirling number of the first kind s(n,k) (flag = 1, default) or of the second kind S(n,k) (flag = 2), where n, k are non-negative integers. The former is (-1)n-k times the number of permutations of n symbols with exactly k cycles; the latter is the number of ways of partitioning a set of n elements into k non-empty subsets. Note that if all s(n,k) are needed, it is much faster to compute ∑k s(n,k) x^k = x(x-1)...(x-n+1). Similarly, if a large number of S(n,k) are needed for the same k, one should use ∑n S(n,k) x^n = (x^k)/((1-x)...(1-kx)). (Should be implemented using a divide and conquer product.) Here are simple variants for n fixed:
/* list of s(n,k), k = 1..n */ vecstirling(n) = Vec( factorback(vector(n-1,i,1-i*'x)) ) /* list of S(n,k), k = 1..n */ vecstirling2(n) = { my(Q = x^(n-1), t); vector(n, i, t = divrem(Q, x-i); Q=t[1]; simplify(t[2])); } /* Bell numbers, Bn = B[n+1] = sum(k = 0, n, S(n,k)), n = 0..N */ vecbell(N)= { my (B = vector(N+1)); B[1] = B[2] = 1; for (n = 2, N, my (C = binomial(n-1)); B[n+1] = sum(k = 1, n, C[k]*B[k]); ); B; }
The library syntax is GEN stirling(long n, long k, long flag)
.
Also available are GEN stirling1(ulong n, ulong k)
(flag = 1) and GEN stirling2(ulong n, ulong k)
(flag = 2).