|
%I #38 Dec 03 2017 17:27:17
%S 1,1,1,3,19,191,2646,46737,1003150,25330125,735180292,24103027865,
%T 880627477269,35469795883964,1561107221731851,74528004538789830,
%U 3835467005270307663,211648845813188932595,12465477924609075602136
%N Column 0 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.
%C From _Gerhard Kirchner_, Apr 20 2017: (Start)
%C 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.
%C 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).
%C Derivation of the recurrence:
%C 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)
%H Vaclav Kotesovec, <a href="/A101481/b101481.txt">Table of n, a(n) for n = 0..300</a>
%F From _Benedict W. J. Irwin_, Nov 29 2016: (Start)
%F Conjecture: a(n) is described by a series of nested sums,
%F a(2) = Sum_{i=1..1} 1,
%F a(3) = Sum_{i=1..1+1}Sum_{j=1..i} 1,
%F a(4) = Sum_{i=1..1+2}Sum_{j=1..i+1}Sum_{k=1..j} 1,
%F a(5) = Sum_{i=1..1+3}Sum_{j=1..i+2}Sum_{k=1..j+1}Sum_{l=1..k} 1,
%F (End)
%F From _Gerhard Kirchner_, Apr 20 2017: (Start)
%F 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)
%F 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
%e G.f. = 1 + x + x^2 + 3*x^3 + 19*x^4 + 191*x^5 + 2646*x^6 + 46737*x^7 + ...
%e This sequence can also be generated in the following manner.
%e 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.
%e The table below illustrates this method:
%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
%e 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...;
%e [1], 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, ...;
%e [3, 9], 19, 34, 55, 83, 119, 164, 219, 285, 363, 454, ...;
%e [19, 53, 108], 191, 310, 474, 693, 978, 1341, 1795, 2354, ...;
%e [191, 501, 975, 1668], 2646, 3987, 5782, 8136, 11169, 15017, ...;
%e [2646, 6633, 12415, 20551, 31720], 46737, 66570, 92358, ...; ...;
%e 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;
%e this sequence then forms the first column of the resultant table.
%e Note: column k of the above table equals column 0 of matrix power T^(k+1) where T=A101479, for k>=0.
%e From _Gerhard Kirchner_, Apr 20 2017: (Start)
%e n=3: 0 0 1 forbidden: 1
%e 0 0 1 0 0 1 1 1
%e 1 1 1 0 1 1 1 0 1 0 0 0
%e s(2)=0 s(2)=1 s(2)=2 s(2)=3>2
%e c(3) = binomial(6,3) = 20. There is only one forbidden matrix.
%e Thus: a(n+1) = a(4) = 19
%e Using the recurrence:
%e f(2,0) = f(1,0) = 1
%e f(2,1) = 2*f(1,0) + f(1,1) = 3
%e a(3) = f(2,2) = f(1,0) + 2*f(1,1) = 3
%e a(4) = f(3,3) = f(2,0) + 3*f(2,1) + 3*f(2,2) = 19
%e (End)
%t 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 *)
%t 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_ *)
%o (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])}
%o (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 */
%Y Cf. A101479, A101482, A101483, A226775.
%K nonn
%O 0,4
%A _Paul D. Hanna_, Jan 21 2005
|
