Let say I have a 'p' items 0 ... p . Next we divide them in two groups picking non overlapping numbers.
for example let p=4 and we split in two groups. All possible splits are 0:4, 1:3 and 2:2.
Lets take 2:2 split, possible group-permutations are :
( 1,2 ), (3,4)
( 1,3 ), (2,4)
( 1,4 ), (2,3)
( 2,3 ), (1,4)
( 2,4 ), (1,3)
( 3,4 ), (1,2)
no repetitions on the same row. And 1:3 split look like this :
(1), (2,3,4)
(2), (1,3,4)
(3), (1,2,4)
(4), (1,2,3)
(2,3,4), (1)
(1,3,4), (2)
(1,2,4), (3)
(1,2,3), (4)
and 0:4
(), (1,2,3,4)
(1,2,3,4), ()
How many grouping are possible given 'p' ? Taking into account all possible splits. And keeping in mind that the splits are only 2 i.e. 1:1:2 or 1:2:1 or 1:1:1:1 are invalid splits
Example thoughts on p=8 :
|8|7|6|5|4|3|2|1|
0:8 = 1 + 1
1:7 = 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
2:6 = 7 + 6 +...
hold 8,7 ... count 7..1
hold 8,6 ... count 6..1
hold 8,5 ... count 5..1
....
3:6 = ..
hold 8,7,6 ... count 6..1
hold 8,7,5 ..
=================
Which means :
(8 choose 0)+(8 choose 1) + (8 2) + .... = 2^p = 2^8 = 256