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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 19:35

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .