Advanced Combinatorics

Shenghui Yang, Wolfram

#WolframTechConf

ABSTRACT

This lecture explores core ideas in advanced combinatorics using the Wolfram Language. Topics include discrete calculus, recurrence relations, and integer sequence analysis via the OEIS interface. 
Participants will learn to apply built-in and repository functions for permutation statistics—such as Eulerian numbers and Foata transforms—and to model combinatorial structures like Catalan trees and binary search trees. The session also aims to raise awareness of high-quality combinatorics tools available in the Wolfram Function Repository, blending symbolic programming with hands-on mathematical exploration.

Ordered-within, unordered-between partitions

The Lah numbers describe how many ways you can divide a set of n distinct elements into k nonempty blocks where the elements inside each block are arranged in order, but the blocks themselves are not ordered. In other words, each block is a small ordered list, and together they form an unordered collection of such lists.

ResourceFunction["LahL"][8,#]&/@Range[4]

The formula for the Lah number, L(n, k) = n! × Binomial[n-1,k-1]/ k!, comes from a clear combinatorial idea. First, arrange all n elements in a line; there are n! possible orders. Then, choose k−1 positions among the n−1 gaps to place dividers, which creates k ordered blocks. This gives the factor Binomial[n-1,k-1]). However, since the blocks are considered unordered as a whole, every distinct Lah partition is counted k! times, once for each possible ordering of its blocks. Dividing by k! corrects for this over-counting, leading to the final expression.

