0

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
sten
  • 149
  • Are you able to write an expression counting the number of permutation in each of the three groupings you have listed? – Eric Towers Oct 05 '19 at 18:15
  • It seems like, in the end, you are looking all complementary (ordered) pairs of subsets of {1,2, ... ,p}. So there will be $2^p$ many such groupings, one for each subset of {1, ... , p}. – Ned Oct 05 '19 at 18:26
  • Why are you treating $(1,2)(3,4)$ (2:2, line 1) as different from $(3,4)(1,2)$ (2:2, line 6)? – Eric Towers Oct 05 '19 at 18:29
  • think of the split as a class0 and class1 .. then the numbers are classified differently .. once as class0 and once as class1 – sten Oct 05 '19 at 18:34

0 Answers0