## The Twelvefold Way

[under construction]

Suppose you have balls to place into boxes. What are the ways you can do this if the balls/boxes are labeled vs unlabeled? Assume the balls are being labeled by i.n (often written ) and the boxes are being labeled by i.m, which is of course equivalent to ordering them. We can represent this situation as the problem of finding functions , where unlabeling or is equivalent to taking the equivalence classes of these functions under permutations of the domain or range. We can also ask to do this for only injective functions (ie every box contains at most one ball) or surjective functions (ie every box contains at least one ball).

In J we can write these functions as vectors of length with values in i.m. If the balls are unlabeled, then corresponding vectors are equivalent under permutations of their positions , so we choose the ordered vector as a representative function (ie 1 2 1 0 is represented by 0 1 1 2). If the boxes are unlabeled, then the vectors are equivalent under permuations of their values , so we might as well choose as the representative the one which has the smallest values available, left to right (ie 1 2 1 0 is represented by 0 1 0 2). If both balls and boxes are unlabeled, then we cannot simply use one to order the other anymore, so as a representative choose the function whose balls are ordered normally and whose boxes are ordered by the total number of balls in them (ie 1 2 1 0 is represented by 0 0 1 2.

I am currently in the process of filling in this table with J expressions.

Number of functions:

 All functions Injections Surjections Both labeled ^~ */@(-i.)~ Only [n] unlabeled ]!&<:+ ! !~&<: Only [m] unlabeled <: Both unlabeled <:

List of functions:

 All functions Injections Surjections Both labeled >@,@{@(#<@i.) dyadicperm Only [n] unlabeled wcomb comb Only [m] unlabeled i.@(<:,[) Both unlabeled i.@(<:,[)

wcomb=. (i.@<:@+ ((-.#+/\)@e.)"1 ]comb&<:+)
dyadicperm=. ,/@:(({~perm@#)"_1)@:comb

JordanTirrell/TwelvefoldWay (last edited 2012-06-27 16:52:26 by JordanTirrell)