twice partitioned numbers
Jon Awbrey
jawbrey at oakland.edu
Tue Aug 21 14:08:50 CEST 2001
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Meeussen Wouter wrote:
>
> hi,
>
> has anyone ever encountered a problem where the
> partitioning of an integer was performed twice?
You are describing trees of constant height h
weighted by number of leaves k, in this case,
with h = 3 and k = 6.
> A flippant example would be:
>
> Take a search party of n people,
> and split it up into clusters
> according to any partition of n:
> if n=6, a possible partitioning
> is (3+3)
| h k
| 1 2 3 4 5 6
| 2 o o o o o o
| \|/ \|/
| 1 o o
| \ /
| \ /
| 0 @
> now, after a time, the organiser of the search
> decides to split 'm up even further :
> the possibilities are
> ( (3),(2+1),(1+1+1) ) *outer product* ( (3),(2+1),(1+1+1) ) equals
>
> ((3) ,(3)), ((3),(2+1)), ((3),(1+1+1)),
> ((2+1) ,(3)), ((2+1),(2+1)), ((2+1),(1+1+1)),
> ((1+1+1),(3)), ((1+1+1),(2+1)), ((1+1+1),(1+1+1))
>
> *** How many different results can be obtained after the second split? ***
> Remark that these are more diverse than the "plane partitions", since there
> is no restriction on the second 'dimension'.
>
> Can anyone come up with a better description or example?
> Table[Length[Flatten[Flatten[Outer[f,Sequence@@(Partitions/@#)
> ,1]]&/@Partitions[i]]],{i,20}]
>
> 1, 3, 6, 15, 28, 66, 122, 266, 503, 1027, 1913, 3874, 7099, 13799, 25501,
> 48508, 88295, 165942, 299649, 554545
>
> Although the Outer Product cooresponds better to the example above, a more
> sensible
> calculation uses the PartitionsP-count :
> Table[ Plus@@ Apply[Times,Partitions[i]/.i_Integer:>PartitionsP[i],2]
> ,{i,36}]
>
> {1, 3, 6, 15, 28, 66, 122, 266, 503, 1027, 1913, 3874, 7099,
> 13799, 25501, 48508, 88295, 165942, 299649, 554545, 997281, 1817984,
> 3245430, 5875438, 10410768, 18635587, 32885735, 58399350, 102381103,
> 180634057, 314957425, 551857780, 958031826, 1667918758, 2881852770,
> 4992747861}
>
> is it easy to set up a generating function for such a thing?
>
> PS.
> A third split *seems* to produce (but I need to check):
>
> Table[Plus@@((Apply[Plus, #/. i_Integer-> PartitionsP[i] ,{1}]/. f->Times)&
> /@
> Flatten[Flatten[Outer[f,Sequence@@(Partitions/@#)
> ,1]]&/@Partitions[w]]),{w,16}]
>
> {1, 5, 14, 51, 125, 429, 1039, 3258, 8254, 23554, 58934,
> 168803, 412177, 1114550, 2795446, 7345875}
>
> what would happen if we 'force' each integer >1 to
> split into at least 2 pieces, effectively forcing
> towards a deeply nested list of all ones?
> Do we end onto binary trees ?
>
> Wouter Meeussen
> tel +32 (0)51 33 21 24
> fax +32 (0)51 33 21 75
> wouter.meeussen at vandemoortele.com
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
More information about the SeqFan
mailing list