Re: Question about integer partitions
- From: "Tim Peters" <tim.one@xxxxxxxxxxx>
- Date: Fri, 6 May 2005 21:49:17 -0400
[neuron posed the question of how many partitions of n contain a
partition of k (for k < n). Tim made up K(n, k) as a notation, and
showed
K(n, k) = K(n, n-k)
K(n, 1) = p(n-1)
K(n, 2) = 2*p(n-2) - p(n-4)
where p(n) is the # of partitions of n, with p(0)=1, and p(i)=0 for
i<0. Various attempts at "a nice solution" fizzled out.
]
[neuron]
>> I've gone down this path of trying to use counting and inclusion-
>> exclusion arguments, but I have not been smart enough to find
>> a reasonable general solution by these methods. Each larger n seems to
>> yield cases that aren't accounted for by hypothesized patterns based on
>> the previous n-1 cases.
[Tim Peters]
> At some level, there's "only one snag": viewing partitions as
> multisets, an n-partition N that extends two distinct k-partitions Ka
> and Kb, but where (Ka union Kb) is not a subset of N. That can't
> happen for k=1 or k=2, and the arguments so far nail it for K(n, 1)
> and K(n, 2) (and, by symmetry, K(n, n-1) and K(n, n-2)). n=7 k=3 is
> the next screwup, where
>
> 1 1 1 2 2
>
> extends both [1 1 1] and [1 2], but ([1 1 1] multiunion [1 2]) =
> [1 1 1 1 2] is not a multisubset of [1 1 1 2 2], so the arguments so far
> fail to realize that [1 1 1 2 2] is double-counted.
>> I'm thinking that it might be quite difficult to solve this problem by
>> these methods alone.
> Me too. I suspect that analyzing K(n, k) this way requires analyzing
> the possible overlaps across all the k-partitions. For k=1 and k=2,
> there aren't any possible overlaps, so those were easy cases.
So let's nail k=3. There are 3 partitions:
A. 1 1 1
B. 1 2
C. 3
How many partitions of n extend A? That's easily seen to be p(n-3), and
likewise for B and C.
How many extend at least two? p(n-6) extend A+C, and p(n-6) extend B+C.
A+B is trickier, as shown in the example above, but it's not really hard to
figure it out: viewed again as multisets, let "+" mean the form of multiset
union that assigns to each result element the larger of that element's
multiplicities in the operands ("max" might be a better name for this
operator ...). So [1 1 1]+[1 2] = [1 1 1 2], and p(n-5) extend that.
Finally, [1 1 1]+[1 2]+[3] = [1 1 1 2 3], and p(n-8) extend that.
Putting in the usual inclusion/exclusion +/- adjustments, "the answer" is
K(n, 3) = 3*p(n-3) - p(n-5) - 2*p(n-6) + p(n-8)
You can check that against the table of actual (computer-generated) counts I
posted earlier. I also confirmed it beyond the table, through n=50.
The earlier results for k=1 and k=2 are instances of the same kind of
analysis, but easier because there's no overlap to worry about.
The same kind of analysis works for larger k too, but it very quickly gets
very tedious to do it by hand (although it's easy for a computer program).
At this point, I have scant hope remaining that "a nice solution" exists.
Consider that if there _is_ such a thing, it must reproduce the equations
for the k=1,2,3 cases given above! They're simply messy, and don't appear
to reduce to anything simpler.
BTW, if anyone would like to see some _beautiful_ partition results (ugly
ones don't get published <wink>), this accounting by Herbert Wilf is highly
recommended:
Lectures on Integer Partitions
http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf
.
- References:
- Re: Question about integer partitions
- From: The Qurqirish Dragon
- Re: Question about integer partitions
- From: neuron
- Re: Question about integer partitions
- From: Tim Peters
- Re: Question about integer partitions
- From: neuron
- Re: Question about integer partitions
- Prev by Date: Re: abundance of irrationals!)
- Next by Date: Re: abundance of irrationals!)
- Previous by thread: Re: Question about integer partitions
- Next by thread: Re: Question about integer partitions
- Index(es):
Relevant Pages
|
