A348901 G.f. A(x) satisfies: A(x) = 1 / (1 + x - 2 * x * A(2*x)).

1, 1, 5, 49, 893, 30649, 2030213, 264198625, 68180168717, 35046644401609, 35958357173552597, 73714882938928013809, 302083844634245306686685, 2475275541582550287356775001, 40559867144321249927245807932197, 1329146863668196853655964629931680001

Offset

0,3

Comments

Counts lower triangular (0,1) matrices with 1's on the diagonal which cannot be decomposed in a nontrivial block diagonal fashion. For example, the third time is 5, counting the matrices [100,110,111], [100,110,011], [100,010,111], [100,110,101], [100,010,101]. There are 3 other 3x3 lower triangular (0,1) matrices with 1's on the diagonal; those others have block decompositions. - David Speyer, Jul 09 2025

Links

Michael De Vlieger, Table of n, a(n) for n = 0..81

Johann Cigler, Hankel determinants of backward shifts of powers of q, arXiv:2407.05768 [math.CO], 2024. See p. 6.

Mare et al., Counting lower triangular 0-1-matrices with connected Coxeter permutation, MathOverflow, 2025.

Formula

a(0) = 1; a(n) = -a(n-1) + Sum_{k=0..n-1} 2^(k+1) * a(k) * a(n-k-1).

a(n) ~ 2^(n*(n+1)/2). - Vaclav Kotesovec, Nov 03 2021

G.f. A(x) satisfies 1/(1 - x*A(x)) = Sum_{n>=0} 2^(n(n-1)/2) * x^n. - David Speyer, Jul 09 2025

Mathematica

nmax = 15; A[_] = 0; Do[A[x_] = 1/(1 + x - 2 x A[2 x]) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
a[0] = 1; a[n_] := a[n] = -a[n - 1] + Sum[2^(k + 1) a[k] a[n - k - 1], {k, 0, n - 1}]; Table[a[n], {n, 0, 15}]

Crossrefs

Cf. A001003, A015083, A348188, A348902.

Sequence in context: A001819 A064618 A249588 * A396263 A363480 A193199

Adjacent sequences: A348898 A348899 A348900 * A348902 A348903 A348904

Keyword

nonn

Author

Ilya Gutkovskiy, Nov 03 2021

Status

approved