OFFSET
0,4
COMMENTS
From Gerhard Kirchner, Apr 20 2017: (Start)
Also: Let U(n,i,k), k<=i<=n, be a triangular matrix with elements selected as "0" or "1" such that the partial sum of the first m rows is s(m)<=m for 1<=m<n and s(m)=m for m=n. A101481(n+1) is the number of possible selections.
U(n,i,k) has r(n) = n*(n+1)/2 elements. There are c(n) = binomial(r(n), n) ways to select n elements, some of which, however, are forbidden, see example. This yields the estimation a(n+1) < c(n).
Derivation of the recurrence:
s(m-1) <= m-1, say s(m-1)= j with 0 <= j <= m-1. Let f(m-1, j) be the number of associated submatrices. In order to determine f(m, k), k>=j, we have to distribute "1" k-j times among the m elements of row number m. There are binomial(m, k-j) ways to do that. The distribution must be repeated for each j. The recurrence describes this procedure. (End)
LINKS
Vaclav Kotesovec, Table of n, a(n) for n = 0..300
FORMULA
From Benedict W. J. Irwin, Nov 29 2016: (Start)
Conjecture: a(n) is described by a series of nested sums,
a(2) = Sum_{i=1..1} 1,
a(3) = Sum_{i=1..1+1}Sum_{j=1..i} 1,
a(4) = Sum_{i=1..1+2}Sum_{j=1..i+1}Sum_{k=1..j} 1,
a(5) = Sum_{i=1..1+3}Sum_{j=1..i+2}Sum_{k=1..j+1}Sum_{l=1..k} 1,
(End)
From Gerhard Kirchner, Apr 20 2017: (Start)
Recurrence: f(m,k) = Sum_{j=0..m-1} f(m-1,j)*binomial(m,k-j) with f(1,0) = f(1,1)= 1. a(n+1) = f(n,n). (End)
a(n) ~ c * exp(n) * n^(n-3/2) / 2^n, where c = (2 + LambertW(-2*exp(-2))) / (exp(2) * sqrt(2*Pi)) = 0.08604131405842589281435... - Vaclav Kotesovec, Apr 20 2017, updated Dec 03 2017
EXAMPLE
G.f. = 1 + x + x^2 + 3*x^3 + 19*x^4 + 191*x^5 + 2646*x^6 + 46737*x^7 + ...
This sequence can also be generated in the following manner.
Start a table with the all 1's sequence in row 0; from then on, row n+1 can be formed from row n by dropping the initial n-1 terms of row n and taking partial sums of the remaining terms to obtain row n+1.
The table below illustrates this method:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...;
[1], 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, ...;
[3, 9], 19, 34, 55, 83, 119, 164, 219, 285, 363, 454, ...;
[19, 53, 108], 191, 310, 474, 693, 978, 1341, 1795, 2354, ...;
[191, 501, 975, 1668], 2646, 3987, 5782, 8136, 11169, 15017, ...;
[2646, 6633, 12415, 20551, 31720], 46737, 66570, 92358, ...; ...;
In the above table, drop the initial n-1 terms in row n (enclosed in square brackets) and then take partial sums to obtain row n+1 for n>=1;
this sequence then forms the first column of the resultant table.
Note: column k of the above table equals column 0 of matrix power T^(k+1) where T=A101479, for k>=0.
From Gerhard Kirchner, Apr 20 2017: (Start)
n=3: 0 0 1 forbidden: 1
0 0 1 0 0 1 1 1
1 1 1 0 1 1 1 0 1 0 0 0
s(2)=0 s(2)=1 s(2)=2 s(2)=3>2
c(3) = binomial(6,3) = 20. There is only one forbidden matrix.
Thus: a(n+1) = a(4) = 19
Using the recurrence:
f(2,0) = f(1,0) = 1
f(2,1) = 2*f(1,0) + f(1,1) = 3
a(3) = f(2,2) = f(1,0) + 2*f(1,1) = 3
a(4) = f(3,3) = f(2,0) + 3*f(2,1) + 3*f(2,2) = 19
(End)
MATHEMATICA
a[ n_, k_: 1] := a[n, k] = If[ n < 2, Boole[n >= 0], Sum[a[n - 1, i], {i, n + k - 2}]]; (* Michael Somos, Nov 29 2016 *)
f[m_, k_] := f[m, k] = If[(m == 0 && k == 0) || (m == 0 && k == 1) || (m == 1 && k == 0) || (m == 1 && k == 1), 1, Sum[f[m-1, j]*Binomial[m, k-j], {j, 0, m-1}]]; Flatten[{1, Table[f[n-1, n-1], {n, 1, 20}]}] (* Vaclav Kotesovec, Apr 20 2017 after Gerhard Kirchner *)
PROG
(PARI) {a(n)=local(A=Mat(1), B); for(m=1, n+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i, B[i, j]=1, B[i, j]=(A^(i-2))[i-1, j]); )); A=B); return(A[n+1, 1])}
(PARI) {a(n, k=1) = if( n<2, n>=0, sum(i=1, n+k-2, a(n-1, i)))}; /* Michael Somos, Nov 29 2016 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Jan 21 2005
STATUS
approved