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?

      Submitted by Bractals    
    No Rating
    Solution: (Hide)
    
    Let S(n) = { a_1 + a_2 + ... + a_m | 
                 m > 0,
                 a_1 + a_2 + ... + a_m = n, and
                 a_1 >= a_2 >= ... >= a_m >= 1 }
    
        H(n,n) = |S(n)|
    
        Search for "partition function" at
          mathworld dot wolfram dot com
    
    Example:
    
      S(4) = { 4, 3+1, 2+2, 2+1+1, 1+1+1+1 }
    
      H(4,4) = |S(4)| = 5
    
    
    I remember deriving this recursive formula in the early seventies while taking a course in abstract algebra. I think it had to do with finding the number of groups of order k (up to an isomorphism). Anybody know if this is correct?

    Comments: ( You must be logged in to post comments.)
      Subject Author Date
    Puzzle Thoughts K Sengupta2023-07-16 01:15:38
    Solutionre(2): But can I prove it? -- Visualization-- informal proofCharlie2005-09-10 13:35:16
    Some Thoughtsre: But can I prove it?Tristan2005-09-10 04:33:17
    Some ThoughtsBut can I prove it?Jer2005-09-09 16:52:56
    just a little resume to think laterpcbouhid2005-09-09 15:56:09
    Looking at Charlie´s posting..pcbouhid2005-09-09 15:23:06
    Some ThoughtsNo Subjectpcbouhid2005-09-09 15:19:00
    Some ThoughtsSome NumbersCharlie2005-09-09 15:07:15
    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 (8)
    Unsolved Problems
    Top Rated Problems
    This month's top
    Most Commented On

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