[seqfan] Re: Divisor partitions

David Corneth davidacorneth at gmail.com
Thu Mar 26 22:48:33 CET 2020


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
> than about 25.
>
> Does anyone have any insight into these sequences? Does something
> related already appear in the OEIS?
>
> Robert
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list