Isomorphism Between Counting Functions and Drawing Balls

61 Views Asked by At

I have a question regarding associations between different formulations of counting problems. My fundamental conception of such problems is as quantities of functions counted via the twelvefold way, where the elements of the domains may or may not be distinguishable, the functions may or may not be required to be injective, the functions may or may not be required to be surjective, and the elements of the codomains may or may not be distinguishable. The bijective cases are sometimes dropped, as suggested by the name "twelvefold," but we'll keep all $16$.

Now for the associated formulations. From Wikipedia...

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. 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

A similar (perhaps simplified) Pre-Calculus class formulation consists of drawing balls from a bag without explicit reference to boxes. This would seem to be isomorphic to the special case of the Wikipedia formulation where each ball is placed into its own separate box.

One distinction typically made is whether the balls are drawn with replacement or without replacement. However, it seems to me that drawing balls with replacement violates right-uniqueness, annihilating the isomorphism between drawing balls and counting functions. My hunch after reading other formulations of counting problems is that drawing balls with replacement is supposed to permit only the violation of left-uniqueness (injectivity), but it seems to me that replacing a ball is isomorphic to reusing an element of the domain, not the codomain. Is this introductory Pre-Calc counting example unaccounted for by the function counting paradigm, the gold standard framework in Combinatorics (requiring instead the counting of left-total relations), or is my assumption that the Pre-Calc formulation is a special case of the Wikipedia formulation incorrect (perhaps the balls in the former are instead elements of the codomain)?

1

There are 1 best solutions below

4
On BEST ANSWER

In the terms used in the Wikipedia article, $N$ is the set of draws, $X$ is the set of balls in the bag. Drawing with replacement is modelled by arbitrary functions from $N$ to $X$, and drawing without replacement is modelled by injective functions from $N$ to $X$.

Added: This can also be modelled by balls and boxes: the draws are the balls, which are distinguishable, and the boxes are the balls in the bag. Drawing without replacement is equivalent to allowing at most one ball per box; drawing with replacement allows unrestricted distributions of the balls. This is different from the most common balls-and-boxes models, however, in that here the balls are distinguishable.