Wolfram Cloud Document

CITE THIS NOTEBOOK: A systematic approach to combinatorics word problems by Peter Burbery. Wolfram Community DEC 13 2022.

I will use the approach of the Maths fix where you ask a question (step 1), abstract it (step 2), compute the answer (step 3), and interpret the result (step 4).

Step 1: The questions

Here are some questions

How many ways can you place n marked/distinct/distinguishable/labeled marbles/balls/items into x marked/distinct/distinguishable/labeled urns/boxes/containers with no rules on placement?

How many ways can you place n plain/unmarked/indistinguishable/unlabeled marbles/balls/items into x marked/distinct/distinguishable/labeled urns/boxes/containers with no rules on placement?

How many ways can you place n marked/distinct/distinguishable/labeled marbles/balls/items into x plain/unmarked/indistinguishable/unlabeled urns/boxes/containers with no rules on placement?

How many ways can you place n plain/unmarked/indistinguishable/unlabeled marbles/balls/items into x plain/unmarked/indistinguishable/unlabeled urns/boxes/containers with no rules on placement?

we have two options here:

◼

plain/unmarked/indistinguishable/unlabeled

◼

marked/distinct/distinguishable/labeled

This can be abstracted to

◼

orbits allowed

◼

distinct functions f

To simplify calculations I use just marked and unmarked. However, you can use any of the other words. If I see a word problem that uses different words I can translate it to my example with marked for example from distinct or labeled.

we have two more options here:

◼

marbles/balls/items

◼

urns/boxes/containers

I'll use marbles and urns. As mentioned previously, other word problems might use different words.

This can be mathematically abstracted to

◼

set N

◼

set X

We have four options in total:

In[]:=

Tuples[{"unmarked","marked"},2]

Out[]=

{{unmarked,unmarked},{unmarked,marked},{marked,unmarked},{marked,marked}}

The mathematical abstractions are:

In[]:=

Tuples[{"orbit","distinct"},2]

Out[]=

{{orbit,orbit},{orbit,distinct},{distinct,orbit},{distinct,distinct}}

Here is what they correspond to:

In[]:=

