1
$\begingroup$

Now, I am going to define an operation on a list of numbers, which I will treat as a set, for want of a better approach. This may not be ideal, or even conventional, so apologies for lack of clarity from the start - clarity of notation os my goal in this question.

Example:

Given the set $\{1,2,3\}$ (for example the indices of the prime factorisation for $2250=2^1 3^2 5^3$), the first operation on that set is division into a specific subset-type, as illustrated below:

\begin{array}{l} &\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\\ &\{1\},\{1,2\},\{1,3\},\{1,2,3\}\}\\ &\{2\},\{1,2\},\{2,3\},\{1,2,3\}\}\\ &\{3\},\{1,3\},\{2,3\},\{1,2,3\}\}\\ &\{1,2\},\{1,2,3\}\}\\ &\{1,3\},\{1,2,3\}\}\\ &\{2,3\},\{1,2,3\}\}\\ &\{1,2,3\}\}\\ \end{array}

Then the products of each subset are taken:

\begin{array}{l} &\{1, 1, 2, 3, 2, 3, 6, 6\}\\ &\{1, 2, 3, 6\}\\ &\{2, 2, 6, 6\}\\ &\{3, 3, 6, 6\}\\ &\{2,6\}\\ &\{3,6\}\\ &\{6,6\}\\ &\{6\}\\ \end{array}

Then each row is summed:

$$\{24, 12, 16, 18, 8, 9, 12, 6\}$$

Note:

Duplicates are not treated any differently.

eg $\{1,1,2\}$ results in $\{12, 6, 6, 8, 3, 4, 4, 2\}$.

There are further operations on these, but these are trivial.

Could someone help me in notating the above sequence of operations using succinct, clear, and conventional notation please?

Update

The thing is, the operation in its entirity is terribly straightforward to code:

op[n_] := If[n == 1, {{1, 0}, {1, 1}}, 
With[{a = Transpose@FactorInteger[n]}, 
With[{b = Times @@@ Subsets[a[[1]]]}, 
With[{c = x[#] & /@ Range@Length@a[[2]]}, 
Transpose@{b, (-1)^PrimeOmega@b Reverse[(-1)^PrimeNu@n* 
Total[Times @@@ #] & /@ -(aa[c, #] & /@ Subsets[c] 
/. Thread[c -> a[[2]] + 1])]}]]]]

,but not at all straightfarward (as far as I can see) to denote using conventional notation Anyway, the operation gives

$$ \{\{ 1 ,24 \}, \{2 ,-12 \}, \{ 3 ,-16 \}, \{ 5 ,-18 \}, \{ 6 ,8 \}, \{ 10 ,9 \}, \{ 15 ,12 \}, \{ 30 ,-6 \}\} $$

Then using these coefficients for some sum.

Is this a hurdle for many combinatorial operations, preferably avoiding set notation?

$\endgroup$
  • 2
    $\begingroup$ I work in algebraic combinatorics and it's easy to draw nice pictures to describe what's going on, but when you get down to the notation it's hard to talk about it precisely. Open your mind a bit and accept that if you try to nail things down completely into utterly precise set theory it's going to be a nightmare. I did this initially for my undergraduate thesis and it was horrible. My advisor suggested, for example, I leave "boxes" (in tableaux) undefined. The concept of a set is often left undefined, so why not do the same for your basic objects? $\endgroup$ – Matt Samuel Jan 24 '16 at 3:25
  • 1
    $\begingroup$ Then you have cases where it's best to loosely describe things (such as which set you're summing over) and trust the reader to be able to write it down precisely if they need to. $\endgroup$ – Matt Samuel Jan 24 '16 at 3:27
  • $\begingroup$ @MattSamuel this sounds precisely what I am after - I don't suppose could persuade you to add an answer to this effect (with an example if poss.) could I? $\endgroup$ – martin Jan 24 '16 at 4:11
  • $\begingroup$ The specific thing you're doing actually has a rather sophisticated description in terms of filters on a partially ordered set. Does the order of the output matter? $\endgroup$ – Matt Samuel Jan 24 '16 at 4:22
  • $\begingroup$ @MattSamuel yes, order matters here. I will update with full function if that helps. $\endgroup$ – martin Jan 24 '16 at 4:31
2
$\begingroup$

A multiset is just like a set in that order doesn't matter, except repeated elements are allowed. As far as I know there is no standard notation for them, but you could use square brackets (as the other answer indicates, it's not correct to use curly braces). For example $$[1,1,2,3,4,4]$$ is a multiset where $1$ occurs twice, $2$ occurs once, etc.

If you have a multiset $A$, a submultiset $B$ has all of its elements contained in $A$ with the same or smaller multiplicity. There's no harm in writing $B\subseteq A$ to mean that $B$ is a submultiset of $A$.

