Define H(m,n) for m≥n≥0 by
H(m,n)=1, if n≤1
H(m,n)=Σi=1..nH(m-i,minimum(i,m-i)), if n>1
For any integer k>0, what do you think H(k,k) represents?
(In reply to
re: But can I prove it? by Tristan)
m\n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1
1 1 1
2 1 1 2
3 1 1 2 3
4 1 1 3 4 5
5 1 1 3 5 6 7
6 1 1 4 7 9 10 11
7 1 1 4 8 11 13 14 15
8 1 1 5 10 15 18 20 21 22
9 1 1 5 12 18 23 26 28 29 30
10 1 1 6 14 23 30 35 38 40 41 42
11 1 1 6 16 27 37 44 49 52 54 55 56
12 1 1 7 19 34 47 58 65 70 73 75 76 77
13 1 1 7 21 39 57 71 82 89 94 97 99 100 101
14 1 1 8 24 47 70 90 105 116 123 128 131 133 134 135
15 1 1 8 27 54 84 110 131 146 157 164 169 172 174 175 176
Let's take h(6,6), the number of ways of partitioning 6. And h(m,n) represents the number of ways of partitioning m using numbers no higher than n.
Largest partition is 1, adding to 6: 1 way (h(5,1)=1 as 1 is isolated and the 5 remaining need to be partitioned with partitions no greater than the 1 that has been isolated):
1+1+1+1+1 + 1 = 6
Largest partition is 2, adding to 6: 3 ways (h(4,2)=3 as 2 is isolated and the 4 remaining need to be partitioned with partitions no greater than the 2 that has been isolated):
1+1+1+1 + 2 = 6
1+1+2 + 2 = 6
2+2 + 2 = 6
Largest partition is 3, adding to 6: 3 ways (h(3,3)=3 as 3 is isolated and the 3 remaining need to be partitioned with partitions no greater than the 3 that has been isolated):
1+1+1 + 3 = 6
1+2 + 3 = 6
3 + 3 = 6
Largest partition is 4, adding to 6: 2 ways (h(2,2)=2 as 4 is isolated and the 2 remaining need to be partitioned with partitions obviously limited to 2):
1+1 + 4 = 6
2 + 4 = 6
Largest partition is 5, adding to 6: 1 way (h(1,1)=1 as 5 is isolated and the 1 remaining need to be partitioned with partitions obviously limited to 1):
1 + 5 = 6
Largest partition is 6, adding to 6: 1 way (h(0,0)=1 as 6 is isolated and the 0 remaining need to be partitioned with partitions obviously limited to 0):
0 + 6 = 6
Thus the necessity of using the minimum of i or m-i is seen in the switchover from not exceeding the chosen maximum value vs not exceeding the remainder to be distributed (the "obvious" limitation above).
|
|
Posted by Charlie
on 2005-09-10 13:35:16 |
re(2): But can I prove it? -- Visualization-- informal proof
