How many tuples? - Part 1

If $T$ has $a$ elements and we want a chain of $b$ -tuples, the general answer is $b^a.$ In this case, that is $10^7 = \fbox{10000000}.$

Here's a proof of the general fact. There is a bijection between the set of all such chains and the set of all functions $F: T \to \{1, \ldots, b\},$ as follows: given a chain satisfying the condition, let $F(t)$ be the index of the first set in the chain in which $t$ appears. Note that this is well-defined, since every $t$ appears in the last set. I'll leave the proof that it's a bijection to you (given a function $F,$ it's clear how to construct the chain that corresponds to $F$ ). The number of functions $F: T \to \{1, \ldots, b\}$ is just $b^a,$ since there are $b$ choices for the image of each of the $a$ elements of $T.$ So there are $b^a$ such chains.

(I must confess that my original proof was less elegant: Let $f(a,b)$ be the number of $b$ =tuples satisfying the condition on a finite set of $a$ elements. Then clearly $f(a,1) = 1$ for all $a.$ Now, suppose we choose $T_{b-1}$ of size $k.$ There are $\binom{a}{k}$ choices for such a set, and then the number of chains including $T_{b-1}$ as their penultimate element is just $f(k,b-1).$ So we get the recursion $f(a,b) = \sum_{k=0}^a f(k,b-1) \binom{a}{k}.$ Now it's clear by induction that $f(a,b) = b^a,$ since $b^a = \sum\limits_{k=0}^a (b-1)^k \binom{a}{k}$ by the binomial theorem (and the base case is $1^a = 1$ for all $a$ ). But once I realized that the answer was $b^a,$ then it was just a matter of thinking about what combinatorial set had that cardinality and constructing the appropriate bijection. So the first proof is much better.)