# Groupings

Groupings[n,k]

gives a list of all possible groupings of 1,,n taken k at a time.

Groupings[{a1,,an},k]

gives all possible groupings of a1,,an taken k at a time.

Groupings[{{a1,a2,},{b1,b2,},},k]

gives the combination of all possible groupings of each of the lists ai,bi, taken k at a time.

Groupings[aspec,fk]

gives all possible groupings of aspec taken k at a time with the function f applied at each level.

Groupings[aspec,{f1k1,f2k2,}]

gives all possible groupings in which the function fi is applied to ki elements.

Groupings[aspec,{{f1k1,m1},{f2k2,m2},}]

allows at most mi occurrences in a given grouping of fi applied to ki elements.

Groupings[aspec,kspec,h]

wraps the function h around each grouping generated.

# Details • Groupings[n,k] can be thought of as generating a list of k-ary expression trees with n leaves.
• In Groupings[{a1,,an},k], the integer n gives the number of leaves on the tree and k gives the number of children of each node.
• Arities k and ki must be positive integers.
• With an arity specification f{k,Orderless}, Groupings returns only one representative for each collection of expressions whose tree structure is equivalent up to permutation of the branches of f.

# Examples

open allclose all

## Basic Examples(5)

Construct all binary expression trees with four leaves:

Visualize them:

Construct all ternary trees with leaves in the given list:

Construct groupings from several lists of leaves:

Construct all binary trees with three leaves in the given list:

Use different heads with different arities:

## Scope(8)

Construct binary groupings from tuples of elements:

Construct groupings of mixed arities and with all possible reorderings of the leaves:

Construct groupings with any head and arity:

Construct groupings with different heads of the same arity:

Construct groupings using different arities for the same head:

Construct groupings using different heads with different arities:

By default, Groupings returns all possible permutations of the branches of the trees:

Return representatives of those classes of groupings that cannot be obtained by permutation:

Use any combination of heads, arities, and ordering properties:

## Applications(7)

List all possible unary application expressions that can be constructed with 4 copies of a symbol s:

Arity 2 requires an odd number of copies of the symbol:

Groupings[Table[s,n],Constructk] will be {} unless nk and Mod[n,k-1]==1:

Each expression has m=(n-1)/(k-1) pairs of brackets:

There are Binomial[k m,m]/n expressions:

Construct all binary additions of three elements keeping their order:

Construct all binary additions of all reorderings of those three elements:

Combine three 1s using the binary operations +,* in all possible ways:

These are their respective values:

Find out the frequencies of all possible results of combining seven 1s with the binary operations +,*:

For a given integer n, the minimum number of 1s needed to construct n using +,* is called the complexity of n. For example, the complexity of 12 is 7:

Construct all possible expressions formed by some variables and binary functions:

Avoid evaluation of the results:

There are 3840 forms of combining the integers 1, 1, 5, 8 and binary operations +, -, *, /:

Find out their respective results, many of them involving division by 0:    Find out the only combination that produces 10:

The most frequent result is 13:

Construct logical propositions containing two atomic propositions and their negations, using some binary connectives:

Convert to disjunctive normal form:

Those correspond to the 16 Boolean functions with two variables:

Construct all expressions containing these six complex numbers, using binary heads Plus and Times:

The distribution of points is not so regular in general:

## Properties & Relations(5)

A tree with heads of arity k and n leaves has (n-1)/(k-1) internal nodes, so this number must be a non-negative integer:

Otherwise the result is an empty list:

In particular, that means that Groupings[n,k] gives {} for k>n>1:

For n1, there is always a grouping for any value k>1:

The number of binary groupings with n leaves is given by the (n-1) Catalan number:

The number of k-ary groupings with n leaves is related to the FussCatalan number:

3-ary groupings:

4-ary groupings:

Leaves are distributed keeping the order at the deepest level:

Groupings[{a1,,an},n] returns {{a1,,an}}:

## Possible Issues(1)

This is interpreted as representing the presence of head h with arity 3 and head List with arity 2:

To have the head h with arity 3 at most twice, use an additional level of list: