Below T(n, k) denotes the number of permutations on n symbols decomposing consecutively into just k separate permutations, see A059438, A263484; a(n) = T(n, 1) denotes number indecomposable, see A003319. Kindly colleagues have pointed out to me an efficient algorithm for these numbers, under OEIS entry A059438 (sans row-reversal). Since the Mathematica program supplied there is not straightforward to decipher nor to motivate, a short discussion seems appropriate. Once pointed out it becomes obvious that every permutation, if decomposing into k parts, also decomposes into two permutations with k-l and l parts respectively, for any 0 <= l <= k . In particular, setting l = 1 yields the convolution: for k > 1 , T(n,k) = \sum_{k-1 <= i <= n-1} T(i,k-1) a(n-i) ; where a(n) = T(n, 1) may be computed separately for n > 0 via: a(n) = n! - \sum_{1 <= i <= n-1} i! a(n-i) . So in a nutshell T(n,k) equals the n-shifted k-fold convolution of a(n) . But that is a little tricky to spot immediately, because T(n,n-k) happens to be polynomial in n of degree k : a natural though fruitless initial response is to focus on these deceptively promising polynomials instead, suggesting a presumptive reason for the existence of mysteriously row-reversed A263484 in the first place. The reliance on a(n) may furthermore be eliminated by noticing that row n sums to n! ; whence for n > 0 , T(n,1) = n! - \sum_{2 <= i <= n} T(n,j) . Attention to argument support and evaluation order now produces the Maple program below, reasonably readable --- albeit compromised by logically vacuous "proc() ... end()" brackets necessary to circumvent one of Maple's numerous syntactic idiosyncrasies! Clean copy available at https://www.dropbox.com/s/8tdz9499suazcd2/A263484_%26_A059438.txt Fred Lunnon [16/06/19] ############################################################ restart; nmax := 12; krodel := proc(p, q) if p = q then 1 else 0 fi end; for n from 1 to nmax do for k from n by -1 to 1 do T[n][k] := proc() if k = 0 and n >= k then krodel(n, k) elif k = 1 then n! - add(T[n][k], k = 2..n) else add( T[i][k-1]*T[n-i][1], i = k-1..n-1) fi end() od od: [seq( [seq( T[n][k], k = 1..n)], n = 1..nmax)]; # triangle [seq( seq( T[n][k], k = 1..n), n = 1..nmax)]; # A059438 [seq( seq( T[n][n+1-k], k = 1..n), n = 1..nmax)]; # A263484 [seq( T[n][1], n = 1..nmax)]; # A003319 ############################################################ [ [1], [1, 1], [3, 2, 1], [13, 7, 3, 1], [71, 32, 12, 4, 1], [461, 177, 58, 18, 5, 1], [3447, 1142, 327, 92, 25, 6, 1], [29093, 8411, 2109, 531, 135, 33, 7, 1], [273343, 69692, 15366, 3440, 800, 188, 42, 8, 1], [2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1], [31998903, 6534978, 1135329, 200344, 37690, 7572, 1582, 328, 63, 10, 1], [392743957, 72754927, 11348623, 1786101, 300170, 54598, 10598, 2122, 417, 75, 11, 1], NULL]; On 6/15/19, Fred Lunnon <fred.lunnon@gmail.com> wrote:

I had not noticed that embarrassingly simple recurrence! WFL

On 6/15/19, Georg.Fischer <georg.fischer@t-online.de> wrote:

...

Hi Fred,

thank you. In the meantime Alois has extended the triangle to 150 rows. So the initial question and my change (which was a bit too hasty) are resolved. The MMA program in A059438 computes 150 rows in some 20 seconds.

@Alois: Thank you too, also for the typo.

Best regards - Georg

Am 14.06.2019 um 19:10 schrieb Fred Lunnon:

...

On 6/14/19, Fred Lunnon <fred.lunnon@gmail.com> wrote:

...

To: GF, AW, JS, CS ---

FYI attached A263484 & A059438 (rows reversed) for 1 <= n <= 12 .

This seems about as far as is reasonable to push my dumb Maple program (shared on request).

There are hints in Stanley (2005) of a somewhat faster algorithm, enumerating compositions or partitions instead of permutations; I don't currently quite see how to make that work.

By the way, note Comtet's generating function for the long diagonal A003319 .

WFL

On 6/13/19, Georg.Fischer <georg.fischer@t-online.de> wrote:

...

Christian Stump posted a note on <https://math.stackexchange.com/questions/3257689>.

I tried to put all together in <https://oeis.org/draft/A263484>: - Allan's comment and name change, - Fred's and Christian's "more" terms (up to row 9) - the link to the math.stackexchange.org discussion Please feel free to amend/change that draft.

Regards - Georg

-- Seqfan Mailing list - http://list.seqfan.eu/

-- Dr. Georg Fischer, Rotteckring 19, D-79341 Kenzingen Tel. (07644) 913016, +49 175 160 7788, www.punctum.com