# Pairwise combinations of distinct elements

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.

• 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? – nobody Jun 6 '20 at 11:47
• 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. – Cesare Jun 6 '20 at 12:12
• @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. – Cesare Jun 6 '20 at 17:31
• $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. – YCor Jun 6 '20 at 17:39
• 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$. – Cesare Jun 6 '20 at 19:35

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]