Atlas of Lie Groups and Representations

Documentation contents

Script File

combinatorics.at

The purpose of this module is to collect basic combinatorial functions,
like factorials, binomial coefficients, generators of partitions and so on
Source
atlas-scripts/combinatorics.at (1159 lines)
Definitions
129
Loads
Loaded by
exp-generating-series.at stable.at

Definitions in source order

|factorial@int| is now defined in basic.at, and it can be written as |n!|
L9

binom 2 overloads

L11binom (int n, int k) = int
L17binom (rat n, int k) = rat

multinom

L23multinom ([int] a) = int
multinomial coefficient, upper index implicit

multi_choose

L27multi_choose (int n,int k) = int

falling_power

L29falling_power (int n, int k) = int

rising_power

L32rising_power (int n, int k) = int
Combinatorial number system ${\N\choose k}\to\N$ encoding and decoding
L35

combination_encode

L40combination_encode([int] list) = int
Represent any $k$-combination on $\N$ as a single natural number
For fixed $k$ this is bijective, and a decoding follows.
|list| strictly increasing

combination_decode

L43combination_decode(int k) = (int->[int])
next assert(@:N=0)
L50

even_places

L53even_places ([int] v)
extract components at even or odd positions

odd_places

L54odd_places ([int] v)
Permutations
L57

Permutation type

L59
set_type Permutation = vec { second line of 2-line form of a permutation }

is_permutation

L61is_permutation (vec v) = bool

permutation_matrix

