A242105 Number of sequences (x(k))_{k=1..n}, of n strictly increasing terms of nonnegative integers {x(1)<x(2)<...<x(n)}, satisfying x(k) <= k^2 for all k.

1, 2, 7, 44, 428, 5802, 102322, 2239844, 58849332, 1810039960, 63930543419, 2553881719348, 113979459829296, 5625823639358928, 304505544257483550, 17944306197698666740, 1144180970802458374244, 78517953136289477587608, 5771772521253777092098050

Offset

0,2

Comments

Also the first occurring nonzero terms in rows of triangle A261897, without repetitions. - Reinhard Zumkeller, Sep 06 2015

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

L. Haddad and C. Helou, Finite Sequences Dominated by the Squares, Journal of Integer Sequences, Volume 18, 2015, Issue 1, Article 15.1.8.

Formula

a(n) = Sum_{k=1..n} (-1)^{k-1}* C((n-k+1)^2+k-1,k) * a(n-k), for n>1.

a(n) = C(n^2,n-1) + C(n^2-1,n-1) - Sum_{k=2..n-1} C(n^2-k^2,n-k+1) *a(k-1), for n>1.

Conjecture: lim n->infinity a(n)^(1/n)/n = 2. - Vaclav Kotesovec, Feb 26 2017

Example

For n=2 the a(2) = 7 solutions are (0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4).

Maple

a:= proc(n) option remember; `if`(n<2, n+1, add((-1)^(k-1)*
       binomial((n-k+1)^2+k-1, k) * a(n-k), k=1..n))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 15 2014

Mathematica

a[0] = 1; a[1] = 2; a[n_] := a[n] = Sum[(-1)^(k-1)*Binomial[(n-k+1)^2+k-1, k]*a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 26 2017 *)

Crossrefs

Cf. A261897.

Sequence in context: A128579 A194453 A346258 * A001046 A158257 A348857

Adjacent sequences: A242102 A242103 A242104 * A242106 A242107 A242108

Keyword

nonn

Author

Charles Helou, Aug 14 2014

Status

approved