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!)
A101481 Column 0 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'. 9
1, 1, 1, 3, 19, 191, 2646, 46737, 1003150, 25330125, 735180292, 24103027865, 880627477269, 35469795883964, 1561107221731851, 74528004538789830, 3835467005270307663, 211648845813188932595, 12465477924609075602136 (list; graph; refs; listen; history; text; internal format)
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

Cf. A101479, A101482, A101483, A226775.

Sequence in context: A229234 A090354 A119394 * A155805 A218261 A001517

Adjacent sequences:  A101478 A101479 A101480 * A101482 A101483 A101484

KEYWORD

nonn

AUTHOR

Paul D. Hanna, Jan 21 2005

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 November 28 06:42 EST 2021. Contains 349401 sequences. (Running on oeis4.)