A047909 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).

1, 1, 1, 1, 5, 1, 1, 19, 47, 1, 1, 69, 1306, 641, 1, 1, 251, 31451, 195709, 11389, 1, 1, 923, 729811, 46922017, 50775091, 248749, 1, 1, 3431, 16928840, 10258694241, 162588279629, 20117051281, 6439075, 1, 1, 12869, 397222288, 2176464012941, 449363984934526, 1077273394836829, 11260558754404, 192621953, 1

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• tabl
• nice

Comments

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

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

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

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

Examples

			First few antidiagonals are:
  1;
  1,   1;
  1,   5,      1;
  1,  19,     47,        1;
  1,  69,   1306,      641,        1;
  1, 251,  31451,   195709,    11389,      1;
  1, 923, 729811, 46922017, 50775091, 248749,   1;
  ...
First few rows are:
  1,   1,        1,             1,                   1, ...
  1,   5,       47,           641,               11389, ...
  1,  19,     1306,        195709,            50775091, ...
  1,  69,    31451,      46922017,        162588279629, ...
  1, 251,   729811,   10258694241,     449363984934526, ...
  1, 923, 16928840, 2176464012941, 1162145520205261219, ...
  ...
		

Links

• Alois P. Heinz, Antidiagonals n = 1..50, flattened
• J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Crossrefs

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

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

Main diagonal gives A268485.

Programs

Maple

g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
      binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
      -1, l))), j=1..nops(l)-1))(add(i, i=l))
    end:
f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
         n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
h:= (n, k)-> f([n$k]):
seq(seq(h(1+d-k, k), k=1..d), d=1..10);  # Alois P. Heinz, Feb 11 2016
# second Maple program:
b:= proc(k, p, j, l, t) option remember;
      `if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,
       j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))
    end:
h:= (p, k)-> k!*(p*k)!*b(k, p-1, 1, 0, irem(k, 2)):
seq(seq(h(1+d-k, k), k=1..d), d=1..10);  # Alois P. Heinz, Mar 03 2016

Mathematica

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 *)

Formula

Reference gives explicit formula.

Extensions

New name, two terms corrected and more terms from Alois P. Heinz, Feb 08 2016