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
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
KEYWORD
nonn
AUTHOR
Vjekoslav Kovac, Dec 10 2013
STATUS
approved