AssociationThread[{"marbles","urns"}->##]&/@Tuples[{"unmarked","marked"},2]

Out[]=

{marblesunmarked,urnsunmarked,marblesunmarked,urnsmarked,marblesmarked,urnsunmarked,marblesmarked,urnsmarked}

In[]:=

AssociationThread[{"set N","set X"}->##]&/@Tuples[{"orbit","distinct"},2]

Out[]=

{set Norbit,set Xorbit,set Norbit,set Xdistinct,set Ndistinct,set Xorbit,set Ndistinct,set Xdistinct}

There are also three rules options.

◼

no rules on placement

◼

no multipacks allowed or no more than one thing in each container. At most 1.

◼

No empty boxes. At least 1.

This can be mathematically abstracted to be equivalent to:

◼

no rules on a function. any f allowed

◼

injective function

◼

surjective function

Now we have 12 options (3 times 4 from above). This is called the twelvefold way.

In[]:=

Dataset[AssociationThread[{"no rules","no multipacks","no empty urns"}->ConstantArray[AssociationThread[{"marbles","urns"}->##]&/@Tuples[{"unmarked","marked"},2],3]]]

Out[]=

	marbles	urns
no rules	unmarked	unmarked
	unmarked	marked
	marked	unmarked
	marked	marked
no multipacks	unmarked	unmarked
	unmarked	marked
	marked	unmarked
	marked	marked
no empty urns	unmarked	unmarked
	unmarked	marked
	marked	unmarked
	marked	marked

In[]:=

Dataset[AssociationThread[{"any f","injective f","surjective f"}->ConstantArray[AssociationThread[{"N","X"}->##]&/@Tuples[{"orbit","distinct"},2],3]]]

Out[]=

	N	X
any f	orbit	orbit
	orbit	distinct
	distinct	orbit
	distinct	distinct
injective f	orbit	orbit
	orbit	distinct
	distinct	orbit
	distinct	distinct
surjective f	orbit	orbit
	orbit	distinct
	distinct	orbit
	distinct	distinct

Step 2 Abstracting the question

Now we abstract the question. here is a picture of Wikipedia's table:

Here is a function that finds the answer:

In[]:=

functions=Function{x,n},Partition

,Binomial[x+n-1,n],

∑

k=0

StirlingS2[n,k],Length[IntegerPartitions[n+x,{x}]],

(x-n)!

,Binomial[x,n],Boole[n<=x],Boole[n<=x],x!StirlingS2[n,x],Binomial[n-1,n-x],StirlingS2[n,x],Length[IntegerPartitions[n,{x}]],{3}

Out[]=

Function{x,n},Partition

,Binomial[x+n-1,n],

∑

k=0

StirlingS2[n,k],Length[IntegerPartitions[n+x,{x}]],

(x-n)!

,Binomial[x,n],Boole[n≤x],Boole[n≤x],x!StirlingS2[n,x],Binomial[n-1,n-x],StirlingS2[n,x],Length[IntegerPartitions[n,{x}]],{3}

Step 3

Carry out the calculations. For example if we have 13 marbles and 23 urns we have:

Note the order is not 13 and then 23. I originally tried this but got the answer wrong when comparing it with my paclet function below.

In[]:=

functions[23,13]

Out[]=

{{504036361936467383,1476337800,27644437},{101,7124122778572800,1144066},{1,1,0},{0,0,0}}

I've also created a function in my RecreationalMathematics paclet available at the new Paclet Repository to perform this calculation named FindCombinatoricsWordProblemSolutions.

I would like to mention the functions that relate to word problems have a bug. I am working on fixing it but my GitHub clone is on version 1.15 and I need to get the updated documentation before I commit an update that patches the error.

Step 4 Interpret

To make interpreting the numbers above organized, I created a function named FindCombinatoricsDataset:

I also created a function to create questions like Wolfram Alpha's Problem Generator named CombinatoricsQuestionGenerator:

The function will check if the answer is right

Conclusion

I hope that this computational essay was helpful in understanding the systematic approach known as the twelve fold way. There is also the twenty fold way which I hope to cover later.

Bonus Section Twenty Fold Way

There's also the twenty fold way. This is a generalization developed by Kenneth P. Bogard in his book "Combinatorics Through Guided Discovery". There are four new cases introduced where the order of marbles matters. These are:

◼

placing marked marbles into an marked urn where the order in which you place marbles into the urn matters. For example, if you put one red in and then one green, this is not the same as putting one green marble in and then one red.

◼

The other case is that each urn contains at least one marble.

◼

The other two cases arise when the urn is unmarked.

The number of ways possible when you place marked marbles into unmarked urns such that the order the marbles are placed in the urn matters and the urns have no restriction on the number of marbles that are placed in them, you sum the Lah numbers.

The Lah number is given by

There's also a function for the number of orderless combinations. This is called the multichoose operator written as

This can be computed as

I have implemented this in my paclet as Multichoose.

Here is an example of how to solve a word problem with multichoose.

A recipe calls for 7 pinches of salt out of 12 types of salt. How many arrangements are there?

If you want to list all the combinations, there is a helpful resource function uploaded by Jon McLoone to the Function Repository named OrderlessCombinations. I added this to my paclet as OrderlessCombinations to make it easy to use when you install my paclet.

For a smaller example maybe there are 3 furniture items needed and 5 types of furniture available. List the possible arrangements:

What is the length?

This can also be computed with the twelve fold way:

The number of spots in the lists above--3--is like the number of marbles you can place in an urn. The marbles would be unmarked because the order of the choices of the furniture doesn't matter. The marbles would have to be marked for you to notice the order. The number of furniture items available to choose from--5--is like the number of urns. The urns would be marked because the types of furniture are distinct. This is why the following computation yields the same answer even though the question is different:

Here is a question:

Wikipedia overview

I'm going to use the Wikipedia article on the twelvefold way to explain the topic better.

Let N and X be finite sets. Let n=the number of elements in N and x be the number of elements in X. n and x are the cardinality of sets N and X, respectively. Here is how to compute this in Mathematica:

We will study the enumeration of equivalence classes of functions.

Combinatorics is the study of 4 things (source: The Art of Computer Programming (TAOCP) by Donald Ervin Knuth Volume 4A – Combinatorial Algorithms, Part 1 Chapter 7 Combinatorial Searching). I own a hard copy boxed set of volume 1-4A of TAOCP.

◼

the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,

◼

the existence of such structures that satisfy certain given criteria

◼

the construction of these structures, perhaps in many ways

◼

optimization: finding the “best” structure or solution among several possibilities, be it the “largest”, “smallest” or satisfying some other optimality criterion.

Combinatorics is part of discrete mathematics. I am a combinatorialist because I study combinatorics. I like writing combinatorial word problems.

Combinatorics includes the study of:

◼

mazes

◼

arc routing

◼

mutually orthogonal latin squares MOLS

◼

graphs

◼

and much more!!!

No condition: each a in N may be sent by f to any b in X, and each b may occur multiple times.

f is injective: each value f(a) for a in N must be distinct from every other, and so each b in X may occur at most once in the image of f.

f is surjective: for each b in X there must be at least one a in N such that f(a)=b, thus each b will occur at least once in the image of f.

There are four different equivalence relations which may be defined on the set of functions f from N to X:

◼

equality

◼

equality up to a permutation of N;

◼

equality up to a permutation of X;

◼

equality up to permutations of N and X.

The three conditions on the functions and the four equivalence relations can be paired in 3 × 4 = 12 ways.

The twelve problems of counting equivalence classes of functions do not involve the same difficulties, and there is not one systematic method for solving them. Two of the problems are trivial (the number of equivalence classes is 0 or 1), five problems have an answer in terms of a multiplicative formula of n and x, and the remaining five problems have an answer in terms of combinatorial functions (Stirling numbers and the partition function for a given number of parts).

The incorporation of classical enumeration problems into this setting is as follows.

◼

Counting n-permutations (i.e., partial permutations or sequences without repetition) of X is equivalent to counting injective functions N → X.

◼

Counting n-combinations of X is equivalent to counting injective functions N → X up to permutations of N.

◼

Counting permutations of the set X is equivalent to counting injective functions N → X when n = x, and also to counting surjective functions N → X when n = x.

◼

Counting multisets of size n (also known as n-combinations with repetitions) of elements in X is equivalent to counting all functions N → X up to permutations of N.

◼

Counting partitions of the set N into x subsets is equivalent to counting all surjective functions N → X up to permutations of X.

◼

Counting compositions of the number n into x parts is equivalent to counting all surjective functions N → X up to permutations of N.

Viewpoints

The various problems in the twelvefold way may be considered from different points of view.

Balls and boxes

Traditionally many of the problems in the twelvefold way have been formulated in terms of placing balls in boxes (or some similar visualization) instead of defining functions. I like using urns instead of boxes. I also like using marbles instead of balls. Other options for urns include containers, receptacles, backpacks, etc. Other options for marbles include things, items, particles, etc. I listed several options at the beginning.

The set N can be identified with a set of balls, and X with a set of boxes; the function ƒ : N → X then describes a way to distribute the balls into the boxes, namely by putting each ball p into box ƒ(p). A function ascribes a unique image to each value in its domain; this property is reflected by the property that any ball can go into only one box (together with the requirement that no ball should remain outside of the boxes), whereas any box can accommodate an arbitrary number of balls. Requiring in addition ƒ to be injective means forbidding to put more than one ball in any one box, while requiring ƒ to be surjective means insisting that every box contain at least one ball.

Counting modulo permutations of N or X is reflected by calling the balls or the boxes, respectively, “indistinguishable”. This is an imprecise formulation, intended to indicate that different configurations are not to be counted separately if one can be transformed into the other by some interchange of balls or of boxes. This possibility of transformation is formalized by the action by permutations.

Labelling, selection, grouping

A function ƒ : N → X can be considered from the perspective of X or of N. This leads to different views:

◼

the function ƒ labels each element of N by an element of X.

◼

the function ƒ selects (chooses) an element of the set X for each element of N, a total of n choices.

◼

the function ƒ groups the elements of N together that are mapped to the same element of X.

These points of view are not equally suited to all cases. The labelling and selection points of view are not well compatible with permutation of the elements of X, since this changes the labels or the selection; on the other hand the grouping point of view does not give complete information about the configuration unless the elements of X may be freely permuted. The labelling and selection points of view are more or less equivalent when N is not permuted, but when it is, the selection point of view is more suited. The selection can then be viewed as an unordered selection: a single choice of a (multi-)set of n elements from X is made.

For example my question furniture above would correspond better to no permutations because the function selects an element of set X for each element of N, a total of n choices.

Labelling and selection with or without repetition

When viewing ƒ as a labelling of the elements of N, the latter may be thought of as arranged in a sequence, and the labels from X as being successively assigned to them. A requirement that ƒ be injective means that no label can be used a second time; the result is a sequence of labels without repetition. In the absence of such a requirement, the terminology “sequences with repetition” is used, meaning that labels may be used more than once (although sequences that happen to be without repetition are also allowed).

I’m still working on understanding this next paragraph.

When viewing ƒ as an unordered selection of the elements of X, the same kind of distinction applies. If ƒ must be injective, then the selection must involve n distinct elements of X, so it is a subset of X of size n, also called an n-combination. Without the requirement, one and the same element of X may occur multiple times in the selection, and the result is a multiset of size n of elements from X, also called an n-multicombination or n-combination with repetition.

The requirement that ƒ be surjective, from the viewpoint of labelling elements of N, means that every label is to be used at least once; from the viewpoint of selection from X, it means that every element of X must be included in the selection at least once. Labelling with surjection is equivalent to a grouping of elements of N followed by labeling each group by an element of X, and is accordingly somewhat more complicated to describe mathematically.

Partitions of sets and numbers

When viewing ƒ as a grouping of the elements of N (which assumes one identifies under permutations of X), requiring ƒ to be surjective means the number of groups must be exactly x. Without this requirement the number of groups can be at most x. The requirement of injective ƒ means each element of N must be a group in itself, which leaves at most one valid grouping and therefore gives a rather uninteresting counting problem.

When in addition one identifies under permutations of N, this amounts to forgetting the groups themselves but retaining only their sizes. These sizes moreover do not come in any definite order, while the same size may occur more than once; one may choose to arrange them into a weakly decreasing list of numbers, whose sum is the number n. This gives the combinatorial notion of a partition of the number n, into exactly x (for surjective ƒ) or at most x (for arbitrary ƒ) parts.

There are several helpful partition functions:

◼

Partition is useful for partitioning arrays and sort of the inverse of ListConvolve. Partition accepts between 2 and 5 arguments and ListConvolve accepts up to 7 arguments:

◼

IntegerPartitions is used for partitions of an integer

Formulas

Formulas for the different cases of the twelvefold way are summarized in the following table; each table entry links to a subsection below explaining the formula:

The particular notations used are:

This is computed with FactorialPower

This is also called the falling factorial, descending factorial, falling sequential product, and lower factorial.

The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product, or upper factorial) is defined as

The falling and rising factorials are related to one another through the Lah numbers:

Unsigned Lah numbers (sequence A105278 in the OEIS):

Adapting the Karamata–Knuth notation for Stirling numbers, it has been proposed to use the following alternative notation for Lah numbers:

Since the falling factorials are a basis for the polynomial ring, one can express the product of two of them as a linear combination of falling factorials:

Several different notations for Stirling numbers are in use. Common notation for ordinary (signed) Stirling numbers of the first kind is:

For unsigned Stirling numbers of the first kind, which count the number of permutations of n elements with k disjoint cycles, is:

And for Stirling numbers of the second kind, which count the number of ways to partition a set of n elements into k nonempty subsets:

For example, the sum

is the number of all permutations, while the sum

is the nth Bell number. I can compute this with BellB.

Abramowitz and Stegun use an uppercase S and a blackletter S , respectively, for the first and second kinds of Stirling number. The notation of brackets and braces, in analogy to binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth. (The bracket notation conflicts with a common notation for Gaussian coefficients.)

Expansions of falling and rising factorials

Expansions of falling and rising factorials
Stirling numbers express coefficients in expansions of falling and rising factorials (also known as the Pochhammer symbol) as polynomials.

Stirling numbers of the second kind express the reverse relations:

and

Considering the set of polynomials in the (indeterminate) variable x as a vector space, each of the three sequences

is a basis. That is, every polynomial in x can be written as a sum

Falling factorials define, up to scaling, the same polynomials as binomial coefficients:

and

As inverse matrices

The Stirling numbers of the first and second kinds can be considered inverse of one another:

and

Although s and S are infinite, so calculating a product entry involves an infinite sum, the matrix multiplications work because these matrices are lower triangular, so only a finite number of terms in the sum are nonzero.

Example

For example, the sum of fourth powers up to n (this time with n included), is:

Here the Stirling numbers can be computed from their definition as the number of partitions of 4 elements into k non-empty unlabeled subsets.

Ideas for different symbols

I added a section where I tried testing ideas for different symbols to avoid conflicting notation. I think the solution is just more notation.

We have the following functions we need to write as

We have

We need to symbolize more than four so we add multiple layers:

We could keep going by adding more brackets: