Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 atmost 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\}$.

share|improve this question
    
This is a variant on the Kirkman schoolgirls problem, which see. –  Gerry Myerson May 29 '12 at 12:29

2 Answers 2

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

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.