one sequence, three conjectures, zero proofs

[Wouter Meeussen]

hi All,

Integer partitions are a seemingly inexhaustible source of surprises,
and the OEIS goes a long way in tying the relations together in an
accessible and user-friendly way.
An example with a funny twist at the end:

Look at the integer partitions gathered first by length and then by
first part:
n=7 gives (tab 1)

{{7}}
{{6,1}}                    {{5,2}}           {{4,3}}
{{5,1,1}}                {{4,2,1}}        {{3,3,1},{3,2,2}}
{{4,1,1,1}}            {{3,2,1,1}}      {{2,2,2,1}}
{{3,1,1,1,1}}        {{2,2,1,1,1}}
{{2,1,1,1,1,1}}
{{1,1,1,1,1,1,1}}

and note that the grouping (length=3;first part=3) contains 2 partitions
: {3,3,1} and {3,2,2}.
now, check the count of these groupings (unique elements, order
irrelevant, so 'sets'?)  for n=7:
 {1,3,3,3,2,1,1)

For n= 1 .. 10 this becomes :
(tab 2)

1
1    1
1    1    1
1    2    1    1
1    2    2    1    1
1    3    3    2    1    1
1    3    3    3    2    1    1
1    4    4    4    3    2    1    1
1    4    5    4    4    3    2    1    1
1    5    5    5    5    4    3    2    1    1

The first 6 lines coincide with A008284 : Triangle of partition numbers:
T(n,k) = number of partitions of n in which the greatest part is k, 1 <=
k <= n.
But from n=7 onward, the count of 'groupings' is less : more than one
partition can occur in  a 'grouping'.

This (tab 2) seems to have the property that along any column the entry
increases by 1 except when the row index i is divisible by i-j+1 with j
the column index.
So, it is conjectured that (tab 2) can be generated recursively by (tab 3) :
Clear[T];  T[_,0]:=1;
T[n_,k_]:=T[n,k]=T[n-1,k-1]+1-Boole[Divisible[n,n-k+1]];
Table[T[n,n-k],{n,0,9},{k,0,n}]//Grid
( I don't see why divisibility comes into play in the above).


Oh, here's the "funny twist at the end" :

The row sums of (tab 2) and (tab 3) seem to equal A309097 :: Number of
partitions of n avoiding the partition (4,2,1).
This one has a conjectured formula of it's own (by Jianing Song):
a(n) = (n^2 + 3n)/2 - Sum(k=1..n; Ceiling(n/k) ) and all 3 conjectures
agree with the data for n=0 .. 54  in A309097.
The 3 conjectures mutually agree for the first 100 terms at least.

Looks like we're over our ears in conjectures here. Where is AI when you
need it?  ;-)

Wouter.
--------------------------- Mma 11.0 -----------------
(tab 1) : n=6;Table[ GatherBy[IntegerPartitions[n,{k}],First] ,{k,n}]//Grid
(tab 2) :
Table[Length/@Table[Map[Length,GatherBy[IntegerPartitions[n,{k}],First],{1}],{k,n}],{n,10}]//Grid
(tab 3) : see recursion above.
-----------------------------------------------------------
ps. I'll submit (tab 3) as a new sequence if it is deemed to be
sufficiently interesting or important.
If so, then I'll add the relevant comments and links.

[Geoffrey Caveney]

Here is why divisibility determines when the entry does not increase by 1 along a column in Wouter Meeussen's (tab 2) :

Meeussen's (tab 1) of the integer partitions of n=7 gathered first by length and then by first part is a convenient example to illustrate the role of divisibility in (tab 2). The count of the groupings for n=7 is {1,3,3,3,2,1,1}, while (tab 2) indicates that the count of the groupings for n=6 is {1,3,3,2,1,1}. The question is, why is the number of groupings for length=2 and length=3 the same for n=7 as for n=6?

Consider length=2:

The partitions of 6 are {5,1}, {4,2}, {3,3}.

The partitions of 7 are {6,1}, {5,2}, {4,3}.

The partitions of 8 are {7,1}, {6,2}, {5,3}, {4,4}.

It is evident that when n is even, the partition {n/2, n/2} occurs, along with the partitions {n-1, 1}, {n-2, 2}, ..., {n/2 + 1, n/2 - 1}.

