perplexus.info :: Just Math : Counting Partitions

Counting Partitions (Posted on 2024-03-21)

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?

No Solution Yet Submitted by Brian Smith

No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)

Puzzle Answer

| Comment 2 of 3 |

The required # ways is:

2*SUM} comb(n-2,a-1)

a= 1 to floor(n/2)

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, 9:44 pm

Posted by K Sengupta on 2024-03-21 14:29:16

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (15)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info