All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Recursive Definition (Posted on 2005-09-09)
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?

 See The Solution Submitted by Bractals No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): But can I prove it? -- Visualization-- informal proof Comment 7 of 7 |
(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  3010   1   1   6  14  23  30  35  38  40  41  4211   1   1   6  16  27  37  44  49  52  54  55  5612   1   1   7  19  34  47  58  65  70  73  75  76  7713   1   1   7  21  39  57  71  82  89  94  97  99 100 10114   1   1   8  24  47  70  90 105 116 123 128 131 133 134 13515   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

 Search: Search body:
Forums (1)