A101481 Column 0 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.

1, 1, 1, 3, 19, 191, 2646, 46737, 1003150, 25330125, 735180292, 24103027865, 880627477269, 35469795883964, 1561107221731851, 74528004538789830, 3835467005270307663, 211648845813188932595, 12465477924609075602136

Offset: 0

Author

Paul D. Hanna, Jan 21 2005

Keywords

• nonn

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<=mA101481(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)

Examples

			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)
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Crossrefs

Cf. A101479, A101482, A101483, A226775.

Programs

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

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

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