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
But can I prove it? by Jer)
Partition numbers?
Very interesting...
Perhaps this will help your proof:
In the first column of 1s (n=0) it seems only the first one is
important to the rest of the sequence. Let's consider the rest of
this column to be zeroes instead of 1s.
Now, there is an interesting pattern relating to partition numbers showing in each row:
1
01
012
0123
01345
013567
In each row, the numbers increase from left to right. By how
much do they increase? Here's a chart of the differences between
adjacent numbers in each row:
1
11
111
1211
12211
133211
1343211
What's so interesting about that? Each difference is equal to
the number of ways we can partition m into n pieces. For example,
that last row corresponds to m=7
7 1 way
6+1 = 5+2 = 4+3 3 ways
5+1+1 = 4+2+1 = 3+3+1 = 3+2+2 4 ways
4+1+1+1 = 3+2+1+1 = 2+2+2+1 3 ways
3+1+1+1+1 = 2+2+1+1+1+1 2 ways
2+1+1+1+1+1 1 way
1+1+1+1+1+1+1 1 way
So to expand our definition, H(m,n) seems to equal the number of
ways to write m as a sum of n or less positive integers, except when n=0
|
|
Posted by Tristan
on 2005-09-10 04:33:17 |
re: But can I prove it?