Consider the lattice of submultisets of $A$ (this is just the set of all submultisets of $A$; a lattice is a particular type of partially ordered set where every pair of elements has a least upper bound and greatest lower bound). There are plenty of ways you could write this, but one way to do it would be $\mathcal{S}(A)$ (after defining what it means). $\mathcal{S}(A)$ is a partially ordered set where the partial ordering is given by $\subseteq$.

If $B\in \mathcal{S}(A)$, then the (principal) filter or upper order ideal generated by $B$ is the set of all elements of $\mathcal{S}(A)$ (so submultisets of $A$) that contain $B$ as a submultiset. This is what you're doing when you split things up into "subset types"; you're taking the principal filter generated by each element of $\mathcal{S}(A)$ separately. For $B\in\mathcal{S}(A)$ we can call this filter $\langle B\rangle$.

Now we can define $$\pi(B):=\prod_{b\in B}{b}$$ for $B\in\mathcal{S}(A)$, which is the product of all of the elements in the multiset. Then the sum of all these products in a filter (the "sum of the row") is given by $$\sum_{B'\in\langle B\rangle}{\pi(B')}$$ Equivalently (may even be easier, don't have to mention filters at all) you could just write $$\sum_{B\subseteq B'\subseteq A}{\pi(B')}$$ Then you indicate somehow how you put these in the appropriate order.

$\endgroup$
  • $\begingroup$ Realized "submultiset" is better. $\endgroup$ – Matt Samuel Jan 24 '16 at 4:48
  • $\begingroup$ thank you for your answer, this is really useful - do you know of any relatively accesible papers that employ this approach, in order to familiarise myself fully with its useage? NB Any of your own are welcome, I will not regard it as advertising or self promotion, since solicited! If, on the other hand you can think of any books / papers that are erudite examples of this approach that are not your own, I would also be most appreciative. $\endgroup$ – martin Jan 24 '16 at 4:49
  • 1
    $\begingroup$ @martin Besides the multisets this is all fairly standard notation, you just have to make definitions. You don't need to delve into lattice theory to do what you're doing I'm sure, so it might be enough to just look up multisets on Wikipedia. If you find yourself aching to study the more advanced aspects (which are almost surely unrelated to your problem) I learned it from Enumerative Combinatorics Volume 1 by Richard Stanley, which is a graduate textbook that assumes quite a bit of mathematical maturity. $\endgroup$ – Matt Samuel Jan 24 '16 at 4:56
  • $\begingroup$ many thanks for your help. I will leave the question open for 24hr as per SE etiquet, and then no doubt accept :) $\endgroup$ – martin Jan 24 '16 at 4:58
  • $\begingroup$ @martin No problem. $\endgroup$ – Matt Samuel Jan 24 '16 at 4:59
2
$\begingroup$

You should not use set-notation for sequences because $\{1,1,2\}=\{1,2\}$ as this denotes the set of objects listed or defined within the brackets. You should use subscripts or function-notation. A sequence of $n$ objects, not necessarily distinct, is written $(x_j){0\leq j<n}.$ This can also be described as the list of the values of a function $f$ with $dom (f)=\{0,...,n-1\},$ where $f(j)=x_j.$ The empty sequence ($n=0$) is the same thing as the empty set.) Each of your "specific types" is a set $T_A=\{(f(x))_{x\in B} :A\subset B\subset dom (f)\}.$ The "products taken" is the sequence $P_A= (\prod_{x\in B}f(x))_{A\subset B\subset dom (f)}.$(The product of the members of the empty set is $1$.) It is assumed here that you have a way to list $\{B : A\subset B\subset dom (f)\}$ as a sequence.

$\endgroup$
  • $\begingroup$ @user2584665 Yes, I know my using set notation for these types of operations is son-standard and confusing (even if I get around it by using "multiset") - thank you for your advice on this - I will read it through carefuylly, and try to digest it despite some terms being completely new to me - eg - what does $\operatorname{dom}$ mean, and where might I find appropriate references fior this? $\endgroup$ – martin Jan 24 '16 at 4:13
  • 1
    $\begingroup$ $dom (f)$ is the domain of the function $ f$. In my example, $dom(f)=\{0,...,n-1\}$ Sometimes written $ dom f$. Making an empty sum equal to 0 and an empty product equal to 1 are common conveniences, used in order to avoid the need for mentioning special cases. $\endgroup$ – DanielWainfleet Jan 24 '16 at 4:40
  • $\begingroup$ thanks - - I will look into it. Is it relevant to combinatorial operations? $\endgroup$ – martin Jan 24 '16 at 4:42
  • $\begingroup$ What "it" are you asking about ? $\endgroup$ – DanielWainfleet Jan 24 '16 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.