A233396 Number of affirmative formulas with two connectives (-> and *) and no variables.

0, 2, 6, 34, 186, 1134, 7134, 46554, 310962, 2118502, 14657478, 102724802, 727695402, 5202222302, 37483252398, 271925724906, 1984561228386, 14560612258518, 107335786509078, 794597315522514, 5904817403594970, 44031888040118478, 329378395247260542, 2470999656320266746

Offset

0,2

Comments

a(n) is the number of affirmative formulas containing n connectives * or ->, n+1 appearances of symbol "f"=false, and parentheses.

Each negative formula is either "f", or is of the form "A->N", where A is a simpler affirmative formula and N is a simpler negative formula. Affirmative formulas are precisely those that are not negative.

The total number of formulas, both affirmative and negative, with n connectives * or -> is A151374(n).

Links

Vjekoslav Kovač, Table of n, a(n) for n = 0..1000

V. Čačić, V. Kovač, On the fraction of IL formulas that have normal forms, arXiv:1309.3408 [math.LO], 2013.

Formula

a(0)=0, a(n) = A151374(n) - Sum_{k=0..n-1} (A151374(k) - a(k))*a(n-k-1).

G.f.: (5 - sqrt(1-8*x) - sqrt(10 + 56*x + 6*sqrt(1-8*x))) / (8*x). [Typo corrected by Georg Fischer, Nov 09 2022]

The ratio a(n)/A151374(n) converges to 1/2 + 3*sqrt(17)/34 as n->infinity.

Asymptotics: a(n) ~ (1/2 + 3*sqrt(17)/34)*8^n/(sqrt(Pi)*n^(3/2)).

Example

a(1)=2 because all affirmative formulas with 1 connective are: f->f, f*f.
a(2)=6 because all affirmative formulas with 2 connectives are: (f->f)*f, (f*f)*f, f->(f->f), f->(f*f), f*(f->f), f*(f*f).

Mathematica

a[0] = 0;
For[n = 1, n <= 23, n++,
  a[n] = 2^n Binomial[2 n, n]/(n + 1) -
    Sum[(2^k Binomial[2 k, k]/(k + 1) - a[k]) a[n - k - 1], {k, 0,
      n - 1}]];
Table[a[j], {j, 0, 23}] (* or *)
CoefficientList[Series[(5 - Sqrt[1-8x] - Sqrt[10 + 56x + 6*Sqrt[1-8x]]) / (8*x), {x, 0, 35}], x] (* Georg Fischer, Nov 09 2022 *)

Crossrefs

Sequence in context: A026951 A030233 A362224 * A003499 A279609 A253778

Adjacent sequences: A233393 A233394 A233395 * A233397 A233398 A233399

Keyword

nonn

Author

Vjekoslav Kovac, Dec 10 2013

Status

approved