[Question]
  [
## Background
Binary Sudoku, also known as [Takuzu](https://en.wikipedia.org/wiki/Takuzu), Binario, and Tic-Tac-Logic, is a puzzle where the objective is to fill a rectangular grid with two symbols (0s and 1s for this challenge) under the following constraints:
1. **Each row/column cannot have a substring of `000` or `111`, i.e. one symbol cannot appear three times in a row, horizontally or vertically.**
	* A row/column of `1 0 0 0 1 1` violates this rule since it contains three copies of `0` in a row.
2. **Each row/column should contain exactly as many 0s as 1s, i.e. the counts of two symbols must be the same.**
	* A row/column of `1 0 1 1 0 1` violates this rule since it has four 1s but only two 0s.
	* Some examples of rows that meet the first two requirements include:
	
	
	
	```
	[1 0 0 1]
	[1 1 0 0]
	[1 1 0 1 0 0]
	[1 1 0 0 1 0 0 1]
	
	```
3. (Not relevant to this challenge) The entire grid cannot have two identical rows or columns.
Note that the constraint 2 enforces the grid size to be even in both dimensions.
Here are some examples of completed Binary Sudoku:
```
(4x4, using 0s and 1s)
1 1 0 0
0 1 1 0
1 0 0 1
0 0 1 1
(6x8, using Os and Xs)
O O X O X O X X
X X O X O X O O
X O X O X X O O
O O X X O O X X
X X O X O O X O
O X O O X X O X
```
## Challenge
Given a positive integer `n`, calculate the number of distinct valid Binary Sudoku rows of length `2n`; that is, the number of permutations of `n` 0s and `n` 1s which do not have `000` and `111` as a substring.
The sequence is [A177790](http://oeis.org/A177790), leading 1 removed and 1-based.
## Test cases
Here are the first 20 terms of this sequence (1-based):
```
2, 6, 14, 34, 84,
208, 518, 1296, 3254, 8196,
20700, 52404, 132942, 337878, 860142,
2192902, 5598144, 14308378, 36610970, 93770358
```
## Scoring and winning criterion
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply. The shortest submission in bytes wins.
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~13 12~~ 9 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ŻcṚ$+Ḋ$²S
```
**[Try it online!](https://tio.run/##y0rNyan8///o7uSHO2epaD/c0aVyaFPw////TQE "Jelly – Try It Online")** Or see the [test-suite](https://tio.run/##ASQA2/9qZWxsef//xbtj4bmaJCvhuIokwrJT/1LFvMOH4oKsR///MjA "Jelly – Try It Online").
### How?
This code is calculating
$$\sum\_{k=\lceil\frac{n}{2}\rceil}^{n}\big(\binom{k}{n-k}+\binom{k+1}{n-(k+1)}\big)^2$$
(where \$k\$ starts at \$0\$ rather than \$\lceil\frac{n}{2}\rceil\$ ...the additional terms are \$0\$ but allows a reversal trick)
```
ŻcṚ$+Ḋ$²S - Link: integer, n       e.g. 7
Ż         - zero range                  [0,  1,  2,  3,  4,  5,  6,  7]
   $      - last two links as a monad:
  Ṛ       -   reverse                   [7,  6,  5,  4,  3,  2,  1,  0]
 c        -   n-choose-k                [0,  0,  0,  0,  4, 10,  6,  1]
      $   - last two links as a monad:
     Ḋ    -   dequeue                   [0,  0,  0,  4, 10,  6,  1]
    +     -   add                       [0,  0,  0,  4, 14, 16,  7,  1]
       ²  - square                      [0,  0,  0, 16,196,256, 49,  1]
        S - sum                         518
```
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 77 bytes
```
n->polcoeff([x,0,1,0]*[0,x,1,0;0,0,1,0;x,0,0,1;x,0,0,0]^(2*n-1)*[1,1,1,1]~,n)
```
[Try it online!](https://tio.run/##LYlLCsMwDESvErKSjAxyoCvjXMS4UEJUAkE2pousenXny8Cbx0z51MV@S5PQ1I4lr1OeRSBuxOSIk4lM22me78Wfz2FPc3rDYNQ6NNHRlfQnxSa5ggZHL6ZSF/2Bdn1nxwMCiohtBw "Pari/GP – Try It Online")
This uses a nice method involving automata and is quite efficient. 
Consider the automaton that checks if a string satisfies condition one. Besides the initial state and a sink state, it has four interesting states. They signify that everything is still okay, what the last letter was and whether it was the same as the one before. When we replace the `x` with `1` in the matrix that occurs in the program, it describes the possibilities to get from one of these states to another.
Usually we should not ignore the initial state, but since it will not be entered again, we can handle it by starting with the vector `[1,0,1,0]` that describes all the states that can be reached after one step. Multiplying this vector with the matrix raised to the `(m-1)`th power gives a vector that tells us how many words of length `m` lead to each state. To get their sum, we multiply with the transpose of the all-one vector. There doesn't seem to be a shorter way to get the sum of the entries of a vector.
However, we still have condition two. It could be handled by the automaton, but that would need more states, depend on `n` and be complicated to create. Instead, we change the matrix (and starting vector) to have an `x` for each transition that corresponds to reading a `1`. This way, the computation will not compuite a number, but a polynomial where each term `a*x^k` means that there are `a` words accepted by the automaton (i.e. satisfying condition one) that contain `k` `1`s. For example, for `n=3` (words of length 6) that polynomial is `6*x^4+14*x^3+6*x^2`. So we just have to take the coefficient of `x^n`.
[Answer]
# [Bash](https://www.gnu.org/software/bash/) + GNU utilities, ~~123~~ ~~121~~ 119 bytes
```
dc<<<[sD1q]so[sD0q]szz`seq -f"%0.fdsK$1lK-[dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/]dsCx1lK+d$1r-lCx+d*+" 0 $1`p
```
[Try the test suite online!](https://tio.run/##HY5BCoMwFET3PcUnpBslNnGtbixuPIIItv6IxZBUfxchpWdP027mMQ8G5n6jNS7uAA8PC29VFKX8nADQpQAg/QLGPfsXPa8OhE1CQV03wCLOVVUNdFX7SC5RJoYwkd5BLOwsiwWp58r0YkDaZBOQLJqtCQOWjUMlsKy6bETqvNlMCms2kZhdkmt9GubI1SFM63PMcgYSuJqe8ffP6vgF "Bash – Try It Online")
---
I've added an explanation of this obscure-looking code at the end of the answer!
---
*Shaved off 2 bytes by moving the definitions of macros F and C to the first place they're used, and then another 2 bytes by eliminating two single-quotes that were no longer required after the macros were moved.*
This is another, completely different bash solution. Unlike my other (shorter) solution, this one is very fast -- [TIO can compute the value for 1800](https://tio.run/##DcvLCsMgEIXhV5FgN4rtTFZdiJuUbPIIEkjbaSg45NLZiC9v3ZwPDvyvp3xrpbf3PsoDz1n2JjRLWeRzKrd2F7iuJJNGnlwkSRAKyUacQonUh53QUe9HM5OMmRO32Ti5prm1b8gttKTx53jIloztFCiNy1FrxTvAHw) in just under its 60-second limit. Because it uses `dc`, it can handle arbitrarily large integers.
The program is based on the binomial coefficient formula from OEIS, which is computed using `dc`. Since loops are such a pain to write in `dc`, I use `seq` instead to unroll the loop into a giant `dc` script to compute the specific number requested, and the `dc` script is then executed.
If you're curious (and don't want to wait the 60 seconds at TIO), here's the 1800th term in the sequence:
`105480721405474718567404887164925416724980133926539712143845881075284\
901677297738964136155557073029386229070488343605298871231397783837622\
530014641802254048917232853438125993571007137377212907244683700588015\
444444467026455576839621404814982031106756318549435412359204504183866\
493764320992226326910391777276272125030010740526937030702909019208912\
640538519829602971756125307274565635138616156817423412863412177199151\
055856207069714084657310495058759139542900519171388443547871558507573\
948937524889911140590562675224573515451638678334944353358816689952838\
021105461897807233248789972151274044554176393928054238190520484054350\
689148029614875765339478833688339093323537661478061731620258929292671\
03260220166411748225093782409130224917917686956257637269268564`
---
**How it works:**
Overall, the structure of the program is: `dc<<<...`, so bash calls dc with a script to run.
But the dc script part isn't written out fully; it's actually generated itself by a program (the dc script is customized for the specific argument `n` that was passed in $1 to bash).
The dc script starts with a prologue string that's taken verbatim, then a call to `seq` to generate the bulk of the `dc` code, and then a final command to print the result.
***PROLOGUE***
The prologue is: `[sD1q]so [sD0q]sz z` (spaces added for clarity -- they don't affect the code).
1. `[sD1q]so`
This defines a macro o which replaces the item at the top of the stack with `1`. It's intended to be called from another macro.
In more detail:
```
[    Start a string (to be used as a macro definition).
sD   Pops an item from the stack and stores it in register D.
     (I only do this because dc doesn't provide a way to just pop an item from the stack without doing something with it, and storing it an otherwise unused register is innocuous.)
1    Push `1` onto the stack.
q    Return from this macro and the macro which called it.
]    End the string.
so   Save the macro in register o.
```
2. `[sD0q]sz`
This defines a macro z which replaces the top of the stack with `0`. It works the same way as macro `o` above.
3. `z`
This pushes the current stack depth onto the stack. But the stack is currently empty, so it just pushes `0` onto the stack. This initializes the running total for the binomial coefficient sum that we're going to be computing. (The reason for using `z` instead of `0` for pushing a `0` is that a number is coming next; so if I used a `0` to push the 0 here, I'd need to put an extra space after it to separate it from the number coming up. So using `z` saves a byte.)
***CALL TO seq***
The `seq` command is of the form `seq -f %0.f... 0 $1`, where the ... is dc code. This takes each number k from 0 to n (the bash argument $1), replaces %0.f (in the first argument to seq) with k, and writes each of those strings on a line:
```
0...
1...
2...
.
.
.
n...
```
where the `...` at the end of each line is the dc code in the argument to seq.
So the loop that one would imagine for computing $$\sum\_{k=0}^n \big( \binom{k}{n-k}+\binom{k+1}{n-k-1}\big)^2$$ is actually unrolled into a simple but long computation for the specific \$n\$ that we have.
There are actually two macro definitions embedded in the dc code. (You can often a save a byte in dc by waiting to define a macro until the first time you use it.)
I'm going to describe those macros first, because I think it's clearer that way.
**The first** of the two embedded macros, `[d2>od1-d2<F*]` computes the factorial of the number at the top of the stack. The macro is saved in register F, so it calls itself recursively:
Assumption: The argument x is on the stack when the macro is called.
```
[    Start macro definition
d    Duplicate the item at the top of the stack, so x is there twice.
2>o  Pop that number. If it's < 2, call macro o to pop the extra copy of the argument, and return from F with 1 on the stack.  (This is the right answer for x! when x<2.)
If it's >= 2:
d    Pop the argument.
1-   Subtract 1.
d    Duplicate the top of the stack, so x-1 is there twice.
2<F  If it's > 2, call F recursively to compute (x-1)!.
*    Multiply the top of stack, which is (x-1)!, by the 2nd item on the stack, which is x, yielding x! as desired.
]    End macro definition
```
The above macro will be saved in register F.
**The second** of the two embedded macros computes the binomial coefficient $$\binom{n}{k} = \frac{n!}{k! (n-k)!},$$ where \$k\$ is the number on the top of the stack and \$n\$ is the second number on the stack.
The binomial coefficient macro is:
`[dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/]`, which is saved in register C. (Note that the definition of macro F is actually embedded inside the definition of C.)
Here's how C works (when it's called, `k` is at the top of the stack, and `n` is second):
```
[    start of macro
d    Duplicate k at the top of the stack.
sk   Pop one k and save it in register k.
0>z  Pop the other k, and if it's < 0, call macro z to return 0 from C (which is the right value for the binomial coefficient when k<0).
If k >= 0:
d    Duplicate n (so there are now two n's at the top of the stack).
sn   Pop one n and save it in register n.
d    Duplicate n (so there are now two n's again at the top of the stack).
lk>z If n<k, call macro z to return 0 from C (which is the right value for the binomial coefficient when k>n).
[d2>od1-d2<F*]  This is the definition of macro F, as described earlier, embedded in C.
d    Duplicate the F macro string on the stack.
sF   Pop one copy of the macro F string, and save it in register F.
x    Pop the stack to get a copy of the macro string F and call it.  So now the n at the top of the stack has been replaced by n!
lk   Load k.
lFx  Compute k!.
lnlk- Compute n-k.
lFx   Compute (n-k)!
*     Multiply k! (n-k)!.
/     Compute n!/(k! (n-k)!).
]     End of macro C.
```
So now let's go back to see what the dc code does with each value k from 0 to n. (Below I've written C(n,k) for \$\binom{n}{k}\$ since TeX doesn't seem to work inside code-sample formatting.)
```
%0.f seq replaces this with k, so k is pushed on the stack.
d    Duplicate the top of the stack, so k is now on the stack twice.
sK   Pop one of the k's off the stack and store it in register K.
$1   Push n on the stack.  ($1 has already been replaced by n due to bash's parameter expansion.)
lK   Push k back on the stack (load it from register K).
-    Pop n and k, and push n-k onto the stack.
[dsk0>zdsndlk>z[d2>od1-d2<F*]dsFxlklFxlnlk-lFx*/]   This is the embedded defintion of C, with the definition of F embedded in it.
d     Duplicate the string defining C, so it's there twice.
sC    Save the macro for C in register C. 
x     Call the macro C.  This pops k and n-k, and replaces them with C(k,n-k).
1     Push 1.
lK    Push k.
+     Compute k+1.
d     Duplicate k+1 on the stack.
$1    Push n.
r     Swap n and the k+1 that comes next.  (So the stack now has k+1 at the top, then n, then k+1 again.)
-     Replace k+1 and n at the top of the stack with n-k-1.
lCx   Replace n-k-1 and k+1 with C(k+1,n-k-1).
+     Add the two binomial coefficients.
d*    Square the sum of the two binomial coefficients.
+     Add it onto the running total.
```
The above is done for each k, so after they're all done, the top of the stack contains the value we want.
***EPILOGUE***
The epilogue is fixed code that's hit last. It just consists of the single dc command
`p`
which prints the result, with a newline after it.
It may be worth mentioning that the macro F is redefined every time C is called (because the definition of F is embedded in C), but that's OK -- it's defined the same way every time.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 46 bytes
*a(n) = Sum\_{k=0..n} (C(k, n-k) + C(k+1, n-k-1))^2* 
```
Sum[Tr@Binomial[{k,k+1},{#,#-1}-k]^2,{k,0,#}]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n277P7g0NzqkyMEpMy8/NzMxJ7o6Wydb27BWp1pZR1nXsFY3OzbOSAcoaKCjXBur9j@gKDOvREHfIV3fISgxLz3Vwcjg/38A "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [Perl 5](https://www.perl.org/) `-p`, ~~50~~ 48 bytes
*@Grimmy saved 2 bytes*
```
$_=grep!/000|111/&&y/1//==y/0//,glob"{0,1}"x2x$_
```
[Try it online!](https://tio.run/##K0gtyjH9/18l3ja9KLVAUd/AwKDG0NBQX02tUt9QX9/WtlLfQF9fJz0nP0mp2kDHsFapwqhCJf7/f0MuIy5jLhMuUy6zf/kFJZn5ecX/dQtyAA "Perl 5 – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), ~~114~~ \$\cdots\$ ~~93~~ 89 bytes
Saved 15 bytes thanks to [Bubbler](https://codegolf.stackexchange.com/users/78410/bubbler)!!!  
Saved 4 bytes thanks to [Jitse](https://codegolf.stackexchange.com/users/87681/jitse)!!!
```
lambda n:sum([*map(bin(i).count,('000','111','1'))]==[0,0,n]for i in range(4**n//8,4**n))
```
[Try it online!](https://tio.run/##RYoxDgIhEAC/sh27ZOOBWphLeMl5BaeiJLIQ5Apfj6GymSlmyre9spx6cNf@9mm7e5D5sydcdPIFtygY6XDLuzRGZYxRrKy1g4podW4xbFjWkCtEiALVy/OBZ61lmi48TNRHlX@1bI80Q6lRGgpDwDH9AA "Python 3 – Try It Online")
Brute force!
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 35 bytes
```
ＮθＩＬΦＥＸ⁴θ⭆◧⍘ι²⊗θΣλ›⁼№ι0№ι1ΣＥ²№ι×³Ｉλ
```
[Try it online!](https://tio.run/##TU7LDoIwELz7FYTTkmCiyI2b@IgJGhL9gQUKNCkU@tDPr1sf0T3NzuzMbN2jqiUK507jZM3FDhVTMEfZolR8NJCjNlCwsTM9HLgwJJ5xglI@CKVxMEdxcDV02r1obArWGtiiZm8WeBwkdLOTthKsoWRvsAOIyKOjYugz97NFoSGXljrJEq5CUn/rOvz6fE3yJ934wDRsiPGf@tTPZM6lbnkX@AQ "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
ＮθＩＬΦＥＸ⁴θ
```
Loop from `0` to `2²ⁿ`.
```
⭆◧⍘ι²⊗θΣλ
```
Generate all binary strings of length `2n`.
```
›⁼№ι0№ι1
```
Check that the number of `0`s and `1`s is the same.
```
ΣＥ²№ι×³Ｉλ
```
Check that the string does not contain 3 repeated digits.
[Answer]
# [Bash](https://www.gnu.org/software/bash/) + GNU utilities, ~~86~~ 75 bytes
```
n=$1;e()(egrep "(21*){$n}"|grep -v 111);seq $[10**(2*n)]|e|tr 12 21|e|wc -l
```
[Try it online!](https://tio.run/##S0oszvj/P89WxdA6VUNTIzW9KLVAQUnDyFBLs1olr1apBiygW6ZgaGioaV2cWqigEm1ooKWlYaSVpxlbk1pTUqRgaKRgZAhklicr6Ob8///fBAA "Bash – Try It Online")
The input is passed as argument, and the output is written to stdout.
It's very slow -- TIO times out at \$n=5\$.
---
**How it works:**
The function e is a filter; it only allows a line through if:
(a) it doesn't have 3 `1`s in a row,
and (b) it has a substring consisting of just `1`s and `2`s, with exactly `n` `2`s.
The seq command counts from \$1\$ to \$10^{2n}\$. These are all numbers of at most \$2n\$ digits (except for the \$10^{2n}\$ at the end).
We'll count numbers consisting of just `1`s and `2`s, not `1`s and `0`s, since otherwise we wouldn't get numbers starting with `0`s.
The filter e is applied, and then it's applied to the same string with the `1`s and `2`s switched around. So a number is allowed through if:
(a) it doesn't have 3 `1`s in a row;
(b) it doesn't have 3 `2`s in a row;
(c) it has a substring consisting of just `1`s and `2`s, with exactly `n` `2`s; 
and (d) it has a substring consisting of just `1`s and `2`s, with exactly `n` `1`s.
Since the numbers being produced are decimal numbers with at most \$2n\$ digits, it follows that we're only letting through numbers with exactly \$n\$ `1`s and exactly \$n\$ `2`s. (The \$10^{2n}\$ at the end is an exception with \$2n+1\$ digits, but it won't have passed through the filter anyway.)
Finally, `wc -l` counts the lines remaining.
---
The earlier 86-byte version used dc instead of seq, so it can handle arbitrarily large numbers, not limited by bash's maximum integer size. But that's more or less moot because it's too slow anyway.
Here's the old version:
`n=$1;e()(egrep "(21*){$n}"|grep -v 111);dc<<<"O$1d+^[d1-pd0<f]dsfx"|e|tr 12 21|e|wc -l`
You can see more about that one (including a faster version that's 2 bytes longer, counting in base 3 instead of base 10) in the edit history.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~13~~ 8 bytes
*Port of [Jonathan Allan's Jelly answer](https://codegolf.stackexchange.com/a/201104/6484)*
```
ÝÂcDÀ+nO
```
[Try it online!](https://tio.run/##yy9OTMpM/f//8NzDTckuhxu08/z//zcHAA "05AB1E – Try It Online")
Old 13-byter:
```
xLÉœêʒü3€ËË}g
```
[Try it online!](https://tio.run/##ASEA3v9vc2FiaWX//3hMw4nFk8OqypLDvDPigqzDi8OLfWf//zQ "05AB1E – Try It Online")
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 18 bytes
```
+.×⍨1,2+/⊢(-!⊢)⍳,⊢
```
[Try it online!](https://tio.run/##DY67SoNREIRfZeyUPzF7OZc9tY2pBOMLBCQ2gdhaC4EETtBCrLVKIVjoE8Q32Rf53WZmd/mWmeXjenr/tFxvHkY/vM1vfPtC43D59@79yBMZZr7/PJ@ehV54/5mEj6tgvB98/@z9y/vv6Vt9@xrfi9ur0Lvr@WIUFHCCJliCkCGzgaUVqOQ4ckxClQhZEiWwSksC1WrVYIU4NuEmjQQ5N@MUUFKyIKClMLVKaForaTb47gORHc1WpyN4iK5C/w "APL (Dyalog Unicode) – Try It Online")
Bubbler's port of the Jelly solution(-14 bytes!).
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~35~~ 32 bytes
```
{+/(×⍨((⍵-1+⊢)!1+⊢)+⊢!⍨⍵-⊢)⍳1+⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6u19TUOT3/Uu0JD41HvVl1D7UddizQVIRSIUARKgSRA/Ee9m4ESvVtr/6cB9T7q7XvU1fyod82j3i2H1hs/apsINDU4yBlIhnh4Bv9PUzAFAA "APL (Dyalog Unicode) – Try It Online") or [Verify all test cases](https://tio.run/##SyzI0U2pTMzJT///qG@qp/@jtgkG/6u19TUOT3/Uu0JD41HvVl1D7UddizQVIRSIUARKgSRA/Ee9m4ESvVtr/6cB9T7q7XvU1fyod82j3i2H1hs/apsINDU4yBlIhnh4Bv9/1Lsq7RBQ72YjAwA "APL (Dyalog Unicode) – Try It Online")
Uses the formula from the Bash answer(which is very, very cool, go upvote it!).
Requires `⎕IO←0` for 0-indexing.
-3 bytes from ovs (Converted inner dfn to train, removing assignment to n).
## Explanation
```
{+/{×⍨((n-⍵+1)!⍵+1)+(n-⍵)!⍵}⍳1+n←⍵}
                               n←⍵  store input in n
                            ⍳1+     range 0..n
   {                       }        apply the following to it's elements k:
                    (n-⍵)!⍵         k C (n-k)
                   +                plus 
      ((n-⍵+1)!⍵+1)                 (k+1) C (n-(k+1))
    ×⍨                              squared
 +/                                 sum the resulting array
```
# [APL (Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 42 bytes
```
{+/(≢=2×+/)¨{⍵/⍨{⍱/0 3∊⍵}¨3+/¨⍵}↓⍉⊤⍳2*2×⍵}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT9dNrShJzUtJTfn/qG@qp/@jtgkG/6u19TUedS6yNTo8XVtf89CK6ke9W/Uf9YLojfoGCsaPOrqAIrWHVhhr6x9aAWI@apv8qLfzUdeSR72bjbSA@kCC/9OApj3q7XvU1fyod82j3i2H1hs/apsItCc4yBlIhnh4Bv9PUzAFAA "APL (Dyalog Extended) – Try It Online")
Brute force method, which is much slower and longer.
[Answer]
# JavaScript (ES6), ~~80 76~~ 70 bytes
A port of the Maple solution presented on OEIS.
```
f=(i,j=i,k=2)=>i*j<0?0:i|j?(k<4&&f(i-1,j,k<3?3:4))+(k&&f(i,j-1,k>1)):1
```
[Try it online!](https://tio.run/##HYpBDoMgEADvvmIPxuwWbKTai4J@RWOlAQw02vRifTslPc1kMnb6TPu8mde79OGxxKgVGm6V4U7dSPXmYmU1VK352gGdbIpCoykFt9zJeqjbhoih@1duU3e9IGpF1GFDDwpEBx5k4j0JYwRHBjAHv4d1ua7hieOE@eFPSm9@aPR0jtRlZ/wB "JavaScript (Node.js) – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-x`](https://codegolf.meta.stackexchange.com/a/14339/), 15 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
Far too long and *extremely* inefficient! :\
```
çA á â Ë«ø56¤ò3
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LXg&code=50Eg4SDiIMur%2bDU2pPIz&input=NA)
[Answer]
# [Ruby](https://www.ruby-lang.org/), 75 bytes
```
->n{([0,1]*n).permutation.uniq.count{|r|r.chunk{|n|n}.all?{|k,v|v.size<3}}}
```
[Try it online!](https://tio.run/##Tcm9DoIwFEDhnae4CQs1eCOimz8v4WYcalNCU7hgaTHa9tmrE2H7To5xz09q4AxpeyFf3Hdl9dgQw1Ga3llu1UDoSL1QDI6sDyYYFK0j7QMFisi77uqDLucw46S@8lTHGNMIDYr/KiqWLd6vXK98YFkOSx0Z5HDjWk7A4d2qTqYf "Ruby – Try It Online")
## Explanation
This is a naive solution that generates the permutations and counts the valid ones.
```
->n{([0,1]*n).permutation.uniq.count{|r|r.chunk{|n|n}.all?{|k,v|v.size<3}}}
# This gets all the unique permutations of `0`s and `1`s of size `2n`.
    ([0,1]*n).permutation.uniq
# This counts all instances where the inner block evaluates to true
                               count{                                     }
# This chunks together consecutive `0`s and `1`s.
                                     |r|r.chunk{|n|n}                      
# This checks that all consecutive `0`s and `1`s are shorter than 3
                                                      all?{|k,v|v.size<3}
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 79 bytes
```
f(i,j,k){i=i*j<0?0:i|j?(k<4)*f(i-1,j,3+k/3)+!!k*f(i,j-1,k>1):1;}a(x){f(x,x,2);}
```
A port of [Arnauld's solution](https://codegolf.stackexchange.com/a/201100), and, by extension, the Maple solution on the OEIS page.
I spent way too much time working on an alternate solution. Here's what I came up with that didn't work:
* The number of numbers that don't meet the requirements of rule 1 is `2(x-1)`, or `4(x-1)` in this challenge's input scheme.
* The number of numbers that do meet the requirements of rule 2 is `(n)!/(floor(n/2)!)^2`, or `(2n)!/(n!)^2`.
* These cannot be combined because some numbers meet both the requirements, some meet neither, and the rest meet only one.
*-6 bytes thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!*
[Try it online!](https://tio.run/##HY3BjoIwFEX3/YqnZpK@UgYZZ2VBf8RNU6w@qsUgmhqGX59avKube05yTX4yJkbLSbbS4Ug1ibZa79db@mv33FW/KBLMy4Q3mSs2mC0WTnz8NLpdidtSTZoHHC0PMsgfVFNckTeXR3OE6j401H2fd4yRH@CqyfNnRw2ykUGK7Xo@gwA1lAoKkVoF5C15Gl4gCgUhy/Djzrn1ybZ8@dUc/FLC/IuKTfHf2Is@3WN@1b05114P9Dy@AQ "C (gcc) – Try It Online")
]