But when n is odd, there is no partition {n/2, n/2}. So the only partitions of length=2 are {n-1, 1}, {n-2, 2}, ..., {(n+1)/2, (n-1)/2}.

The value (n-1)/2 for odd n is the same as the value m/2 for even m = n-1. This is why the number of groupings of partitions of length=2 must be the same for odd n as for even n-1, and it is why the entry does not increase by 1 along the given column of (tab 2).

And for length=3:

The partitions of 6 are {4,1,1}, {3,2,1}, {2,2,2}.

The partitions of 7 are {5,1,1}, {4,2,1}, {3,3,1}, {3,2,2}.

The partitions of 8 are {6,1,1}, {5,2,1}, {4,3,1}, {4,2,2}, {3,3,2}.

The partitions of 9 are {7,1,1}, {6,2,1}, {5,3,1}, {5,2,2}, {4,3,2}, {3,3,3}.

The partitions of 10 are {8,1,1}, {7,2,1}, {6,3,1}, {6,2,2}, {5,3,2}, {4,4,2}, {4,3,3}.

It is evident that when n == 0 mod 3, its partitions of length n=3 have first parts n-2, n-3, ..., n/3.

When n == 2 mod 3, its partitions of length n=3 have first parts n-2, n-3, ..., (n+1)/3.

When n == 1 mod 3, its partitions of length n=3 have first parts n-2, n-3, ..., (n+2)/3.

This means that any n == 1 mod 3 has the same number of groupings of length=3 as n-1, but any n == 0 mod 3 or n == 2 mod 3 each has 1 more grouping of length=3 than n-1.

This is why the entry does not increase by 1 only for n == 1 mod 3 along the given column of (tab 2).

The same can be demonstrated for any length=k :

n == 0 mod k has partitions with first parts n-k+1, n-k, ..., n/k.

n == 1 mod k has partitions with first parts n-k+1, n-k, ..., (n+k-1)/k.

n == 2 mod k has partitions with first parts n-k+1, n-k, ..., (n+k-2)/k.

etc.

It follows that each n has 1 more grouping of length=k than n-1, EXCEPT for the case n == 1 mod k, which has the same number of groupings of length=k as n-1.

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/fa00cda5-63f3-4da8-93ea-ba56534af094%40gmail.com.

[Geoffrey Caveney]

Also, regarding Wouter's (tab 2) and his empirical observation that the sum of the terms in each row appear to equal the terms of A309097, which Jianing Song has conjectured to have the formula  a(n) = [(n^2 + 3n) / 2] - Sum(k=1..n; Ceiling(n/k)) :

Observe that (n^2 + 3n) / 2 can be rewritten as 

= (n^2 + 3n + 2 - 2) / 2 

= [(n^2 + 3n + 2) / 2] - 1

= [(n+1)(n+2) / 2] - 1

= [(n+1)^2 + (n+1) / 2] - 1

Now one may recognize the latter expression as the triangular number of (n+1) minus 1. Or in other words, the sum of the positive integers from 2 up to (n+1) inclusive.

Let us take the now-familiar example of n=7, and write this sum of integers as a row:

8 + 7 + 6 + 5 + 4 + 3 + 2

Now consider the Sum(k=1..n; Ceiling(n/k)), which naturally can also be written as sum of n integers in a row:

7 + 4 + 3 + 2 + 2 + 2 + 1

If one now subtracts each respective term in order, one gets precisely the terms of the row for n=7 in (tab 2) :

1 + 3 + 3 + 3 + 2 + 1 + 1

To check that this was not just some lucky coincidence, let us perform the same sequence of operations for n=10 :

Triangular number of (10+1) - 1 :

11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2

Sum(k=1..n; Ceiling(n/k)) :

10 + 5 + 4 + 3 + 2 + 2 + 2 + 2 + 2 + 1

Subtract to get the terms of the row for n=10 in (tab 2) :

1 + 5 + 5 + 5 + 5 + 4 + 3 + 2 + 1 + 1

And just to make sure that this works when n != 1 mod 3, we show these operations for n=9 and n=8 :

 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2

- (9 + 5 + 3 + 3 + 2 + 2 + 2 + 2 + 1)

= 1 + 4 + 5 + 4 + 4 + 3 + 2 + 1 + 1

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2

8 + 4 + 3 + 2 + 2 + 2 + 2 + 1

1 + 4 + 4 + 4 + 3 + 2 + 1 + 1

Geoffrey