×   Home   Blog   Newsletter   Privacy   Contact Us   About

Horse Jumping

Rebecca likes to jump horses. She likes to practice jumping, and to keep things fresh, wants to practice with different configurations of fences.
Rebecca’s dad has seven modular fence components. These can be stacked in any combination to make fences of variable heights. For instance, all seven components could be stacked to make one single tall fence (Puissance style), or singly to make seven individual fences all a single unit tall. There are a plurality of configurations in between, for instance 2,2,2,1 or 1,2,1,3 or 1,5,1 …
If Rebecca always rides around the paddock in the same direction, how many distinct ways can her dad arrange for the components?
Above (not to scale) are a couple of representative configurations. Note, because the order the fences are encountered is important, {4,1,2} is considered a different course to {4,2,1} or {2,1,4} or any other arrangement of this triplet.
How many distinct fence configurations can be made with seven fences?
Let’s build up this:

One Component

With one component, there is only one configuration.

Two Components

With two components, they can be both stacked, or both singular, resulting in two configurations.

Three Components

With three components, they can be all stacked, all singular, or a two and a one (arranged two ways), for a total of four configurations.

Four Components

A quick exercise shows there are eight configurations with four components.

Five Components

Have you spotted a pattern yet? With five components there are 16 configurations.

More Components

ComponentsConfigurations
 11
 22
 34
 48
 516
 632
 764
You’ve probably seen the pattern by now that with n components there are 2n-1 configurations for the fences, so the answer is that there are 64 configurations for how Rebecca’s dad can arrange seven fence components.
Advertisement:

Why?

To see why, let’s think about the problem a different way. Rebecca will always be riding the fences from left to right, and first imagine all seven of the components are laying on the ground.
Imagine each component is separated by a barrier, which can either be present or not. If all the barriers are present, then each of the components is separate. However, if a barrier is removed, then those components can be merged.
If there are n components, then there are n-1 barriers.
Each barrier can be represented by a ‘1’ (if present), or by a zero ‘0’ (if missing), and you can see the presence, or not, of a barrier encodes to an n-1 digit binary number.
Each binary number represents a distinct combination of grouping of the components from [000000] (all together) through [111111] (all distinct).
The merged components configure to represent a unique fence layout for each binary number.

Image: Ian Mercer

Solution

Here are all 64 possible configurations for seven components.
{1,1,1,1,1,1,1} {1,1,1,1,1,2} {1,1,1,1,2,1} {1,1,1,1,3} {1,1,1,2,1,1} {1,1,1,2,2} {1,1,1,3,1} {1,1,1,4} {1,1,2,1,1,1} {1,1,2,1,2} {1,1,2,2,1} {1,1,2,3} {1,1,3,1,1} {1,1,3,2} {1,1,4,1} {1,1,5} {1,2,1,1,1,1} {1,2,1,1,2} {1,2,1,2,1} {1,2,1,3} {1,2,2,1,1} {1,2,2,2} {1,2,3,1} {1,2,4} {1,3,1,1,1} {1,3,1,2} {1,3,2,1} {1,3,3} {1,4,1,1} {1,4,2} {1,5,1} {1,6} {2,1,1,1,1,1} {2,1,1,1,2} {2,1,1,2,1} {2,1,1,3} {2,1,2,1,1} {2,1,2,2} {2,1,3,1} {2,1,4} {2,2,1,1,1} {2,2,1,2} {2,2,2,1} {2,2,3} {2,3,1,1} {2,3,2} {2,4,1} {2,5} {3,1,1,1,1} {3,1,1,2} {3,1,2,1} {3,1,3} {3,2,1,1} {3,2,2} {3,3,1} {3,4} {4,1,1,1} {4,1,2} {4,2,1} {4,3} {5,1,1} {5,2} {6,1} {7}