A281270 a(n) is the number of closed BCK (a.k.a. affine) lambda terms of size n.

0, 0, 1, 2, 3, 9, 30, 81, 242, 838, 2799, 9365, 33616, 122937, 449698, 1696724, 6558855, 25559806, 101294687, 409363758, 1673735259, 6928460475, 29115833976, 123835124242, 532449210893, 2317382872404, 10199542298725, 45345006540851, 203704505953902, 924427259637953, 4234544300812834

Offset

0,4

Comments

It appears that for n >= 1, a(n + 5) == a(n) (mod 5), a(n + 38*7) == a(n) (mod 7), a(n + 30*11) == a(n) (mod 11) and a(n + 288*17) == a(n) (mod 17). - Peter Bala, Apr 11 2022

Links

Gheorghe Coserea, Table of n, a(n) for n = 0..201

O. Bodini, D. Gardy, and A. Jacquot, Asymptotics and random sampling for BCI and BCK lambda terms, Theor. Comput. Sci. 502: 227-238 (2013).

Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. (the authors of the paper incorrectly identified this sequence as A073950)

Pierre Lescanne, Quantitative aspects of linear and affine closed lambda term, arXiv:1702.03085 [cs.DM], 2017.

Formula

a(n) = 1 + a(n-1) + 2*Sum_{k=2..n-3} k*a(k) + Sum_{k=2..n-3} a(k)*a(n-1-k) for n>=2.

0 = 2*x^4*y' + (x-x^2)*y^2 - (1-x)^2*y + x^2, where y(x) is the g.f.

a(3*n+1) = Sum_{k=0..n-1} binomial(3*n,3*k+1)*A062980(k).

Example

A(x) = x^2 + 2*x^3 + 3*x^4 + 9*x^5 + 30*x^6 + 81*x^7 + 242*x^8 + ...

Mathematica

a[0] = a[1] = 0; a[n_] := a[n] = 1 + a[n - 1] + 2 Sum[ k a[k], {k, 2, n - 3}] + Sum[a[k] a[n - 1 - k], {k, 2, n - 3}]; Table[a@ n, {n, 0, 30}] (* Michael De Vlieger, Apr 02 2017 *)

Prog

(PARI)
seq(N) = {
  my(a = vector(N));
  for (n=2, N, my(s1 = sum(k=2, n-3, k*a[k]));
    a[n] = 1 + a[n-1] + 2*s1 + sum(k=2, n-3, a[k]*a[n-1-k]));
  concat(0, a);
};
seq(30)
\\ test: y = Ser(seq(201)); 0 == 2*x^4*y' + (x-x^2)*y^2 - (1-x)^2*y + x^2

Crossrefs

Cf. A062980, A262301, A267827.

Sequence in context: A277251 A275165 A073950 * A322752 A277345 A259943

Adjacent sequences: A281267 A281268 A281269 * A281271 A281272 A281273

Keyword

nonn

Author

Gheorghe Coserea, Apr 02 2017

Extensions

Name clarified by Pierre Lescanne, May 19 2017

Status

approved