login
Array read by antidiagonals upwards: h(n,k) = number of sequences with n copies each of 1,2,...,k and longest increasing subsequence of length k (n>=1, k>=1).
26

%I #49 Nov 02 2018 21:51:37

%S 1,1,1,1,5,1,1,19,47,1,1,69,1306,641,1,1,251,31451,195709,11389,1,1,

%T 923,729811,46922017,50775091,248749,1,1,3431,16928840,10258694241,

%U 162588279629,20117051281,6439075,1,1,12869,397222288,2176464012941,449363984934526,1077273394836829,11260558754404,192621953,1

%N Array read by antidiagonals upwards: h(n,k) = number of sequences with n copies each of 1,2,...,k and longest increasing subsequence of length k (n>=1, k>=1).

%C Old name was: Triangle of numbers arising from problem of complete increasing subsequences.

%C Table h_p(k) on page 80 in the Horton & Kurn reference has two typos. - _Alois P. Heinz_, Feb 05 2016

%C Conjecture: Column k > 1 is asymptotic to k^(k*n + 1/2) / (2*Pi*n)^((k-1)/2). - _Vaclav Kotesovec_, Feb 21 2016

%C Conjecture: Row k > 1 is asymptotic to sqrt(k) * (k^k/(k-1)!)^n * n^((k-1)*n) / exp((k-1)*(n+1)). - _Vaclav Kotesovec_, Feb 21 2016

%H Alois P. Heinz, <a href="/A047909/b047909.txt">Antidiagonals n = 1..50, flattened</a>

%H J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>

%F Reference gives explicit formula.

%e First few antidiagonals are:

%e 1;

%e 1, 1;

%e 1, 5, 1;

%e 1, 19, 47, 1;

%e 1, 69, 1306, 641, 1;

%e 1, 251, 31451, 195709, 11389, 1;

%e 1, 923, 729811, 46922017, 50775091, 248749, 1;

%e ...

%e First few rows are:

%e 1, 1, 1, 1, 1, ...

%e 1, 5, 47, 641, 11389, ...

%e 1, 19, 1306, 195709, 50775091, ...

%e 1, 69, 31451, 46922017, 162588279629, ...

%e 1, 251, 729811, 10258694241, 449363984934526, ...

%e 1, 923, 16928840, 2176464012941, 1162145520205261219, ...

%e ...

%p g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*

%p binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]

%p -1, l))), j=1..nops(l)-1))(add(i, i=l))

%p end:

%p f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(

%p n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):

%p h:= (n, k)-> f([n$k]):

%p seq(seq(h(1+d-k, k), k=1..d), d=1..10); # _Alois P. Heinz_, Feb 11 2016

%p # second Maple program:

%p b:= proc(k, p, j, l, t) option remember;

%p `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,

%p j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))

%p end:

%p h:= (p, k)-> k!*(p*k)!*b(k, p-1, 1, 0, irem(k, 2)):

%p seq(seq(h(1+d-k, k), k=1..d), d=1..10); # _Alois P. Heinz_, Mar 03 2016

%t g[l_] := g[l] = Function[n, f[l[[1 ;; -2]]]*Binomial[n-1, l[[-1]]-1] + Sum[ f[Sort[ReplacePart[l, j -> l[[j]] - 1]]], {j, 1, Length[l] -1}]][ Total[ l]]; f[l_] := Function [n, If[n<2 || l[[-1]]==1, 1, If[l[[1]]==0, 0, If[n == 2, Binomial[l[[1]] + l[[2]], l[[1]] ] - 1, g[l]]]]][Length[l]]; h[n_, k_] := f[Array[n&, k]]; Table[Table[h[1+d-k, k], {k, 1, d}], {d, 1, 10}] // Flatten (* _Jean-François Alcover_, Feb 19 2016, after _Alois P. Heinz_ *)

%Y Columns k=1-10 give: A000012, A030662, A047911, A268840, A268841, A268842, A268843, A268844, A268845, A268846.

%Y Rows n=1-10 give: A000012, A006902, A047910, A268847, A268848, A268849, A268850, A268851, A268852, A268853.

%Y Main diagonal gives A268485.

%K nonn,easy,tabl,nice

%O 1,5

%A _N. J. A. Sloane_

%E New name, two terms corrected and more terms from _Alois P. Heinz_, Feb 08 2016