Fuss–Catalan Numbers

As you’ve seen, Catalan numbers have many interpretations in combinatorics, including:

A generalization of Catalan numbers uses triples instead of pairs, for example:

The sequence of numbers described by this generalization is called the Fuss–Catalan numbers, with values:

Binomial[3 n, n]/(2 n + 1)

You’ll sometimes see this notation:

C sub n super (3)

There’s one way to parenthesize {1, 2, 3} as a triple (specifically, leave it alone):

{1, 2, 3}

One planar ternary tree with three leaves:

ternary tree for (1, 2, 3)

One path from (0, 0) to (2, 1) that doesn’t cross above the diagonal:

...

One partition of {1, 2} into subsets of even size:

...

And one way to cut a square into one quadrilateral (with zero cuts):

square

Three ways to parenthesize {1, 2, 3, 4, 5} as triples:

{{1, 2, 3}, 4, 5}
{1, {2, 3, 4}, 5}
{1, 2, {3, 4, 5}}

Three corresponding planar ternary trees:

three ternary trees for (1, 2, 3, 4, 5)

Three paths from (0, 0) to (4, 2) that don’t cross above the diagonal:

...

Three non-crossing partitions of {1, 2, 3, 4} into subsets of even size:

...

And three correponding ways to slice a hexagon into quadrilaterals (with one cut):

hexagon sliced into quadrilaterals two ways

Twelve ways to parenthesize {1, 2, 3, 4, 5, 6, 7} as triples:

{{{1, 2, 3}, 4, 5}, 6, 7}
{1, {{2, 3, 4}, 5, 6}, 7}
{1, 2, {{3, 4, 5}, 6, 7}}
{{1, {2, 3, 4}, 5}, 6, 7}
{1, {2, {3, 4, 5}, 6}, 7}
{1, 2, {3, {4, 5, 6}, 7}}
{{1, 2, {3, 4, 5}}, 6, 7}
{1, {2, 3, {4, 5, 6}}, 7}
{1, 2, {3, 4, {5, 6, 7}}}
{{1, 2, 3}, {4, 5, 6}, 7}
{{1, 2, 3}, 4, {5, 6, 7}}
{1, {2, 3, 4}, {5, 6, 7}}

Twelve ternary trees:

twelve ternary trees for 1 through 7

Twelve paths from (0, 0) to (6, 3) that don’t cross above the diagonal:

...

Twelve non-crossing partitions of {1, 2, 3, 4, 5, 6} into subsets of even size:

...

And twelve ways to slice an octagon into quadrilaterals (with two cuts):

octagon sliced into three quadrilaterals, twelve ways

Fifty-five ways to parenthesize {1, 2, 3, …, 9}:

{{{{1,2,3},4,5},6,7},8,9}	{1,{{{2,3,4},5,6},7,8},9}	{1,2,{{{3,4,5},6,7},8,9}}	{{1,{{2,3,4},5,6},7},8,9}	{1,{2,{{3,4,5},6,7},8},9}
{1,2,{3,{{4,5,6},7,8},9}}	{{1,2,{{3,4,5},6,7}},8,9}	{1,{2,3,{{4,5,6},7,8}},9}	{1,2,{3,4,{{5,6,7},8,9}}}	{{{1,{2,3,4},5},6,7},8,9}
{1,{{2,{3,4,5},6},7,8},9}	{1,2,{{3,{4,5,6},7},8,9}}	{{1,{2,{3,4,5},6},7},8,9}	{1,{2,{3,{4,5,6},7},8},9}	{1,2,{3,{4,{5,6,7},8},9}}
{{1,2,{3,{4,5,6},7}},8,9}	{1,{2,3,{4,{5,6,7},8}},9}	{1,2,{3,4,{5,{6,7,8},9}}}	{{{1,2,{3,4,5}},6,7},8,9}	{1,{{2,3,{4,5,6}},7,8},9}
{1,2,{{3,4,{5,6,7}},8,9}}	{{1,{2,3,{4,5,6}},7},8,9}	{1,{2,{3,4,{5,6,7}},8},9}	{1,2,{3,{4,5,{6,7,8}},9}}	{{1,2,{3,4,{5,6,7}}},8,9}
{1,{2,3,{4,5,{6,7,8}}},9}	{1,2,{3,4,{5,6,{7,8,9}}}}	{{{1,2,3},{4,5,6},7},8,9}	{1,{{2,3,4},{5,6,7},8},9}	{1,2,{{3,4,5},{6,7,8},9}}
{{{1,2,3},4,{5,6,7}},8,9}	{1,{{2,3,4},5,{6,7,8}},9}	{1,2,{{3,4,5},6,{7,8,9}}}	{{1,{2,3,4},{5,6,7}},8,9}	{1,{2,{3,4,5},{6,7,8}},9}
{1,2,{3,{4,5,6},{7,8,9}}}	{{{1,2,3},4,5},{6,7,8},9}	{{{1,2,3},4,5},6,{7,8,9}}	{{1,2,3},{{4,5,6},7,8},9}	{{1,2,3},4,{{5,6,7},8,9}}
{1,{{2,3,4},5,6},{7,8,9}}	{1,{2,3,4},{{5,6,7},8,9}}	{{1,{2,3,4},5},{6,7,8},9}	{{1,{2,3,4},5},6,{7,8,9}}	{{1,2,3},{4,{5,6,7},8},9}
{{1,2,3},4,{5,{6,7,8},9}}	{1,{2,{3,4,5},6},{7,8,9}}	{1,{2,3,4},{5,{6,7,8},9}}	{{1,2,{3,4,5}},{6,7,8},9}	{{1,2,{3,4,5}},6,{7,8,9}}
{{1,2,3},{4,5,{6,7,8}},9}	{{1,2,3},4,{5,6,{7,8,9}}}	{1,{2,3,{4,5,6}},{7,8,9}}	{1,{2,3,4},{5,6,{7,8,9}}}	{{1,2,3},{4,5,6},{7,8,9}}

Fifty-five ternary trees:

55 ternary trees for 1 through 9

Fifty-five paths:

55 paths

Fifty-five non-crossing partitions of {1, 2, 3, 4, 5, 6, 7, 8} into subsets of even size:

...

And 55 ways to slice a decagon into quadrilaterals:

decagon sliced into four quadrilaterals, 55 ways

Just as the Catalan partitions can be partially ordered, the Fuss–Catalan partitions can be too. Here are some Tamari lattice–like partial orderings.

partial ordering of 12345 partial ordering of 1234567 partial ordering of 123456789

This sequence—1, 1, 3, 12, 55, 273, 1428, 7752, 43263, …—is OEIS sequence A001764.

See R. P. Stanley, Enumerative Combinatorics Volume 2, Cambridge University Press, 1999, pp. 212, 234 (Exercise 6.33(c)); and Graham, Knuth, and Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1994, p. 361.

See also Martin Gardner, Time Travel and Other Mathematical Bewilderments, Chapter 20, W. H. Freeman, 1988.

Figures created with Mathematica 11.

Robert Dickau, 2016.

[ home ] || [ 2016-09-24 ]

robertdickau.com/fusscatalan.html