6
$\begingroup$

Consider a set of four elements $$ Y^0 = \{ y_1, y_2, y_3, y_4 \} $$ Let $Y^1$ be the set that includes all pairwise combinations of distinct elements of $Y^0$ $$ Y^1 = \{ y^1_1, \dots, y^1_6 \} := \{ \{y_1, y_2\}, \{y_1, y_3\}, \{y_1, y_4\}, \{y_2, y_3\}, \{y_2, y_4\}, \{y_3, y_4\} \} $$ By construction, each element of $Y^1$ contains each element of $Y^0$ at most once. Now let's build $Y^2$ as the pairwise combinations of distinct elements of $Y^1$ \begin{align} Y^2 &= \{ y^2_1 \dots, y^2_{15} \} := \\ & := \{ \ \{\{y_1, y_2\}, \{y_1, y_3\}\}, \ \{\{y_1, y_2\}, \{y_1, y_4\}\}, \ \{\{y_1, y_2\}, \{y_2, y_3\}\}, \dots, \ \{\{y_2, y_4\}, \{y_3, y_4\}\} \} \end{align} 12 elements of $Y^2$ are such that one element of $Y_0$ appears twice. 3 elements of $Y_2$ contain only distinct elements of $Y^0$.

At each step $N$ we build $Y^N$ as the set of pairwise combinations of distinct elements of $Y^{N-1}$.

Question: is there a way to know, given $N$, how many elements of $X_N$ include how many repetitions of elements of $X_0$? The information I am looking for is something like "$\ell$ elements of $X_N$ are such that they include an element of $X_0$ three times, another distinct element of $X_0$ two times and a third distinct element of $X_0$ one time" and so on, I am not interested in which specific elements of $X_0$ is repeated.

Addendum: I am adding a picture that should describe the generation of the nested sets better.

enter image description here

$\endgroup$
9
  • 1
    $\begingroup$ This looks like plethysm of the elementary symmetric function $e_2$ taken $N$ times, and then you are expressing it in terms of the monomial symmetric functions. Is that correct? $\endgroup$ – nobody Jun 6 '20 at 11:47
  • $\begingroup$ I have no idea of the terms you are using. I am building these sets as example for a method for information theory that I am developing. $\endgroup$ – Cesare Jun 6 '20 at 12:12
  • $\begingroup$ @MaxAlekseyev: No, I am not considering multisets the elements of $X_N$ are pairs of distinct elements of $X_{N-1}$. It is only by looking into the nested sets of sets down to level $N = 0$ that one finds the elements of $X_0$. But maybe it is possible to reformulate the problem in terms of multisets. I will add a picture that should describe the problem more clearly. $\endgroup$ – Cesare Jun 6 '20 at 17:31
  • 1
    $\begingroup$ $X_1$ is called the "set of 2-element subsets of $X_0$". And each element of $X_1$ contains (not "includes") every element of $X_0$ at most once. $\endgroup$ – YCor Jun 6 '20 at 17:39
  • 1
    $\begingroup$ I guess that from the combinatoric point of view that could probably lead to the same result. In my example I cannot, but that is another story. For me the $Y^N$ are random variables and I want to compute the mutual information between them (starting from equiprobable elements of $Y^0$). If I find a way to answer the question in my post I can compute the mutual information as a function of $N$. $\endgroup$ – Cesare Jun 6 '20 at 19:35
2
$\begingroup$

Define the signature of an element $t\in Y^N$ as a monomial $s_t(z_1,z_2,z_3,z_4):=z_1^{k_1}z_2^{k_2}z_3^{k_3}z_4^{k_4}$ where $k_i$ is the number of occurrences of $y_i$ in $t$. It is clear that $k_1+k_2+k_3+k_4=2^N$. Let $$S_N(z_1,z_2,z_3,z_4) := \sum_{t\in Y^N} s_t(z_1,z_2,z_3,z_4).$$ In particular, $S_N(1,1,1,1)=|Y^N|$ with numerical values listed in OEIS A086714.

From the definition of $Y^N$, it follows that $$S_{N+1}(z_1,z_2,z_3,z_4) = \frac{S_N(z_1,z_2,z_3,z_4)^2-S_N(z_1^2,z_2^2,z_3^2,z_4^2)}2.$$

In particular, we have $$S_0(z_1,z_2,z_3,z_4) = z_1+z_2+z_3+z_4,$$ $$S_1(z_1,z_2,z_3,z_4) = z_1z_2+z_1z_3+z_1z_4+z_2z_3+z_2z_4+z_3z_4,$$ $$S_2(z_1,z_2,z_3,z_4) = z_1^2(z_2z_3+z_2z_4+z_3z_4)+z_2^2(z_1z_3+z_1z_4+z_3z_4) + z_3^2(z_1z_2+z_2z_4+z_1z_4)+z_4^2(z_2z_3+z_1z_2+z_1z_3)+3z_1z_2z_3z_4.$$

There may exist a nice representation in terms of symmetric polynomials.


For example, in terms of monomial symmetric polynomials, we have: $S_0 = m_{(1,0,0,0)}$, $S_1 = m_{(1,1,0,0)}$, $S_2=m_{(2,1,1,0)}+3m_{(1,1,1,1)}$, $S_3=m_{(4,2,1,1)}+2m_{(3,3,1,1)}+m_{(3,3,2,0)}+5m_{(3,2,2,1)}+9m_{(2,2,2,2)}$, etc.

Here is a sample SageMath code:

m = SymmetricFunctions(QQ).monomial()
S = m[1]
for i in range(5):
  print i,":",S
  S = (S^2 - sum( t[1]*m[vector(t[0])*2] for t in S ))/2
  S = sum( t[1]*m[t[0]] for t in S if len(t[0])<=4 )

producing such representation for first few $N$:

0 : m[1]
1 : m[1, 1]
2 : 3*m[1, 1, 1, 1] + m[2, 1, 1]
3 : 9*m[2, 2, 2, 2] + 5*m[3, 2, 2, 1] + 2*m[3, 3, 1, 1] + m[3, 3, 2] + m[4, 2, 1, 1]
4 : 210*m[4, 4, 4, 4] + 141*m[5, 4, 4, 3] + 92*m[5, 5, 3, 3] + 59*m[5, 5, 4, 2] + 15*m[5, 5, 5, 1] + 59*m[6, 4, 3, 3] + 35*m[6, 4, 4, 2] + 22*m[6, 5, 3, 2] + 8*m[6, 5, 4, 1] + m[6, 5, 5] + 3*m[6, 6, 2, 2] + 2*m[6, 6, 3, 1] + 15*m[7, 3, 3, 3] + 8*m[7, 4, 3, 2] + 2*m[7, 4, 4, 1] + 2*m[7, 5, 2, 2] + m[7, 5, 3, 1] + m[8, 3, 3, 2]
$\endgroup$

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.