[seqfan] Re: Divisor partitions

Robert Dougherty-Bliss robert.w.bliss at gmail.com
Fri Mar 27 15:14:01 CET 2020

```David,

I agree with your suggestion, but the "reversal" process is difficult.
You can't put n + 1 into every subset that appears.

(I also don't see a picture attachment. Could you please try sending it
again, or to me personally if SeqFans doesn't allow attachments?)

I should mention the following "recurrence" I found, which is
essentially the same as your idea:

Let f(S) be the number of divisor partitions of a set S which does not
contain 0. Then, for any element x in S,

f(S) = f(S \ x) + D(S \ x, x),

where D(S \ x, x) is the number of divisor partitions of S where x
appears with some other element. After some reflection, it is the total
number of parts over all divisor partitions of S \ x such that every
element in the part is a divisor or multiple of x.

In summation notation:

D(S \ x, x) = sum([x | t or t | x for all t in part]
P divisor partition of S \ x,
part in P)

In general, this seems like a very nasty function. I only have one nice
case:

D(S \ 1, 1) = f(S \ 1).

Robert

On Fri, Mar 27, 2020 at 1:10 AM David Corneth <davidacorneth at gmail.com>
wrote:

> Hi,
>
> I attached an image that shows some sort of parent-child relation between
> solutions for n and n + 1 respectively.
> One can generate all solutions for n + 1 from all solutions for n with n =
> 0 the empty set. Proof: from a solution for n + 1, one can remove the
> number n + 1 from each set and then all resulting empty sets and keep only
> distinct solutions. It leaves all solutions for n. Reversing this from all
> solutions for n gives all solutions for n + 1.
> Does the image explain itself sufficiently?
>
> Best,
> David
>
> On Thu, Mar 26, 2020 at 4:32 PM Robert Dougherty-Bliss <
> robert.w.bliss at gmail.com> wrote:
>
> > Dear SeqFans,
> >
> > If you choose 11 numbers from the set {1, 2, ..., 20}, then there is at
> > least one pair such that one number in the pair divides the other, i.e.,
> > we get a "divisor pair."
> >
> > This is just the pigeonhole principle after noting that {1, 2, ..., 20}
> > can be partitioned into 10 parts such that any two numbers in the same
> > part form a divisor pair. I've been calling such partitions "divisor
> > partitions."
> >
> > Let a(n) be the total number of divisor partitions of [n] = {1, 2, ...,
> > n}, which begins as follows:
> >
> >     1, 2, 3, 7, 9, 25, 30, 78, 138, 342, 386, 1307
> >
> > a(n) does not seem to be in the OEIS, nor does the sequence "divisor
> > partitions of [n] into k parts" for most nice values of k. I've begun a
> > draft for a(n) at A333517.
> >
> > I've failed to find recurrences for a(n) or the corresponding "into k
> > parts" sequence, and I don't yet have a way to compute a(n) for n larger
> >
> > Does anyone have any insight into these sequences? Does something
> > related already appear in the OEIS?
> >
> > Robert
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

```