L73permutation_matrix (Permutation pi) = mat
Matrix whose left-multiplication to a column vector permutes it by |pi|.
It has nonzero entries at each (pi(j),j), it could have been defined (using
|matrix| from basic.at) as |matrix((#pi,#pi),(int i,int j): #(i=pi[j]) )|.

permutation

L76permutation (mat P) = Permutation
assumed a permutation matrix
right-act on row [0,1,...,n-1] for one-line form

compose_permutations

L79compose_permutations (Permutation sigma, Permutation pi) = Permutation

inverse

L82inverse (Permutation pi) = Permutation
hope the name causes no conflict

also defined in basic.at

permutation_inverse

L92permutation_inverse (Permutation pi) = Permutation
longer name for non-checking (so faster) version of the above

permutation_product

L96permutation_product (mat M) = Permutation
a product of many permutations, arranged as columns of a matrix

cyclic_permutation

L100cyclic_permutation (int n) = ([int] cycle) Permutation
get transpositions as |cyclic_permutation(n)([i,j])|, and cycles similarly

cycle_product

L105cycle_product (int n) = ([[int]]->Permutation)
similarly make a permutation from a product of cycles (disjoint or not)

permute 2 overloads

L111permute (Permutation pi,vec v) = vec
permutation action on |vec| values
L119any_type Tpermute (Permutation pi,[T]a) = [T]

permutation_act

L128permutation_act (Permutation sigma, mat M) = mat
left-multiply by permutation matrix (permute rows by permutation)

permutation_right_act

L132permutation_right_act (mat M,Permutation sigma) = mat
right-multiply by permutation matrix (permute columns by inverse permutation)

permute_rows

L135permute_rows = permutation_act@(Permutation,mat)

permute_columns

L136permute_columns (Permutation sigma,mat M) = mat

permutation_conjugation

L139permutation_conjugation (Permutation sigma, mat M) = mat

permutation_cycles

L144permutation_cycles (Permutation pi) = [[int]]

permutation_encode

L158permutation_encode (Permutation sigma) = int
represent a permutation as a single number: its lexicographic position

permutation_decode

L169permutation_decode(int code, int n) = Permutation
permutation number |code| in lexicographic order among permutations of |n|

permutation_iterator

L192permutation_iterator (vec pi) = Iterator<vec>
The following generates partitions starting from #n, without large storage

  let (get,incr)= permutation_iterator(#n) in
  while
    case get() | none(): false | some(perm): process(perm); true esac
  do incr()
  od

Instead of |#n| one can supply any vector |pi| as starting value, which will
generate all permutations only if |pi| is weakly increasing. In case of
equality among entries of |pi|, permuting these among each other is avoided.
generate |(#xs)!| permutations of |xs|, not avoiding permutation of equals
L205

permutations

L207any_type Tpermutations([T] xs) = [[T]]

root_orbits

L222root_orbits (WeylElt w) = [[int]]
group root indices by orbits under action of cyclic group generated by |w|

multiset_permutations

L229multiset_permutations ([int] multiplicities) = [[int]]
Partitions
L242

Partition type

L244
set_type Partition = [int]   { list of decreasing parts, no trailing zeros }

strip_to_partition

L246strip_to_partition (Partition lambda) = [int]
alternatively: |for x in list do if =x then break fi od|
L248

is_partition

L250is_partition ([int] seq) = bool

frequencies

L252frequencies (Partition lambda) = vec
frequency vector, position 0 unused

repeat_parts

L262repeat_parts (vec frequencies) = Partition
the following is a right-inverse to |frequencies|; assuming |frequencies[0]=0|
to avoid getting trailing 0's, the image is precisely the set of partitions

sort_to_partition

L265sort_to_partition ([int] parts) = Partition

cycle_type

L268cycle_type ([int] pi) = Partition
cycle sizes in decreasing order

transpose

L272transpose ([int] parts) = Partition
transpose of a composition, after implicitly sorting it to a partition

also defined in basic.at

or more "manually", when |parts| assumed already in decreasing order
if #lambda=0 then []
else let l=#lambda in
  for i:lambda[0] { since |i<lambda[0]|, we can never set |l:=0| below }
  do while lambda[l-1]<=i do l-:=1 od; l
  od
fi
L274

Levi_A

L284Levi_A ([int] parts) = (int,LieType,[int])
basic data for Levi factor of $A_{n-1}$ given by composition |parts| of $n$
|(n,Levi_type,simples)|

compressed_string

L290compressed_string(Partition P) = string

also in this file at line 1138

rlex_leq_partitions

L303rlex_leq_partitions (Partition lambda, Partition mu) = bool
lexicographic comparison restricted to partitions of same |n| (0-extended)

rlex_cmp_partitions

L312rlex_cmp_partitions (Partition lambda, Partition mu) = int
same, but three-way result in $\{-1,0,1\}$ for less/equal/greater; no 0-ext
if |lambda| exhausted then so is |mu|, and we have equality
L318

slex_leq_partitions

L321slex_leq_partitions ((Partition,Partition) (lambda,mu):pair) = bool
comparing partitions by sum then lexicographically; implicitly 0-extend

slex_cmp_partitions

L325slex_cmp_partitions ((Partition,Partition) (lambda,mu):pair) = int

index_partition

L330index_partition([Partition] sorted_list) = (Partition->int)
look up partition in sorted list of partitions, all assumed of same sum

dominance_leq_compositions

L340dominance_leq_compositions (Partition v,Partition w) = bool
dominance order on compositions, assumed to be so of the same number

dominance_leq_partitions

L352dominance_leq_partitions (Partition v,Partition w) = bool
same as previous, but assuming |v|,|w| are equal sum partitions (so sorted)
functions related to representations of S_n
L365

hook_lengths

L367hook_lengths (Partition lambda) = [int]

also in this file at line 376

not viewed as partition, but sorting is the same
L371

Sn_representation_dimension

L373Sn_representation_dimension (Partition lambda) = int

hook_lengths

L376hook_lengths ([bool] edges) = [int]

also in this file at line 367

edge_sequence

L385edge_sequence (Partition lambda) = ([bool],int)
edge sequence from first horizontal (false) to last horizontal, and shift

cycle_type_order

L393cycle_type_order = lcm@[int]

also in this file at line 848, line 954

cycle_centralizer_order

L394cycle_centralizer_order ([int] cycles) = int

also in this file at line 850

cycle_class_size

L396cycle_class_size ([int] cycles) = int

also in this file at line 856

cycle_power

L400cycle_power ([int] cycles, int k) = [int]
compute cycle type of power of a permutation, given its cycle type

also in this file at line 860, line 971

Murnaghan_Nakayama

L406Murnaghan_Nakayama (Partition lambda, [int] cycle_type) = int
character of irreducible Sn representation lambda at give cycle type
generating all partitions; for counting, see |n_partitions| in lazy_lists.at
L430

partitions

L432partitions = (int n) [Partition]
generating partitions, all of whose parts must lie in a given set
L452

part_restricted_partitions

L454part_restricted_partitions ((int->bool)pred) = (int n) [Partition]

odd_part_partitions

L479odd_part_partitions = part_restricted_partitions(is_odd@int)

strict_partitions

L482strict_partitions = (int n) [Partition]
partitions with distinct parts: all multiplicities are 0 or 1
Jordan types of nilpotent elements (or orbits)
L503

is_valid 2 overloads

L506is_valid (string type,Partition P) = bool
test if partition is valid (nilpotent orbit) Jordan type in type ABCD
L520is_valid (LieType t) = (Partition->bool)

also defined in L_packet.at

Combinatorics specifically for (Weyl groups of) types B,C,D
L530

parity_restricted_partitions

L533parity_restricted_partitions (bool restrict_odd_parts) = (int->[Partition])
partitions with even multiplicity of parts of one parity (odd or even)

Signed_cycles type

L565
set_type Signed_cycles = [int,bool] { bool |b| encodes product |minus_1^#b| }
for conjugagy classes: cycles with product of signs, for simple types B,C,D

BiPartition type

L568
set_type BiPartition = (Partition,Partition)
for $W(C_n)$ irreducible representations: partition pairs of total size $n$
no specific interpretation imposed here, but ordering should always have:
positive/even/0/false/trivial repn BEFORE negative/odd/1/true/sign repn one
parametrises irreps of the hyperoctahedral group $W(C_n)=W(B_n)$
also in bijection with |Signed_cycles| as (unflipped lengths,flipped lengths)
L569

Symbol type

L577
set_type Symbol = [[int]]  { must have 2 lists, first longer than second by 1 }
Sometimes (Springer correspondence) a transformation of |BiPartition| is used
The type to represent them is delibetately distinct from |BiPartition|
both lists strictly INcreasing with non-negative entries
equivalence [a_1,...a_k]->[0,a_1+1,s_2+1,...a_k+1] can be used to adapt length
every symbol can be written with length difference 1 and at most one term 0
L578

rank 2 overloads

L584rank (Signed_cycles cycles) = int
L585rank (BiPartition(lambda,mu)) = int

also in this file at line 942, line 948; also defined in basic.at, sommers.at

=

L588= (Signed_cycles cyc0,Signed_cycles cyc1) = bool
equality is strict (don't want to force interpretation onto |[int,bool|])

also in this file at line 639, line 1016, line 1087; also defined in basic.at, modules.at

!=

L595!= (Signed_cycles cyc0,Signed_cycles cyc1) = bool

also in this file at line 1017, line 1088; also defined in basic.at

same_as

L598same_as (Signed_cycles cyc) = (Signed_cycles->bool)
for equivalence up to permutation of cycles, use |c0.same_as(c1)|

also in this file at line 1002, line 1075

The hyperoctahedral group $H_n$ can be represented by sigend permutation
matrices (where every row and column has a unique nonzero entry, which lies in
$\{-1,1\}$. There is a surjective group morphism to $S_n$ forgetting the signs.

This is the symmetry group of en $n$-dimensional hyperoctahedron (also of the
hypercube), centered at the origin, with 2 vertices on each coordinate axis.

Conjugacy classes of $H_n$ are given by signed cycle types: projection to
$S_n$ gives a cycle type (for the permutation of the axes), and to each cycle
is attached the product of the signs for the coordinate axes in the cycle.
L605

to_cycles

L618to_cycles (BiPartition(lambda,mu)) = Signed_cycles
converting partition pairs to signed cycle types, second has flipped cycles

to_partition_pair

L622to_partition_pair(Signed_cycles cy) = BiPartition
the inverse of |to_cycles@BiPartition|

pairs_of_total_sum

L629pairs_of_total_sum (int n,(int->[Partition]) lister) = [BiPartition]
generate pairs of partitions of total size |n| with size |k| components
produced in the order in which |lister| lists them, starting all on left

partition_pairs

L636partition_pairs (int n) = [BiPartition]
generate all bi-partitions of |n| by size distribution, starting all left

=

L639= (BiPartition (P,Q), BiPartition (R,S)) = bool

also in this file at line 588, line 1016, line 1087; also defined in basic.at, modules.at

<=

L642<=(BiPartition (P,Q), BiPartition (R,S)) = bool
compare |BiPartition| values of same sum, in ordering of |partition_pairs|

also in this file at line 1067; also defined in basic.at

index_bipartition

L650index_bipartition ([BiPartition] sorted_list) = (BiPartition->int)
look up pair in sorted list of partition pairs, all assumed of same sum
counterpart of the Murnaghan-Nakayama rule for hyperocthedral groups
L655
Characters of the hyperoctahedral group $H_n$ are parametrised as follows by
bi-partitions |(lambda,mu)| of $n$. Call "axis-sign" the 1-dimensional
representation of any hyperoctahedral group that takes value $+1$ on all
simple reflection except the last (for the off-length simple root) where it
takes the value $-1$: on a general signed permutation it is the product of the
nonzero entries in its matrix (it is also the product of the cycle-signs in
its signed cycle type).

Given a bi-partition |(lambda,mu)|, let |l=sum(lambda),m=sum(mu)|, let $K$ be
the $H_l\times H_m$ subgroup of $H_n$, restrict (back up the surjective group
morphisms $H_i\to S_i$) the irreducible representations for |lambda| and |mu|
of $S_l$ respectively $S_m$ to ones of $H_l$ respectively $H_m$, tensor the
latter with the axis-sign representation of $H_m$, then induce the resulting
(outer tensor product) representation of $K=H_l\times H_l$ from $K$ to $H_n$.
L657

hyperoctahedral_character

L673hyperoctahedral_character ( BiPartition (lambda,mu):pair ,Signed_cycles signed_cycle_type ) = int
irreducible repn, sign applies to |mu|
describes a conjugacy class
Commented-out code, lines 736–756 (19 lines)
Core and quotient operations can be defined in terms of associating to any
partition $\lambda$ the subset $\{ lambda[i]-i-1 | i\in\N \}$ of $\Z$. This
set represents the set of vertical edges terminating the rows of the Young
diagram, recorded by their diagonal positions (the main diagonal separating
positions in $\N$ from its complement, i.e., its splits between -1 and 0).

This set is bounded above while its complement is bounded below; more
specifically the set meets $\N$, and its complement the complement of $\N$, in
equal size finite sets. An ordered pair of partitions can be "spliced
together" as follows: take there associated sets, transform the former by
$i\mapsto 2i$ and the latter by $i\mapsto 2i+1$, merge the results and find
the partition corresponding to the set. If the Young diagrams original
partitions together have $n$, the spliced partition can be covered by $n$
dominos. More generally we could add a fixed integer $d$ in the first
transformation and subtract it in the second; then $d$ will be the unbalance
of black and white squares in the diagram of the resulting partition, and
after removing $n$ dominos from it we are left with a "2-core" still having
the same unbalance. It is a staircase diagram with |core_length(d)| parts.
The pair of original partitions is the "2-quotient" of the spliced partition.

core_length

L758core_length (int n) = int

core_number

L759core_number (int k) = int

core_quotient_2

L763core_quotient_2 (Partition lambda) = (int,BiPartition)
Core number and quotient partition pair. In the latter, as per |BiPartition|
convention, the partition coming from the EVEN edge positions comes first

from_core_quotient_2

L773from_core_quotient_2 (int d,BiPartition(lambda,mu)) = Partition
Splicing BiPartitions |(lambda,mu)|, with 2-core with (unbalance) number |d|

classic_permutation

L804classic_permutation (WeylElt w) = Permutation
Find classical (permutation or signed permutation) description of Weyl group
elements in classical types. The associated root datum must have one simple
factor of type A-D, but need not have standard (Bourbaki) diagram numbering.

The output is a (signed) permutation in one-line format. For type $A_n$ this
is just a permutation of $n+1$ (hence 0-based), for types $B_n$, $C_n$, $D_n$
this is a permutation of the $2n$ elements $-n, ,..., -2 -1, 1, 2, ..., n$,
commuting with $x \mapsto -x$, and the one-line format consists of a list of
the images of $1, 2, ..., n$ (1-based); it determines the signed permutation.

signed_permutation

L821signed_permutation(WeylElt w) = [int]
a simpler version when |w| is known to be for some Sp(2n) or SO(m)

signed_cycle_type_code

L828signed_cycle_type_code ([int] sigma) = vec
for a signed permutation |sigma| of $\{1,...,n\}$, represented by the images
of $1,...,n$, compute the cycle type as list of pairs (cycle length, sign);
return weakly decreasing vector of sign*cycle_length, e.g., |[4,2,-1,-1,-3]|

cycle_code

L833cycle_code(WeylElt w) = vec
assuming |w| is for |Sp(2n)| or |SO(m)|

as_signed_cycles

L837as_signed_cycles (vec v) = Signed_cycles
convert code as above to |Signed_cycles|, ordering as |to_cycles| does

as_bipartition

L841as_bipartition (vec v) = BiPartition

signed_cycle_type

L845signed_cycle_type ([int] sigma) = Signed_cycles

cycle_type_order

L848cycle_type_order (Signed_cycles cycles) = int

also in this file at line 393, line 954

cycle_centralizer_order

L850cycle_centralizer_order (Signed_cycles cycles) = int

also in this file at line 394

cycle_class_size

L856cycle_class_size (Signed_cycles cycles) = int

also in this file at line 396

cycle_power

L860cycle_power (Signed_cycles cycles, int k) = Signed_cycles
compute cycle type of power of a signed permutation, given its cycle type

also in this file at line 400, line 971

a |Symbol| is a transformed |BiPartition|: reversed, strict, length diff. 1
L873

normalize

L876normalize (Symbol S) = Symbol
normalize symbol: |f|=|g|+1 and at most 1 zero
all other functions taking |Symbol| assume that argument is normalized
L883

symbol

L885symbol (BiPartition(lambda,mu)) = Symbol
normalized

symbol_to_bipartition

L896symbol_to_bipartition (Symbol S) = BiPartition

is_special

L901is_special (Symbol S) = bool

make_special 2 overloads

L904make_special (Symbol S) = Symbol
L919make_special (BiPartition bip) = BiPartition

also in this file at line 1090

adaptation to the above to deal with Weyl groups of type Dn
L923

is_very_even

L926is_very_even (Partition P) = bool
a condition relevant to which cycle types give split classes in $W(D_n)$
whether all parts are even

is_doubly_even

L929is_doubly_even (Partition P) = bool
a condition relevant to which $D_n$ nilpotent orbits are split from $O(2n)$
even parts even multiplicities only

D_class type

L932
set_type D_class = { cycle types restricted to Dn subgroup }
   ( Signed_cycles unsplit_class { the XOR of all |bool| values is |false| }
   | (Partition,bool) split_class { "all false" even cycles, and a single sign }
   )

Fields: unsplit_class, split_class

D_irrep type

L936
set_type D_irrep = { from folding pairs of partitions under swapping }
   ( (Partition,Partition) unsplit_irr { unequal partitions, larger first }
   | (Partition,bool) split_irr { for pair of equal partitions, with sign }
   )

Fields: unsplit_irr, split_irr

rank 2 overloads

L942rank (D_class c) = int
recover the value of |n|
L948rank (D_irrep chi) = int

also in this file at line 584, line 585; also defined in basic.at, sommers.at

cycle_type_order

L954cycle_type_order (D_class c) = int

also in this file at line 393, line 848

centralizer_order

L959centralizer_order (D_class c) = int

class_size

L967class_size (D_class c) = int

cycle_power

L971cycle_power (D_class c, int k) = D_class
compute cycle type of power of a signed permutation, given its cycle type

also in this file at line 400, line 860

to_D_class

L985to_D_class ([int] sigma) = D_class
rather than |signed_cycle_type_code|, $D_n$ classes need a finer analysis
as from |classic_permutation

same_as

L1002same_as (D_class c0) = (D_class->bool)

also in this file at line 598, line 1075

=

L1016= (D_class c0, D_class c1) = bool

also in this file at line 588, line 639, line 1087; also defined in basic.at, modules.at

!=

L1017!= (D_class c0,D_class c1) = bool

also in this file at line 595, line 1088; also defined in basic.at

D_classes

L1019D_classes (int n) = [D_class]

D_irreducibles

L1028D_irreducibles (int n) = [D_irrep]

less_eq

L1043less_eq (D_class elt) = (D_class->bool)
predicate of coming before a given element in the ordering of |D_classes|

<=

L1067<= (D_class a,D_class b) = bool
i.e., |less_eq(b)(a)|

also in this file at line 642; also defined in basic.at

index_D_classes

L1070index_D_classes ([D_class] sorted_list) = (D_class->int)
look up pair in sorted list of |D_class|es, all assumed for the same size

same_as

L1075same_as (D_irrep chi) = (D_irrep->bool)

also in this file at line 598, line 1002

=

L1087= (D_irrep c0, D_irrep c1) = bool

also in this file at line 588, line 639, line 1016; also defined in basic.at, modules.at

!=

L1088!= (D_irrep c0,D_irrep c1) = bool

also in this file at line 595, line 1017; also defined in basic.at

make_special

L1090make_special (D_irrep chi) = D_irrep

also in this file at line 904, line 919

character

L1110character (D_irrep chi, D_class c) = int

also defined in modules.at, W_reps.at

compressed_string

L1138compressed_string(BiPartition(P,Q)) = string
for printing |BiPartition| values compactly

also in this file at line 290

Generated from atlas-scripts at commit 7e1b958 (2026-09-17).