[math-fun] two kinds of partitions
As RKGuy would say, "probably well known to those who know it", but I found this cute: There are two kinds of partitions in common use: (a) Partitions of integers. p(5) = 7 partitions of 5, which are: 5, 41, 32, 311, 221, 2111, 11111. There's a complicated formula for p(n). (b) Partitions of sets. The 5 partitions of the set {abc} are abc, ab/c, ac/b, a/bc, a/b/c. There's a different complicated formula for these. The objects being partitioned are important in case B, while only the sizes of the pieces matter in case A. The other day, I realized that these two concepts could be joined together, with partitions of bags (multisets, sets with repeated elements). Case A is the partitioning of a bag with only one kind of element, {x,x,x,x,x}, while case B is the partitioning of a bag with all elements distinct {a,b,c}. The first nontrivial bag that's in between cases A and B is {a,a,b}, whose partitions are aab, aa/b, ab/a, a/a/b. So {aaa} has 3 partitions, {aab} has 4, and {abc} has 5. Case A has some interesting generalizations (planar partitions, cubic partitions, etc.). I don't know of similar notions for case B, or for bags. The generating functions for case A and case B are (of course) different, but have some similarities. Perhaps there's an in-between generating function for bag partitions. Rich
On 1/17/07, Schroeppel, Richard <rschroe@sandia.gov> wrote:
... The objects being partitioned are important in case B, while only the sizes of the pieces matter in case A.
The other day, I realized that these two concepts could be joined together, with partitions of bags (multisets, sets with repeated elements). ...
The same principle may be applied to permutations and combinations: the permutation is represented by a vector of n distinct integers modulp n, the combination by a vector comprising m 1's and n-m 0's, and the same algorithm may then be employed to generate either object. Plainly other bags of symbols lead to generation of intermediate "permbinations", enumerated by multinomial coefficients. A pleasant problem is to attempt to design such a generator algorithm utilising just one (adjacent?) transposition to construct each permbination from the previous one. Fred Lunnon
One can really fit this into a more general framework, which incorporates a lot of combinatorial structures. A very general form is: given two finite sets S and T, and a group G which acts on both S and T, how many functions are there from S to T up to the equivalence induced by G? One can also ask for the number of one-to-one function or the number of onto functions. (Not both; if |S| = |T|, the one-to-one and onto functions are the same; if |S| < |T|, there are no onto functions; and if |S| > |T|, there are no one-to-one functions.) In many cases of interest, the group G can be represented as a product H x I, where H acts on S and I acts on T. For ordinary partitions, S and T are both sets with n elements, and H and I are both S_n. For set partitions, I is S_n, but H is the trivial (one-element) group. If we take H as a cyclic group C_n, we get A084423 (Set partitions up to rotations). The case described of a partition of a multiset has H as the product of various S_{k_i}'s, where each S_{k_i} acts on a separate subset of k_i elements. (This gives A096443.) There are numerous other possibilities. For all these partitions, we can take T to be a set with k elements, k <= n, I = S_k, and ask for onto functions; this gives us the number of partitions in k parts - including the two dimensional partition function (A008284) and the Stirling numbers of the second kind (A000392). If H and I are both the trivial group, with |S| = n and |T| = k, there are k^n functions, including k!/(n-k)! one-to-one functions - the latter are permutations. On the other hand, we can take S = T (so G acts identically on them), |S| = n, and we are talking about endofunctions. If G is trivial, these are labeled endofunctions: n^n; if G = S_n, it's unlabled endofunctions (A001372). Taking |T| = 2 and S = T^n, with various choices for G we get a number of Boolean function counting sequences. I could go on. All of these are approachable by use of the Cauchy-Frobenius lemma (http://mathworld.wolfram.com/Cauchy-FrobeniusLemma.html), also commonly known as Burnside's lemma. How useful this approach is depends mostly on how complex the group G is. Franklin T. Adams-Watters ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
participants (3)
-
franktaw＠netscape.net -
Fred lunnon -
Schroeppel, Richard