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?
(In reply to
solution by Charlie)
ct=0;
for memb=1:n-1
s=combinator(n,memb,'c');
for i=1:size(s,1)
if ~ismember(memb,s(i,:))
if ismember(n-memb,s(i,:))
% disp(s(i,:))
ct=ct+1;
end
end
end
end
fprintf('%3d %5d ',[n ct])
end
forms the actual sets and counts:
N ways
3 2
4 2
5 8
6 10
7 32
8 44
9 128
10 186
11 512
12 772
13 2048
The eight sets of members of A for n=5 are
4
1 3
3 4
3 5
1 2 4
1 2 5
2 4 5
1 2 3 5The ten sets of members of A for n=6 are
5
1 4
3 4
4 5
4 6
1 2 3 5
1 2 3 6
1 2 5 6
2 3 5 6
1 2 3 4 6
The OEIS finds A202736
however the formula given begins with the value for our 3 as a=1:
For odd n, a(n) = 2^n, for even n, a(n) = 2^n - binomial(n,n/2).
For the puzzle's N, this becomes
For odd n, a(n) = 2^(n-2),
for even n, a(n) = 2^(n-2) - C((n-2),(n-2)/2).
Edited on March 21, 2024, 4:31 pm
|
|
Posted by Charlie
on 2024-03-21 16:25:09 |
re: solution
