Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let number of elements in a set be $1,2,3...n^2$ , for a given "n" . I want to know the number of subsets having "n" elements such that any two sub-sets have at most one element in common.
Example: For $n=2$, we have $\{1,2,3,4\}$ in the set. And number of subsets satisfying the above criteria is $\{1,2\}, \{3,4\}, \{1,3\},\{1,4\},\{2,4\},\{2,3\}$.
Note that any 2-element subset cannot occur as a subset of a chosen n-element subset more than once. Moreover, each n-element subset involves ${n}\choose{2}$ such subsets So $\frac{{n^2}\choose{2}}{{n}\choose{2}}$ is an upper bound. This is divisible by n, so there are no problems with us not being able to distribute subsets having different elements equally. Looking at a few example, this seems possible to achieve. eg.
1 2 3
1 4 5
1 6 7
1 8 9
2 4 8
2 5 7
2 6 9
3 4 6
3 5 9
3 7 8
4 7 9
5 6 8
Here's a construction that works if $n$ is a prime.
Instead of calling the elements $1,2,\dots,n^2$, I'll call them $(a,b)$ with $a,b$ running from 0 to 4. Given any two points $(a,b)$ and $(c,d)$, they define a unique line --- but do the arithmetic modulo $n$, and you'll get a line with exactly $n$ points. For example, let's take $n=5$, and consider the line through $(1,2)$ and $(4,3)$. It also goes through $(7,4)$, $(10,5)$, and $(13,6)$; working modulo 5, those points are $(2,4)$, $(0,0)$, and $(3,1)$.
The formula in Wonder's answer gives you the number of lines, and no two lines intersect in more than one point.
The technical name for all this is "the affine plane over the field of $n$ elements."
The construction doesn't work so well when $n$ isn't prime. E.g., when $n=4$, the line through $(0,0)$ and $(1,0)$ and the line through $(0,0)$ and $(1,2)$ intersect at two points, $(0,0)$ and $(2,0)$. Technically, what's happening here is that the integers modulo 4 don't form a field. But there is a field of 4 elements, and you can do the construction there, and get your 20 lines. This works as long as $n$ is a prime power, but fails otherwise. E.g., there is no field of 6 elements, so we need another idea if $n=6$.
