Set size of a cartesian product

[guropalica]

Set S with n elements!
Set size of
{<x,y> | (X,Y are proper subsets of S), (X union Y = S)!
I tried doing something, but I'm stuck staring at a closed door, so I need a fresh start!
Any hints would be appreciated!

 

[CompuChip]

If X has k elements, then how many elements does Y have?
What is the minimum and maximum value for k?

Maybe you can try writing out all the combinations for n = 2 and n = 3 to get some feeling for the problem.

 

[guropalica]

If x has k elements, than Y has n-k to n-k elements at most!
Minimum value for k is 1, and max is n-1
It's pretty much pointless to write about 2 elements since that way I'd have only 2 cartesian products only since by the condition sets are not subsets so they can't be equal to the parent ie we get two sets of 1 element!
The same with 3 :/

 

[SteveL27]

If x has k elements, than Y has n-k to n-k elements at most!
/

X union Y = S is a big clue.

 

[CompuChip]

Is there a typo, or did you just mean "n - k elements exactly"? :-)

OK, here's another hint: how many different subsets of k elements can you choose from a set of n? In other words, how many possibilities are there for X?

 

[guropalica]

n-1 a typo...There are k^2 possibilities for X, and C of k from n for Y I think!
PS.Can we go more direct with hints I'm deadline's due 02:15 GMT :)

 

[CompuChip]

You're almost there, just take a moment to think it through.

C(n, k) is the number of k-element subsets you can make for X.

Then Y has to contain all the other elements (and, if X and Y don't need to be disjoint, any subset of X. How many of those are there?)

 

[guropalica]

C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
Thanks a lot guys

 

[guropalica]

C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
Thanks a lot guys