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

¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤

```