Privacy Policy

March 21, 2016

The twelvefold pythonic way (WIP post)

As you may know, "What I cannot create I do not understand" is not only the motto of this blog but a tout-court didactic strategy. I thought we could inspect the Twelvefold way[2] using python to have a more practical grasp of abstract combinatorial concepts. In this post, I'll follow the same scheme of the wikipedia article. My aim is not to explain the TW better, but just take the most important concepts of the page, perhaps explain them with more examples, and put them together with some good old code.



Note:
I noted that in the years, I had to solve this kind of problems a numerous amount of time again and again, so it might be useful to be ready once and for all. A few weeks ago I started collecting information and code across the internet, and I gathered all of them here. I plan to update and refine this post in the next months, since some there are some snippet of code still missing. This post has to be intended as a draft/work in progress /alpha release, written during the study of the TW itself, therefore any suggestion or correction is welcome. It is not complete because I plan to start a very busy period soon, and I hope benefits for other will exceed the lack of completeness a decent work must have. Part of the code is not fully tested. I am not a mathematician, so forgive me any mistake (but tell me if you find any!). Links are given when code is not mine.

A few initial notes

One thing that I don't like is when a single (relatively simple) concepts has many different names. My little brain hurts with such confusion - enhanced by the fact that I'm not an English native speaker - and this paragraph is meant just to clarify a few initial concepts. Skip it if you don't need it. 

Before going ahead you might want to remember that, when speaking about "messing with objects together and counting": 
  • If the order does not matter, it is a combination.  
  • If the order does matter it is a permutation.
In other words: a permutation is combination where order matter. A permutation is a rearrangement, or sequence, of some elements. Since you can re-dispose back elements in the previous order, they are invertible, and can be thought as bijective function. As you can imagine, given $n$ elements, means that there are more permutation than combinations of those elements.

A permutation of legnth $k<n$ of a set of $n$ elements are sometimes called $k$-permutation, or even disposition. People also might say that ($k$-)permutations are a special case of dispositions where $k=n$.

With this information we can start thinking at the data structure we want to use for this concepts. Now to model a combination combination I would use a sets/frozensets, while for the permutation we might be good with tuples.


Twelvefold way

The Twelvefold Way (TW) is model for organizing combinatorial concepts into a table with the excuse of speaking on cardinality of equivalence classes of different kind of functions between 2 finite sets.

The functions $f : N \Rightarrow X$ can be grouped into injective, surjective, or any of those. These classes will be placed on different columns (the column for bijective function would be trivial to state).

Furthermore, we can group functions using four other equivalence relation, on the domain or in the image. The rows of the table represent four possible equivalence class: on the domain, on the image, on both, or on none of them.

We can consider those equivalence class:
  • equality: two elements belong to the same equivalence class only if they are equal (i.e. $ f1_(x) = f_2(x) \forall x \in X $ pretty much trivial equivalence class, one for each function, like not having equivalence class at all)
  • equality up to a permutation on $N$
  • equality up to a permutation on $X$: if $ [f_1(1), ... f_1(n) ]$ can be permuted into $[f_2(1), ... f_2(n)]$ then $f_1$ and $f_2$ would be in the same equivalence class. If we get out of an experiment $(1,2,3)$ would be the same as getting $(3,2,1)$.
  •  equality up to a permutation on both $N$ and $X$.
Therefore, all the possibile combinations are these: (Look at wikipedia for the table )
  1. Functions from $N$ to $X$
  2. Injective functions from $N$ to $X$
  3. Injective functions from $N$ to $X$ , up to a permutation of $N$
  4. Functions from $N$ to $X$ , up to a permutation of $N$
  5. Surjective functions from $N$ to $X$ , up to a permutation of $N$
  6. Injective functions from $N$ to $X$ , up to a permutation of $X$
  7. Injective functions from $N$ to $X$ , up to permutations of $N$ and $X$
  8. Surjective functions from $N$ to $X$ , up to a permutation of $X$ (Stirling numbers of the second kind).
  9. Surjective functions from $N$ to $X$
  10. Functions from $N$ to $X$ up to a permutation of $X$ (Bell's number)
  11. Surjective functions from$N$ to $X$ , up to permutations of $N$ and $X$
  12. Functions from $N$ to $X$ , up to permutations of $N$ and $X$
In the following, we try to add to the concepts the code for solving problems often related to such questions. Where possible, there is an example of such functions, or come code connected to the problem (i.e. how to calculate the number of those function, etc..). Some of the following class of function have a closed formula for calculation, some others don't.


  • A partition of a integer $n$ in $x$ parts is (aka integer partition ), is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. There are $p_x(n)$ partition of $n$ into $x$ parts.
  • A composition of an integer $n$ in $x$ parts: is a way of writing $n$ as the sum of a sequence of (strictly) positive integers. 
  • A partition of a set $N$ into $x$ subset decompose the set $N$ in $x$ (nonempty) different subset such as their union is the set $N$.

We define $n=|N|$ and $x=|X|$. For injective functions $n \leq x$, for surjective functions $x \geq n$ instead.

So... PoC || GTFO (cit.)

 

 

1) Functions from N to X

