# Blogofbrew

home

## Transformation Analogues of Permutations

28 Jul 2014

We will go over some properties of transoformations that are similar to properties of permutations.

Lets start with the most basic, the number of transformations on n elements, OEIS_A000312.

$a(n) = n^n$

One ubiquitous equation involving permutations are the binomial coefficients. $${n\choose k} = {n!\over k! (n-k)!}$$

If we subsitute the factorial function for a(n) we get :

${a(n)\over a(k) a(n-k)}$

Combinatorially this equation takes all elements of order n then removes elements that match a pair consisting of one order k element and one order n-k element. By replacing a(n) with the number of transformations on n elements we obtain OEIS_A069322.

${n^{n}\over k^{k} (n-k)^{n-k}}$

##Monotonic runs

Another property of permutations is the [Eulerian numbers] (http://en.wikipedia.org/wiki/Eulerian_number), which count the number of elements that are greater than their previous element. For transformations they form OEIS_A22573.

##Unlabeled transformations

The number of unlabeled transoformations of $T_{n}$ is OEIS_A001372.

##Monogenic sizes

The histogram of single transformation generated (monogenic) semigroup sizes. The first column is OEIS_A000248, these are the idempotent transformations.

One theme that will come up reguarly is the connection between transformation composition and trees. OEIS_A00248 also counts forests with n nodes and height at most one.

Another way to view idempotent transformations is to partition the transformation elements into k nonempty parts, then designate a representitive of each to send all the other elements within that partition to.

The entire table is OEIS_A225725.

##Lolipop graphs of monogenic transformations

So what do monogenic transformation semigroups look like? Sort of like a lolipop. They have a tail then enter a cycle. The length of the tail is refered to as the index, and the length of the cycle is referred to as the period. Permutations are transformations with index zero. We can think of the tail as where elements get anhilated, and the cycle as when we reach a steady state number of elements.

Here is the lolipop generation graph triangle of cycle lengths First column is OEIS_A000272 Second column is OEIS_A163951 Third column is OEIS_A163952 Triangle is provisionally OEIS_A222029

Looking at the histogram of lolipop tail lengths for transformations generated by a single element The first column is OEIS_A006153 The table is OEIS provisionally http://oeis.org/A225540

##Transformations with k outputs OEIS_A090657

##Closed subsets OEIS_A001865 second column

OEIS_A065456 third column

1,18,305,5595 Forth column new to OEIS

OEIS_A060281 The entire triangle (without zeros)

##Derangements for $T_{n} = {(n-1)}^n$ OEIS_A065440 OEIS_A007778 Derangements (for permutations)