3
$\begingroup$

Let $A=\{1,2,...,n\}$. Let the powerset of $A$ be $\mathcal{P}(A)$.

We call $S\subseteq \mathcal{P}(A)$ a paired family of subsets if $\forall a\in A$, the number of elements of $S$ that contain $a$ is even.

For $|A|=n$, how many $S\subseteq \mathcal{P}(A)$ are paired?

$\endgroup$
1
  • $\begingroup$ I have found nothing beside basic or trivial results. For instance, the answer is bounded below by the number of pairs of nonempty disjoint subsets (since these sets with their union would be a paired set). $\endgroup$ Nov 10, 2018 at 8:08

1 Answer 1

5
$\begingroup$

Answer is $2^{2^n-n}$.

I'll give two (morally the same) proofs.

Proof Using Linear Algebra

Identifying subsets with indicator functions, we can view every $\mathcal{S}\subseteq\mathcal{P}(A)$ as an element of the $\mathbb{F}_2$-vectorspace $(\mathbb{F}_2)^{\mathcal{P}(A)}$. For each $a\in A$, define an $\mathbb{F}_2$-linear map $p_a\colon (\mathbb{F}_2)^{\mathcal{P}(A)}\to\mathbb{F}_2$ by $$S\in\mathcal{P}(A)\mapsto \begin{cases}1 & a\in S\\0 & a\notin S\end{cases}$$ so $p_a$ is counting whether $a$ appears in even or odd number of elements $S\in\mathcal{S}\subseteq\mathcal{P}(A)$ (exactly as in the condition of paired families). So counting paired families becomes a problem of counting elements in the common kernel of all $p_a$'s.

The set $\{p_a\mid a\in A\}$ is linearly independent (easy check), hence there are $n$ linearly independent conditions being put on $(\mathbb{F}_2)^{\mathcal{P}(A)}$. So the common kernel has dimension $\lvert\mathcal{P}(A)\rvert-n=2^n-n$ over $\mathbb{F}_2$, so $2^{2^n-n}$ paired families.

Proof Using Simple Counting/Probability

Without loss of generality, let $A=\{1,2,3,\dots,n\}$. Suppose we ask the question: What proportion of families will contain $1$ even number of times? We can argue the answer is one-half by the following observation: Pair off the elements of $\mathcal{PP}(A)$ as $\mathcal{S},\mathcal{S}\triangle\{\{1\}\}$, i.e. the pairs agree on all subsets of $A$ except the singleton $\{1\}$. Exactly one member from each pair will contain $1$ even number of times.

Continuing this argument for $2$, exactly one from each $$\mathcal{S},\mathcal{S}\triangle\{\{2\}\}$$ will have even number of $2$'s. Moreover, this is independent of the the number of $1$s, so a quarter of families have both even number of $1$'s and $2$'s.

Repeat for $3,\dots,n$ therefore gives us the probability of each element $1,2,\dots,n$ appearing even number of times is $2^{-n}$, because we have $\{1\},\{2\},\dots,\{n\}$ all can appear (or not) independently.

So the total number of paired families is $2^{-n}\cdot\lvert\mathcal{PP}(A)\rvert=2^{2^n-n}$.

$\endgroup$
4
  • $\begingroup$ Can you do it with probability, please! As a another answer (for a purpose of upvoting). $\endgroup$
    – nonuser
    Nov 10, 2018 at 8:44
  • $\begingroup$ @user10354138 I was trying to take an example if $A=\{1,2\}$ and I found only 3 paired families that are {phi}, {{1},{2},{1,2}}, and {phi,{1},{2},{1,2}}. But by your answer there must be $4$ paired families. Can you please tell me which one is the fourth? $\endgroup$ Nov 10, 2018 at 8:49
  • $\begingroup$ @FareedAF: The four families are $\varnothing,\{\varnothing\},\{\{1\},\{2\},\{1,2\}\},\{\varnothing,\{1\},\{2\},\{1,2\}\}$. $\endgroup$ Nov 10, 2018 at 8:52
  • $\begingroup$ Oh okay thank you... $\endgroup$ Nov 10, 2018 at 8:54

You must log in to answer this question.

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