The set of natural numbers 1 through N is to be partitioned into two subsets A and B, with one restriction:
The number of elements in A is not a member of A and the number of elements in B is not a member of B.
How many ways are there to make these partitions?
My logic is flawed. The below is wrong:
A contains the cardinality of B, but not its own cardinality, so the split can't be equal.
if A has 1 element, it must be the cardinality of B:
there's 1 choice (or rather, way).
if A has 2 elements, one is the cardinality of B, and there are N-2 choices for the other.
if A has 3 elements, one is the cardinality of B, and there are C(N-2,2) choices of the other two.
if A has 4 elements, one is the cardinality of B, and there are C(N-2,3) choices of the other two.
etc. through floor(N/2).
The same total of the above also applies to B if B is the smaller set, so the above total is doubled.
N partitions
3 2
4 4
5 8
6 14
7 32
8 54
9 128
10 214
11 512
12 856
2*Sigma{a = 1 to floor(n/2)} C(n-2,a-1)
Table- shown is from:
for n = 3:12
w=0;
for a=1:floor(n/2)
if a~=(n-2)/2
ch=nchoosek(n-2,a-1);
w=w+ch;
end
end
disp([n,2*w])
end
Edited on March 21, 2024, 3:55 pm
|
|
Posted by Charlie
on 2024-03-21 13:45:01 |
solution
