[Jprogramming] partitions

[Roger Hui]

The recurrence can be used to find the index of a partition
in the sorted list of partitions.  Thus:

   ] x=: \:~ 1+5 ?.@$ 10
10 7 6 5 3
   parti x
2834
   +/ x
31
   (part 31) i. <x
2834

pkn on large arguments needs some work; the double recursion
leads to repeated calls on the same arguments.

---------------------------------------

NB. all partitions of n
part =: 3 : 'final (, new)^:y. <<i.1 0'
final=: ; @: (<@-.&0"1&.>) @ > @ {:
new  =: (-i.)@# <@:(cat&.>) ]
cat  =: [ ;@:(,.&.>) -@(<.#) {. ]

pn=: 3 : 0       NB. # partitions of 0,1,2,...,n
 k=. 1+i.1+<.%:y.*2%3
 m=. <. y.-(-:k)*"1 ]_1 1+/3*k
 v=. ,1x
 for_i. i.-y. do. v=. v, -/+/(_1>.m-i){v,0 end.
)

pkn=: 4 : 0 " 0  NB. # partitions of n whose largest part is k
 k=. x. [ n=. y.
 if. (0>:k)+.(0>:n)+.k>n do. 0x
 elseif. (k=n)+.k=1 do. 1x
 elseif. 1 do. ((k-1) pkn n-1) + k pkn n-k end.
)

parti=: 3 : 0    NB. index of a partition
 (_1+{:pn +/y.) - +/ (i.&.<:&.>y.) +/@:pkn&> +/\. y.
)


----- Original Message ----- 
From: "Boyko Bantchev" <boykobb at gmail.com>
To: "Programming forum" <programming at jsoftware.com>
Sent: Tuesday, November 29, 2005 6:45 PM
Subject: Re: [Jprogramming] partitions

On 11/30/05, Roger Hui <RHui000 at shaw.ca> wrote:
> P(n,k) is the number of partitions of n into
> k parts, or equivalently, the number of partitions
> of n where the largest part is k.
>
> http://mathworld.wolfram.com/PartitionFunctionP.html
> equation 50 says that:
>
>    P(n,k)=P(n-1,k-1)+P(n-k,k)
>
> No proof or explanation was given.  Can anyone offer one?

All (n,k) partitions fall into two classes: those that only have
one summand that equals k, and those that have two or more
that large.  By removing a summand k, it becomes clear that
the second class has P(n-k,k) members -- that many are the
partitions of n-k with a largest summand (still) k.
To count the partitions of the first class, for each partition
subtract 1 from its (only) largest summand k.  Thus such a
partition corresponds to one of the kind (n-1,k-1): a partition
of n-1 with a largest summand k-1.  Conversely, for each
(n-1,k-1) partition, by adding 1 we obtain a partition of n with
precisely one summand k.  So there is a one-to-one
correspondence between the first class from above and the
(n-1,k-1) partitions.  Hence the formula.