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

Home > Numbers
Recursive Definition (Posted on 2005-09-09) Difficulty: 4 of 5
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.)
    Solution 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  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
    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 (2)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

    Chatterbox:
    Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information