A233130 Number of negative formulas with two connectives (-> and *) and no variables.

1, 0, 2, 6, 38, 210, 1314, 8358, 55118, 370842, 2541626, 17668926, 124321750, 883614498, 6334772562, 45754956054, 332639032734, 2432189656362, 17874332863722, 131957567836206, 978161729926950, 7277592773408562, 54327287358246018, 406792963221032454

Offset

0,3

Comments

More precisely, a(n) is the number of negative 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ć and V. Kovač, On the fraction of IL formulas that have normal forms, arXiv:1309.3408 [math.LO], 2013.

Formula

Recurrence: a(0)=1, a(n) = sum_{k=0..n-1} (A151374(k)-a(k)) a(n-k-1).

G.f.: (-3 - sqrt(1-8*x) + sqrt(10 + 56*x + 6*sqrt(1-8*x))) / (8*x).

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)=0 because there are no negative formulas with 1 connective.
a(2)=2 because all negative formulas with 2 connectives are: (f->f)->f, (f*f)->f.
a(3)=6 because all negative formulas with 3 connectives are: ((f->f)*f)->f, ((f*f)*f)->f, (f->(f->f))->f, (f->(f*f))->f, (f*(f->f))->f, (f*(f*f))->f.

Mathematica

a[0] = 1;
For[n = 1, n <= 23, n++,
  a[n] = 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}]

Crossrefs

Sequence in context: A202737 A186648 A013033 * A267405 A027322 A085447

Adjacent sequences: A233127 A233128 A233129 * A233131 A233132 A233133

Keyword

nonn

Author

Vjekoslav Kovac, Dec 10 2013

Status

approved