login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 26
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

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

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

FORMULA

Reference gives explicit formula.

EXAMPLE

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, ...

  ...

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

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.

Sequence in context: A168551 A262307 A144397 * A171243 A111577 A176242

Adjacent sequences:  A047906 A047907 A047908 * A047910 A047911 A047912

KEYWORD

nonn,easy,tabl,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 31 03:48 EDT 2020. Contains 333136 sequences. (Running on oeis4.)