Tabular[PadRight[#,12]&/@Table[ResourceFunction["LahL"][n,k],{n,12},{k,n}],Alignment-><|"Columns" -> Left|>]

Use WFR OEIS functions to search for

ResourceFunction["OEISLookup"][{40320,141120,141120,58800}]

Find more details with the second argument:

ResourceFunction["OEISSequenceData"]["A105278","Dataset"]

Generate random Lah partition

The random generator preserves the *correct* probability weight for every configuration in sample space with all linear permutations :

n=8;k=4;

Generate one random permutation:

sample=RandomSample[Range[n],n]

Treat the numbers as stars and  insert “bars” in between:

par=Sort[RandomSample[Range[n-1],k-1]]

Indices of items between the bars:

g=Partition[{0}~Join~par~Join~{n},2,1]+Threaded@{1,0}

Find the Lah partition up to isomorphism (ignore the order of blocks):

lp=LexicographicSort[Take[sample,#]&/@g]

Graph structure

Recurrence relation for Lah is L(n+1,k) = (n+k)L(n,k)+L(n,k-1), which has the same structure of binomial number.

Prepare for regular triangle lattices:

Clear[i,j]

lattice[n_Integer]:=With[{r=n},Table[{r,c},{c,1,r}]]

interLayer[n_Integer]:=With[{lower=lattice[n+1]},
Thread[lattice[n]\[UndirectedEdge]Most[lower]]~Join~Thread[lattice[n]\[UndirectedEdge]Rest[lower]]]

triGrid[{i_,j_}]:={j-i/2,-i*Sqrt[3]/2.}

ew[e_]:=Which[e[[1,2]]==e[[2,2]],Total[e[[1]]],True,1]

annoate[e_UndirectedEdge]:=Annotation[e,
EdgeLabels->ew[e],
EdgeLabelStyle->Directive[15,Bold,StandardOrange,Background->None]
]

Generated the weighted graph:

LahTriangle[n_Integer]:=Module[{edge,vtx},
edge=Table[interLayer[k],{k,1,n}]//Flatten;
vtx=ResourceFunction["FlatTable"][{i,j},{i,1,n+1},{j,i}];
Graph[annoate/@edge,
VertexLabels->Table[
v->Placed[
With[{en=ResourceFunction["LahL"]@@v},
If[en<999,en,Tooltip[Subsuperscript["L",v[[1]],v[[2]]],Style[en,20]]]
],Center],{v,vtx}],
VertexLabelStyle->Directive[Floor[10*(Sqrt[Log[n]])],RGBColor["#00203F"],FontFamily->"Courier",Bold],
VertexSize->0.32*(Sqrt[Log[n]]),
VertexStyle->RGBColor["#ADEFD1"],
VertexCoordinates->Table[v->triGrid@v,{v,vtx}],
EdgeStyle->Opacity[0.4],ImageSize->n*65,
EdgeWeight->Map[#->ew[#]&,edge]]]

LahTriangle[10]

Foata Transform — A bridge between words and permutations

The Foata Transform, introduced by Dominique Foata in the 1960s, is a fundamental bijection in combinatorics that reorders elements of a word or permutation to reveal hidden structure.
It provides a correspondence between the number of inversions and the major index, showing that these two statistics are equidistributed. Conceptually, the transform decomposes a permutation into cycles or “records” based on local rises, allowing combinatorial properties to be studied through an elegant algebraic and graphical framework. 
The Foata Transform thus plays a central role in permutation statistics, q-analog identities, and enumerative combinatorics.

Eulerian statistics

A permutation ascent is a position where one element is followed by a larger one, marking a local increase. The number of ascents complements descents and is central to Eulerian statistics, which count permutations by how many rises they contain.

p=RandomSample[Range[8],8]

ResourceFunction["PermutationAscents"]@p

LaunchKernels[];

Tally[ParallelMap[Length@*ResourceFunction["PermutationAscents"],Permutations[Range[8]]]]

Compare the results to Eulerian numbers

ResourceFunction["EulerianNumber"][8,#]&/@(Range[8])

ResourceFunction["EulerianNumberTriangle"][9]

The Foata transformation provides a bijection mapping each permutation to another whose number of descents matches the number of excedances in the original:

exc[perm_]:=Position[MapIndexed[{#,#2[[1]]}&,perm],_?(#[[1]]>#[[2]]&),1,Heads->False]//Flatten

p2=RandomSample[Range[15],15]

p2f=ResourceFunction["FoataTransform"][p2]

Verify that the number of elements in the list are the same (bijection):

{ResourceFunction["PermutationAscents"]@p,exc[p]}

Length/@%

Let’s take a look at the source code and that of its inverse. (Hover to the object below to reveal local documentation)

{ResourceFunction["FoataTransform"],ResourceFunction["InverseFoataTransform"]}

Create a Foata bijective graph:

circleLayout[n_]:=Table[{Cos[2. π/n i],Sin[2. π/n i]},{i,0,n-1}];
n=20;
r=Range[n];
SeedRandom["WTC 2025"];
p1=Permute[r,RandomPermutation[n]];
p2=[p1];
cyc2=FindPermutation[p1,p2];
Graph[Thread[r->PermutationList[cyc2,n]],
VertexLabels->Placed[Automatic,Center],
VertexCoordinates->Thread[r->circleLayout[n]],
VertexSize->.5,ImageSize->360
]

Colijn–Plazzotta numbering scheme for unlabeled rooted binary trees

The Colijn–Plazzotta numbering scheme assigns a unique positive integer to every unlabeled rooted binary tree, establishing a one-to-one correspondence between integers and tree topologies. Defined recursively, the scheme starts with the single-node tree labeled as 1. For any binary tree whose left and right subtrees are assigned integers 
L and R (with L>=R ), its number is given by

This elegant recursive formula mirrors the structure of the binomial number system, where hierarchical combinations are encoded through triangular indexing. As such, the Colijn–Plazzotta bijection provides not only an efficient enumeration of binary tree shapes but also a numerical framework rooted in combinatorial representation theory—linking tree topology ranking to binomial-based positional encoding.

Colijn–Plazzotta tree in WFR

ColijnPlazzottaTree is available in the repository with efficient implementation

ResourceFunction["ColijnPlazzottaTree"][10^6]

ResourceFunction["ColijnPlazzottaTree"][10^6,"SubtreeRanks"]

Let’s take a look at the source code and that of its inverse. (Hover to the object below and select local documentation)

ResourceFunction["ColijnPlazzottaTree"]

This tree is closely related to binomial number system:

Table[ResourceFunction["SubsetFromIndex"][index,3],{index,1,20}]

ResourceFunction["BinomialNumberSystemTriplet"][#]&/@Range[20]

Uniformly random full binary tree with labeled leaves

The hidden Catalan recurrence is used to compute the weight of each configuration. (Hover to the object below to reveal local documentation)

t1=ResourceFunction["RandomBinaryTree"][12]

Full binary tree theorem implies that if a tree has L leaves, the total number of nodes is N = 2L – 1. If the root is excluded, the number of internal nodes is always even.

Sample  Tree-Dyck-words bijection

Use tree traversal function to specify depth first search on the whole tree:

pa=TreeMap[Which[#=={},"",Last[#]//OddQ,"(",True,")"]&,t1,All->{"Position"}]

Generate a valid Dyck word using matching parenthesis notation:

res={};
TreeScan[AppendTo[res,#]&,pa,TreeTraversalOrder->{"DepthFirst"}];
Row[res]

Summary and key topics

The session emphasizes using Wolfram Language functions and the Wolfram Function Repository to analyze and visualize combinatorial structures effectively.

• Lah Numbers: Ways to partition a set of  elements into  non-empty linearly ordered subsets.

• Random Lah Partition: Generating partitions with correct probability weights.

• Foata Transform: A bijection revealing hidden structure in permutations, equating the number of inversions and the major index.

• Colijn–Plazzotta Numbering: Assigns unique integers to unlabeled rooted binary trees, linking tree topology to binomial positional encoding.

• Random full binary tree: Utilizes the hidden Catalan recurrence for weighting tree configurations.