How many: $x^n$
Common name: Sequences with repetition (disposizioni con ripetizione), permutations with repetition.
Meaning: all the possible choices of length $k$ of $n$ elements. Given that now we may have repetitions, order is important. These are the possible password of length $n$ of $x$ characters, or the possible digits in a digital clock.Did you ever asked why the cardinality of the powerset of a set $S$ with $n$ element is $2^n$? That's because you can characterize all the subset of a set with function $\chi_{S}: S \to \left\{ True, False \right\}$.
python:


 

 

2) Injective functions from $N$ to $X$

How many: $ | P_{x,n} | = x^\underline{n} = \frac{x!}{x-n!}$
Common names: permutation of $n$ elements, partial permutations, n-permutations, permutations without repetition, sequences without repetition. The symbol $n^\underline{k}$ is often referred as falling factorial. When $X=N$ they are just referred as permutations.
Meaning: all the permutation of length $k$ of a set of $n$ elements.
You can not repeat element of $n$. If $k = n$ we have all the permutation of a set of $n$ elements: the usual $n!$. For these, order matter (the first element can be chosen upon $X$ different element, there's not a unique choice for the first element), as much as it metter for the first three people in a running race. You can't be first and second.
Python:



 

 

3) Injective functions from N to X, up to a permutation of N.

How many: $$ | C_{x,n} | = \binom{x}{n} = \frac{x^\underline{n}}{n!} = \frac{x!}{n!(x-n)!} $$
Common name: Simple combination: n-combination, combination without repetition (Combinazioni semplici)
Meaning and interpretation: you can organize a committee of $N=3$ members out of $X=6$ different person in $C_{6,3}= $ ways. Order does not matter (practically: there is indeed a division by n! which means that you quotient by the possible ordering of equivalence classes on $n$: all possible $n!$ permutation). It's formula is known as the binomial coefficient. This is how lotteries work. $\binom{x}{n}$ it is read $x$ choose $n$. It's value are those in the Pascal's triangle (aka Tartaglia's triangle).
Python:

And to calculate the binomial:
[code missing]

4) Functions from N to X, up to a permutation of N

How many:
$$ \bigg( \binom{x}{n} \bigg) = \binom{x+n-1}{n} =  \frac{x^\bar{n}}{n!} =\frac{( x + n - 1 )!}{n! * ( x - 1 )! }$$ .
Common name:  $n$-combination with repetitions, or $n$-multicombination, or multisubset of size n from a set X, combinations with repetition, combination with replacement, $n$-selection, $n$-multiset, or $n$-combination with repetition are often used. [7]
Meaning:  These represent multisubset of size $n$ from a set $X$. The number of n-multicombinations from a set with x elements can be seen to be the same as the number of $n$-combinations from a set with $x + n − 1$ elements. This reduces the problem to another one in the twelvefold way, namely the problem of Injective functions from $N$ to $X$ up to a permutation on $N$.  How many different cup of $|N|= 3$ balls of ice can I create out of $|X| = 5$ different tases (given that I take multiple balls of the same flavor and I don't mind the order flavor are chosen)? These are the number of compositions of the integer $x$ into $n$ parts.
Python:
If you feel lame, go here

And to calculate them, well.. that's simply this.



5) Surjective functions from N to X, up to a permutation of N

How many: $$ \binom{n-1}{n-x}  =\binom{n-1}{x-1} = \bigl( \binom{x}{n-1} \bigr)  $$
Common name: none that I know

Meaning: This case is equivalent to counting multisets with $n$ elements from X (as before), but with the added requirement to let each element of X occurs at least once. This is also equivalent to counting the compositions of $n$ with $x$ non-zero parts. There is an interesting method called Stars and Bars: to come up with this result: "Feller derives the same result directly as follows. Imagine to have  $x+1$ bars,  and $n$ stars lined up. You have to decide where to place the bars. We must place one bar before the first star and one after the last star. The remaining $x-1$ bars must be distributed among the $n-1$ spaces between stars. Thus, there are  $ \bigg( \binom{n-1}{x-1} \bigg)$ possibilities" [3]

Python:
[not yet]

 

6) Injective functions from N to X, up to a permutation of X

How many: $$ [n \leq x ] = $$
 =$1$ if $n \leq x$,  else $0$
Common name: none known.
Meaning: Since the function is injective, two elements of $N$ will be assigned the same element $X$. Moreover all elements of $X$ are the same for us. These can be view as the way of assigning labeled balls to unlabeled urn when there are more urn than balls.  It's like picking from a pocket $n$ out of $x$ metal(identical) marbles.

python: There is little point in this function. Any injective function from $N$ to $X$ is a good candidate. What would I do to show it is a good solution is to generate a set $A$ of all the possible injective function from $N$ to $X$ and show that, given a representative $r$ of this set, there's always a permutation from $r$  to all the element of the set $A$.


7) Injective functions from N to X, up to a permutation of N and X

How many: $$ [n \leq x ] = $$
 =$1$ if $n \leq x$,  else $0$
Common name: none known.

