[seqfan] Progress on columns of "A005646 triangle"

[Robert Munafo]

Later today I realized that indeed my approach is very well suited to
computing the (smaller-valued) columns of the triangle.

Any valid classification of N types and R partitions can be turned into a
classification of N-1 types by removing any one type, and at most one
(now-redundant) partition.

It follows that all classifications with a given N and R can be found by
first enumerating all classifications for (N-1,R) and trying all possible
ways to add a type, followed by a similar process taking the classifications
for (N-1,R-1) and adding both a type and a partition.

Put another way, every entry in the triangle represents a set of solutions
that are easily derived from those in the position immediately above it and
those in the position to the immediate upper-left.

In practice this involves taking binary matrices of size N*R and adding rows
and columns, then testing in a complex way. I has already implemented most
of this as an efficiency optimization, the only remaining task was to simply
discarding any solution it finds that has too many partitions.

So, reading down each column, we have:

  0th column: 1, 0, 0, 0, ...
  1st column: 1, 0, 0, 0, ...
  2nd column: 1, 1, 0, 0, 0, ...
  3rd column: 2, 3, 3, 1, 1, 0, 0, 0, ...
  4th column: 3, 17, 36, 60, 56, 50, 27, 19, 6, 4, 1, 1, 0, 0, 0, ...

My program is currently working on the 5th column and has gotten as far as:
6, 74, 573, 2802, 10087, 26512, 55088, 91984, (Next term in progress.)

The column-sum sequence, thus far, is: 1, 1, 2, 10, 280, ... The only
candidate in OEIS is the formidable A003047 (cumulative product of itself
times Catalan(N): 1, 1, 2, 10, 280, 235200, 173859840000, ...) However,
given that column 5 already adds up to 187126, a column-sum of 235200 seems
too low.

Franklin wrote:

[...]
>
>> I'm also interested in a question that is much less approachable with the
>> development path you are following.  That is what happens at the "bottom" of
>> each column -- just before it becomes zeros.  Does this have a limit?  If
>> so, it would be 1,1,3,...., reading up the columns.  You would have to go to
>> at least N=14 to get a clue to whether anything of this sort is happening
>> (presumably the cases N=15 and N=16 can readily be shown to be 1).
>>
>> One can also ask about the column sums: 1,1,2,10,???
>>
>> Franklin T. Adams-Watters
>>
>> -----Original Message from: Robert Munafo
>> Andrew Weimholt and I have been working on A005646. Franklin T.
>> Adams-Watters suggested the importance of the triangle:
>>
>>   N=1   1
>>   N=2   0  1
>>   N=3   0  0  1
>>   N=4   0  0  1  2
>>   N=5   0  0  0  3   3
>>   N=6   0  0  0  3  17    6
>>   N=7   0  0  0  1  36   74   11
>>   N=8   0  0  0  1  60  573  358   23
>>   N=9   0  0  0  0  56 2802 7311 1631  47
>> N=10  0  0  0  0  50 10087 107938 83170 7563 106
>>
>>  I've copied in row 10 from a later post - FTAW.
>>>
>>
>> The main diagonal suggests a relation to sequence A000055, unlabaled
>> unrooted trees.
>>
>> [...]
>>
>

-- 
 Robert Munafo  --  mrob.com