This is inspired by a card-game – the game involves cards with 8 different symbols printed on each, with the property that each pair of cards has exactly 1 symbol in common. That set us thinking – given an $n$-alphabet, what's the maximum number of $k$-sets of symbols such that each pair of $k$-sets has exactly one symbol in common? Formally:


Given $k,\ n,\ A = \{a\_1, …, a\_n\}$, maximise $s = s(k,n)$ such that


* $∃ S=\{S\_1, S\_2, …, S\_s\}$, and
* $∀ 1 ≤ t ≤ s,\ |S\_t| = k ∧ S\_t - A = ∅$, and
* $∀ 1 ≤ u, v ≤ s, |S\_u ∩ S\_v| = 1 $


Or a dual problem: to generate $m$ $k$-sets with the above property between any $2$ $k$-sets, how big must the alphabet be? 



Ways of choosing k items out of n with exactly one symbol in common
The kind of object you're looking at is exactly an $(r, \lambda)$-design for $\lambda = 1$ in combinatorial design theory.


An *$(r, \lambda)$-design* is an ordered pair $(V, \mathcal{B})$, where $\mathcal{B}$ is a collection of subsets of finite set $V$ such that every element of $V$ appears in exactly $r$ elements of $\mathcal{B}$, and every pair of distinct elements of $V$ appears in exactly $\lambda$ elements of $\mathcal{B}$.


Usually, the cardinalitys $\vert V \vert$ and $\vert \mathcal{B} \vert$ are written as $v$ and $b$ respectively. We call the elements of $V$ *points* and those of $\mathcal{B}$ *blocks*.


To see the equivalence, call each card a point, and each symbol a block. The set $A =\lbrace a\_1, \dots, a\_n \rbrace$ is the set $\mathcal{B}$ of blocks here, and you say a point is *contained* in block $a\_i$ if the corresponding card has the symbol $a\_i$ on it. Then setting $r = k$ and $\lambda = 1$, the above definition defines exactly what you described in the language of cards with symbols on them; every card has $k$ symbols (= every point appears $r$ times) and every pair of cards share exactly one symbol of $A$ (= every pair of points appear exactly once in a block in $\mathcal{B}$). The question you asked can be understood as "What's the maximum number of points in a $(k,1)$-design when the number of blocks is $n$?" To answer this, the basic relation between parameters of a nontrivial $(r, \lambda)$-design is:


$v \leq r(r-1)+1$ with equality if $r-\lambda$ is the order of a finite projective plane.


The following might also be helpful if you ask the same kind of question by fixing some parameters:


$b \geq v r^2/(r+\lambda(v-1))$,


$c\_i(r-\lambda+\lambda v - \lambda k\_i) \leq (r-\lambda)(r-\lambda +\lambda v)$, (c\_i is the size of the $i$th block or equivalently the number of cards that have the symbol $i$).


You can find more about $(r, \lambda)$-designs in chapter "(r, \lambda)-designs" by G.H.J. van Rees in the book "Handbook of Combinatorial Designs" edited by C.J. Colbourn and J. Dinitz.


Edit: The correct definition should allow the same subset of $V$ appearing more than once in $\mathcal{B}$, so $\mathcal{B}$ shouldn't be a set but a collection.


