login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A233130 Number of negative formulas with two connectives (-> and *) and no variables. 1
1, 0, 2, 6, 38, 210, 1314, 8358, 55118, 370842, 2541626, 17668926, 124321750, 883614498, 6334772562, 45754956054, 332639032734, 2432189656362, 17874332863722, 131957567836206, 978161729926950, 7277592773408562, 54327287358246018, 406792963221032454 (list; graph; refs; listen; history; text; internal format)
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-8x) + sqrt(10 + 56x + 6*sqrt(1-8x))) / 8x.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 08:44 EST 2019. Contains 329318 sequences. (Running on oeis4.)