Meaning: Things don't get better if we apply also a permutation on $N$. It's like picking from a pocket $n$ out of $x$ metallic ( = identical) marbles. Each permutation of those $n$ balls is equal because marbles are equal.
Python:
As before.

 

8) Surjective functions from N to X, up to a permutation of X.

How many: $$ S(x, n) = \begin{Bmatrix}
x\\
n
\end{Bmatrix}$$

Meaning: Number of ways of expressing a set of $n$ elements as union of  exactly $k$ nonempty subsets. These are called Stirling number of the second kind. They have the same cardinality of all the possible $n$-equivalence classes of a set $X$. They answer the question: how many times do I have to toss a dice to get all of its faces? How many hashes should I generate before fulfilling the hash space? (you'll see... <3 )

Python:
Here is a nice question on Stackexchange of this problem, with a bunch of solutions, even one by Knuth.

If you just want to know what's the $x$-th,$n$-th Stirling number of the second kind, you just need to run:

For big value of $x$ and $x$ things gets complicated for a normal computer. There are not closed expressions without sums, but there's an explicit formula which use sums of binomial.
[todo]

 

9) Surjective functions from N to X

How many: $$ x! \begin{Bmatrix}
x\\
y
\end{Bmatrix}$$

Common name: nope
Meaning: There are $x!$ different possible way we can call one among all the possible surjective function from $N$ to $X$ up to a permutation of $X$. Since the function is surjective we have $x!$ ways for distinguish each of the equivalence class of the previous group.

Python:


The cardinality of this set is imply the cardinality of the previous set multiplied by $x!$.

 

10) Functions from N to X, up to a permutation of X (OK)

How many: $$ B_n = \sum_{k=0}^{n} \begin{Bmatrix}
n\\
k
\end{Bmatrix} $$
Common name: nope
Meaning: Number of partition of a set of $n$ elements. Rephrased: is the number of ways a set can be expressed as a union of any number of nonempty subsets. Since the set of functions from $N$ to $X$ up to a permutation of $X$ is equal to the set of surjective function plus the number of non-surjective function, we can make some sense of the formula above.


As you may note reading again the definition of Stirling numbers of the second kind, this class of function is just the sum of all the $S(x, n)$ for all $k$. This numbers are called Bell's Number.

Python:
A few years ago I used for SEPtAGe this nice library called PartitionSet.

11) Surjective functions from N to X, up to permutations of N and X

How many: $p_x(n) $
Common name:nope
Meaning: They are as much as the partition of the number $n$ into $x$ positive summands. The order of the summand does not matter.

Python:
There are billions of different example on the internet:

But if you need just the partition of the number in $k$ elements.. click here

As written in the answer: if you want all permutations: (i.e., $(1, 3)$ and $(3, 1)$ ) remove the call to sort function.


http://stackoverflow.com/questions/18503096/python-integer-partitioning-with-given-k-partitions

12) Functions from N to X, up to permutations of N and X

How many: $p_x(n+x)  ( \neq  \sum_{k=0}^{x} p_k(n)) $
Common name: nope
Meaning: This case is equivalent to counting partitions of the number $n$ into up to  $x$ nonzero addends. Unlabeled balls into unlabeled urns.
Python:
[todo]

13 (unsigned) Stirling number of the first kind:

Those are not part of the TW, but I felt they might find space in this page.
How many:  $$ | s(n,x) | = \begin{bmatrix} n\\ x \end{bmatrix} $$
Meaning: They count the number of permutations of $x$ elements with $n$ disjoint cycles. By cycle we mean exactly a reference to $S_n$, the symmetry group of order $n$.

python:
From here:





Conclusions:

Well, there's isn't much to say for this post. Another nice exercise can be to plot 3D graphs in order to know how does this functions growth. 


If it wasn't for the TW, probably id would have little "practical" sense to know the answer of those question singularly. With the TW it makes more senso, since it is a really nice idea, and it's somehow a "complete pill" of mathematics: there's nothing to extend. 

Moreover is nice to see patterns in the final table. For instance:
  • The formulas for the non-injective and non-surjective functions resemble often a summation (or something else) over the simpler surjective case.

#lolfact1: IIRC, Rota, the author of the TW,  was the PhD supervisor of my professor of Graph Theory.
#lolfact2: According to the comments (and after my check) I corrected this stackoverflow question.

References and links:

In addition to pdf, code, articles linked in this post, it might be cool to read the following:

[1] http://www.mathsisfun.com/combinatorics/combinations-permutations.html - Clear and fun :D

[2] https://en.wikipedia.org/wiki/Twelvefold_way - I studied from this article. It's also the skeleton of this post and I have taken most of the content from the article. (Beware however, there are some errors or imprecision on wikipedia.)

[3] http://www.johndcook.com/TwelvefoldWay.pdf  - Explanation in term of labeled, unlabeled balls and urns.

[4] https://people.sc.fsu.edu/~jburkardt/py_src/monomial/i4_choose.py

[5] http://people.sc.fsu.edu/~jburkardt/py_src/subset/comp_enum.py

[6] http://adorio-research.org/wordpress/?p=11460 - Useful python code

[7] https://en.wikipedia.org/wiki/Combination

daje regà