# How do you define “independence” in combinatorics?

I feel like most definitions of “independence” are circular. Consider how we count the number of cards in a standard deck of cards: $$|S \times R| = |S||R|$$, where $$S$$ is the set of suits, and $$R$$ is the set of ranks. That is, $$S = \{\text{Hearts, Diamonds, Spades, Clubs}\}$$ and $$R = \{ 2,3,\dots,\text{King},\text{Ace} \}.$$ We know that $$|S| = 4$$ and $$|R| = 13$$, so $$|S \times R| = |S||R| = 4 \cdot 13 = 52.$$ In such an example, we define that they are independent, because they are disjoint subsets. But do we know that? In this example, it is “obvious.” What about examples where it is not obvious?

• Not sure this is clear. If you can't be sure of independence, then you can't blindly assume it. But I doubt that this is what you are asking...do you have an example in mind?
– lulu
Commented Oct 31, 2020 at 18:10
• To be clear, in the card example, we aren't "defining" anything. We are told (or we know from experience) that there are $4$ suits and that each suit contains $13$ ranks. That's all you need to do the calculation we indicate. If we were only told "there are some suits and each suit has some ranks" then you couldn't compute much of anything.
– lulu
Commented Oct 31, 2020 at 18:12
• In general, in early combinatorics you often learn that you can multiply two things (i.e. the “number of ways to either do something, or choices for something” when they are “independent.” But what exactly does that mean? Commented Oct 31, 2020 at 18:13
• Well, presumably the context would be something like "Our objects have a number of characteristics. Each characteristic has a known number of options and that number is independent of all of the other options." That is to say, if we know that that are $C_1$ options for the first characteristic, and $C_2$ for the second, then there are $C_1\times C_2$ ways to choose the first two characteristics. And so on.
– lulu
Commented Oct 31, 2020 at 18:21
• Most of the formal definitions of "independent" you gave are circular. And none of them are. Well, that's what to expect of empty sets..
– user436658
Commented Oct 31, 2020 at 18:58

Let's say you have a structure $$S$$. This structure is a combination of a few Attributes, each from a certain set of possible values.

If we let $$A_1,...,A_n$$ be the sets of the possible values for the corresponding attributes, then we can, pretty general, define the structure $$S$$ as follows:

$$S:= \{\pmatrix{x_1\\\vdots\\x_n}\in ⨉_{i=1}^n A_i\mid P\pmatrix{x_1\\\vdots\\x_n} \}$$

Where $$P$$ is a predicate, i.e. it models our constraints, on which combinations of attributes are allowed.

Our goal, as usual in combinatorics, is determining $$|S|$$.

We say that the structure $$S$$ is independent of an attribute $$A_i$$ is (in the combinatoric sense), if: $$\forall x_1\in A_1,...,x_n\in A_n,y_i\in A_i:\qquad P(x_1,...,x_i,...,x_n) = P(x_1,...,y_i,...,x_n)$$

Simply put this means that we don't need to look at the value of attribute $$A_i$$ to find out whether a specific instance of the structure is valid.
We therefore can fix a specific $$x_i\in A_i$$ (which exactly we choose doesn't matter), and define $$P': ⨉_{k=1\\i\neq i}^n A_k\to \{\text{True},\text{False}\}$$ via $$P'(x_1,...,x_{i-1},x_{i+1},...,x_{n}) = P(x_1,...,x_{i-1},x_i,x_{i+1},...,x_{n})$$

In terms of the cardinality, this then means the following: $$|S| =|A_i|\cdot |\{\pmatrix{x_1\\...\\x_{i-1}\\x_{i+1}\\...\\x_{n}}\in ⨉_{k=1\\k\neq i}^n A_k\mid P'\pmatrix{x_1\\...\\x_{i-1}\\x_{i+1}\\...\\x_{n}} \}|$$

As for every tuple $$\pmatrix{x_1\\...\\x_{i-1}\\x_{i+1}\\...\\x_{n}}$$, the structure instance $$\pmatrix{x_1\\...\\x_{i-1}\\x_i\\x_{i+1}\\...\\x_{n}}$$ is either valid for all choises of $$x_i$$, or for none of it.

To finish this, let's look at your example.
Our structure is the set of valid cards, where each card has the two attributes suit and rank.

Therefore we have $$n=2$$, $$A_1:= \{\text{Hearts, Diamonds, Spades, Clubs}\}, A_2:=\{ 2,3,\dots,\text{King},\text{Ace} \}$$.
Since we have no restrictions on our set members of $$S$$ besides that we have to pick from every attribute, we have further $$P(x_1,x_2)=\text{True}$$.

So, our structure $$S$$ is in this case independent of both $$A_1$$ and $$A_2$$, and therefore we have $$|S| = |A_1|\cdot |A_2|$$

To answer the question in the title: you don't. Independence is a concept in probability theory, not in combinatorics. In your card example, there is no concept of the sets $$S$$ and $$R$$ being independent. What you can say is that, if all $$52$$ cards are equally likely to be chosen in some experiment, then the probability of a particular rank, say ace, is independent of a particular suit, say clubs. But if one of the cards is sticky, and hence more likely to be chosen than the others, independence is lost.

You can look up the standard definitions of independence: for events $$E$$ and $$F$$, the events are independent if $$\Pr(E\cap F)=\Pr(E)\Pr(F)$$, or equivalently, if $$\Pr(E\vert F)=\Pr(E)$$.

Also, be careful to distinguish the concepts of disjointness and independence. They are not related.

Added: It looks like your question is really about sets that have the structure of a Cartesian product. If $$S=A\times B$$ and all elements of $$S$$ are equally likely, then the events $$X=$$"first element of tuple is $$x$$" and $$Y=$$"second element of tuple is $$y$$" are independent in the usual probability sense. These events are the sets $$X=\{(x,b)\vert b\in B\}$$ and $$Y=\{(a,y)\vert a\in A\}$$. Now $$\Pr(X\cap Y)=\Pr(\{(x,y)\})=\frac{1}{\lvert S\rvert}=\frac{1}{\lvert A\rvert\lvert B\rvert}$$, while $$\Pr(X)\Pr(Y)=\frac{\lvert B\rvert}{\lvert S\rvert}\frac{\lvert A\rvert}{\lvert S\rvert}=\frac{\lvert B\rvert\lvert A\rvert}{(\lvert A\rvert\lvert B\rvert)^2}=\frac{1}{\lvert A\rvert\lvert B\rvert}$$, so that the first definition of independence is satrisfied. This independence holds regardless of whether $$A$$ and $$B$$ are disjoint or not. (They might even be the same set.)

• Is disjointedness what is actually being referred to when independence is taught in a combinatorics course, but not talking about probability? Commented Oct 31, 2020 at 19:59
• I wouldn't think so. Can you give an example? Either a quotation or a reference to a book or online notes would be fine. Returning to the card example, the event ace is the set $\{AS,AH,AC,AD\}$, while the event clubs is the set $\{2C,3C,4C,5C,6C,7C,8C,9C,10C,JC,QC,KC,AC\}$. These events are not disjoint since they have non-empty intersection, $\{AC\}$. They are independent since $\Pr(\text{ace }\cap\text{ clubs})=\frac{1}{52}=\frac{1}{13}\cdot\frac{1}{4}=\Pr(\text{ace})\Pr(\text{clubs})$ (assuming all cards equally likely). The events clubs and hearts are disjoint; they are not independent. Commented Oct 31, 2020 at 21:42
• I would recommend that you have a close look at Sudix's answer and consider accepting it, as it does what you asked for, whereas mine does not. It should also help answer your question in the comment above: disjointness and independence are distinct concepts. Sudix's answer says nothing about whether the sets $A_j$ overlap or not; either may happen. Commented Nov 1, 2020 at 14:40

Here is another view point. Independence is a property of partitions, not of individual sets. Namely, let $$S$$ be a finite set, and let $$\{X_1,\dots,X_m\}$$ and $$\{Y_1,\dots,Y_n\}$$ be two partitions of $$S$$ (meaning the $$X_i$$ are nonempty, disjoint, and have a union of $$S$$, and same for the $$Y_i$$). We say that these two partitions are independent if $$|X_i\cap Y_j|\text{ is the same for all }i\in \{1,\dots,m\},j\in \{1,\dots,n\}$$ For example, let $$S$$ be a deck of cards, and let $$X_1=\{\text{the set of spades}\}=\{A\spadesuit,2\spadesuit,\dots,K\spadesuit\},\\X_2=\{\text{the set of hearts}\},\\ X_3=\{\text{the set of clubs}\}\\ X_4=\{\text{the set of diamonds}\}$$ and $$Y_1=\{\text{set of aces}\},Y_2=\{\text{set of twos}\},\dots,Y_{13}=\{\text{set of kings}\}$$ Since it is true that $$|X_i\cap Y_j|=1$$ for all $$i,j$$, we conclude these two partitions are independent.

A consequence of the definition of independence is that $$|S|=m\cdot n\cdot |X_1\cap Y_1|$$