login
A233396
Number of affirmative formulas with two connectives (-> and *) and no variables.
1
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
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
KEYWORD
nonn
AUTHOR
Vjekoslav Kovac, Dec 10 2013
STATUS
approved