[Question]
  [
*This is a cross-post of a problem I posted to anarchy golf: <http://golf.shinh.org/p.rb?tails>*
Given two integers \$ n \$ and \$ k \$ \$ (0 \le k \le n) \$, count the number of combinations of \$ n \$ coin tosses with at least \$ k \$ tails in a row.
For example, if \$ n = 3 \$ and \$ k = 2 \$, the answer is \$ 3 \$:
```
HHH ‚ùå
HHT ‚ùå
HTH ‚ùå
HTT ‚úîÔ∏è
THH ‚ùå
THT ‚ùå
TTH ‚úîÔ∏è
TTT ‚úîÔ∏è
```
**For convenience sake, you do not need to handle the case where \$ n = k = 0 \$**.
## Rules
* The input must take in two integers \$ n \$ and \$ k \$, and output the answer as a single integer
* Inaccuracies due to integer overflow are acceptable, but floating point errors are prohibited
* As usual for [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), the shortest code in bytes wins
## Test Cases
```
 n,  k  ->  ans
---------------
 1,  0  ->  2
 1,  1  ->  1
 2,  0  ->  4
 2,  1  ->  3
 2,  2  ->  1
 3,  1  ->  7
 3,  2  ->  3
 3,  3  ->  1
 5,  2  ->  19
 6,  4  ->  8
 9,  2  ->  423
12,  0  ->  4096
13,  5  ->  1262
14,  8  ->  256
16,  7  ->  2811
```
More terms are listed under [OEIS A109435](https://oeis.org/A109435).
  
[Answer]
# [Python](https://www.python.org), 50 bytes
```
lambda n,k:sum(k*"1"in bin(i)for i in range(2**n))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3jXISc5NSEhXydLKtiktzNbK1lAyVMvMUkjLzNDI10_KLFDIVgNyixLz0VA0jLa08TU2oTnuQZB5C0tBA04pLoaAoM69EQ0sjTak6TSNPRyFb08q4VkkBpDYbodZUE2bMggUQGgA)
Brute-force solution seems to be the shortest.
---
## [Python](https://www.python.org), 67 bytes
```
lambda n,k:2**n-(g:=lambda a:a*k>0and(a<3or g(a-1)*2-g(a+~k)))(n+2)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vweI025ilpSVpuhY3nXMSc5NSEhXydLKtjLS08nQ10q1soWKJVola2XYGiXkpGok2xvlFCukaibqGmlpGukCGdl22pqamRp62kSbUKPs0oJI8hcw8haLEvPRUDUMDTSsuhYKizLwSDS2NNKXqNI08HYVsTSvjWiUFkNpshFpToFkQYxYsgNAA)
-11 bytes thanks to Neil.
More mathematical answer.
$$
f(n, k) = 2^n - k \operatorname{-bonacci}(n+k)
\\
k \operatorname{-bonacci}(n) =
\begin{cases}
0 & n < k-1 \\
1 & n = k-1 \\
\sum^k\_{i=1} k \operatorname{-bonacci}(n-i) & n > k-1
\end{cases}
$$
[Answer]
# x86-64 machine code, 28 bytes
```
31 C0 99 52 89 F1 FF C9 78 07 D1 EA 72 F8 75 F4 41 FF C0 5A FF C2 0F A3 FA 73 E8 C3
```
[Try it online!](https://tio.run/##pVLBctMwED1rv2IbJjMStjtJyHBwai6cuXBihnBwJDnekMjBcsChza/j7iYtDTPcqsNKu9J7@54km62tHYYy7lB/HmmoctU3LfqyTyWAsu4HlLnaH2KNrethlatd8xO9lQORwObKeSs5qE1EByrWjHe8PeWKRcsx/MYVqNvVsfM46edTcLmiYC8d9s3@zHypyGLVXQi8IwFbLEG1vgMzMgug0GGlJYYUZfrORXjD4O3BebyLnaPmtv5wPrgrKWgD99yl5bzSI8QHYVEVuzyzbLDAyYKnmwKnM14kiQG8Gn@R4zmNUtwI@rm2DFmWZK8Y/2qhixZ61kKiRbH6q4bjGT2wDBLgf1zcFUhPJtQL7Ek731u6MYI8gbp2sQyfSltT8Ggb5/OzKqHthTbFI6euwfsXusnsC/MdC60PIdI6eIe2Ltu3pjJf@yT5ZhYn/FXT1qM@iptJ//Hd9cWhHhPKf4hmGZipl01@40Mb2AechuGPrbblOg7Z7v2cA//QgqF@@wg "C (gcc) ‚Äì Try It Online")
Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes n in EDI and k in ESI and returns the answer in EAX.
In assembly:
```
f:  xor eax, eax
    cdq
a:  push rdx
b:  mov ecx, esi
c:  dec ecx
    js d
    shr edx, 1
    jc c
    jnz b
    .byte 0x41
d:  inc eax
    pop rdx
    inc edx
    bt edx, edi
    jnc a
    ret
```
[Answer]
# [Vyxal](https://github.com/Vyxal/Vyxal) `s`, ~~13~~ ~~9~~ 8 bytes
```
E∆õbƒ†·π†‚Å∞‚â•a
```
[Try it Online!](https://vyxal.pythonanywhere.com/#WyJzIiwiIiwiRcabYsSg4bmg4oGw4omlYSIsIiIsIjFcbjAiXQ==)
A very neat little answer I'm very happy with.
## Explained
```
E∆õbƒ†·π†‚Å∞‚â•a
E∆õ       # to each item in the range [1, 2 ** N)
  bƒ†·π†    #   get the sums of consecutive digits of the binary representation of that number
     ‚Å∞‚â•a #   are any of those greater than K? This is essentially getting all consecutive runs of flips and getting there length. Works because there's only 1s and 0s
# the s flag sums that list. 
```
[Answer]
# [Python](https://www.python.org), 55 bytes
```
f=lambda n,k:n>=k and 2*f(n-1,k)-(-1<<n>>-~k)-f(n+~k,k)
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72soLIkIz9vwYKlpSVpuhY3zdNscxJzk1ISFfJ0sq3y7GyzFRLzUhSMtNI08nQNdbI1dTV0DW1s8uzsdOuAHKCodl02UBiq3SEtv0ghTyEzT6EoMS89VcPIQNOKS6GgKDOvRENLI02pGqhBRyFb08qsVkkBpDYbRa0m1ByYcwA)
Slightly longer than [@pxeger's Python answer](https://codegolf.stackexchange.com/a/248500/107561) but more efficient.
### How?
Uses the recurrence
\$f(n,k)=2f(n-1,k)+2^{n-k-1}-f(n-k-1,k)\qquad(n>k)\$
which is obtained by counting words that have k consecutive 1's somewhere in the first n-1 places, words that end in a 0 followed by k 1's and the overlap of these two groups.
[Answer]
# JavaScript (ES7), 59 bytes
Expects `(n)(k)`.
Fully bitwise because binary string manipulation in JS is too verbose.
```
(n,i=1<<n)=>g=k=>i--&&(h=m=>i&m^m?h(m*2):m<=i)(2**k-1)+g(k)
```
[Try it online!](https://tio.run/##dc9NDoIwEAXgvafoisygCB1@FEPxJiYEBSq0GDFeH1lAIBV2Tb6896bP7Jt1@Vu@Po5u74@@ED3ogxQ8STSKtBS1SKXjWBZUQg1PS93UtQJlE15UIiQC2XbtcNyXUGOft7prm8exaUsogHEED5G5LmO0@zc@GjeN5lywYlPOXzHa6vTn3GnFaKtzMH@rM1zsxSZGCMGIZ9PiORiQOcmX3/fiyOThonBapYj6Hw "JavaScript (Node.js) ‚Äì Try It Online")
---
# JavaScript (ES7), 38 bytes
*Saved 2 bytes thanks to @Neil*
Expects `(k)(n)`. Returns [*true* for *1*](https://codegolf.meta.stackexchange.com/a/9067/58563).
Uses [loopy walt's recursion formula](https://codegolf.stackexchange.com/a/248518/58563).
```
k=>g=n=>n>k?2*g(--n)-g(n-=k)+2**n:n==k
```
[Try it online!](https://tio.run/##ddFLDoMgEIDhvadgCRqqAz6bYM9irJIWA01ten3KQoxBuv7yk5nhOXyHdXw/Xh@qzX2ys7BK9FJo0ete3VgqMaWaUIk1FYpkLE31VQuh7Gj0apbpshiJsxkXBCMgBOU5QiwJEA4ISaRkG5ax0iMPkR0QYiXfsImV/N@z/IAQKyuPXail03rTNpZ2flHGI3eA/Q5FV4deOd/HYvXpyK3z0v9Adcobx3401gLYHw "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), ~~21~~ 19 bytes
-2 bytes saved thanks to a suggestion by [coltim](https://codegolf.stackexchange.com/users/98547/coltim) on another answer.
Enumerates all binary length-n sequences and counts the ones with runs of at least k 1s.
```
{+/y<|/1(1+*)\!x#2}
```
[Try it online!](https://ngn.codeberg.page/k#eJw1jjESgzAMBHu/ggwNCQVIso2N+AnQ8oYwJHl77DPu9k6rkY756odz+QzUUf96bo93y19jzLGSjnvzaxhIGSkhl9YC0QqQqyClnYBcBVGpgrvdmNirzRwSxlJbzjrVM2P0OYo67LDHO1YDXnMYep2QAtEfipkyPg==)
[Answer]
# [PARI/GP](https://pari.math.u-bordeaux.fr), 40 bytes
```
k->g(n,r=k)=if(!r,2^n,n,g(n--,r--)+g(n))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=Nc5BCsIwEEDRq0RXGZwBk7S1LtqLlCjZpJRKCKEuvIngpiDimbyNSdNu8uaHBOb19SYM197Pb8uaz32yVP_4SG3PHYZmhGawfBdQXhw6jJdEGIjgEEeA9f3TeH97cMOoZT4MborjPsWeWW46qSGeQgMg6zqBRx0VKBIyl9xKJlQutZVKlLkqLBLnXGL9LxSWiwXWixWetF73m-fsHw)
A port of [@tsh's JavaScript answer](https://codegolf.stackexchange.com/a/248536/9288).
---
# [PARI/GP](https://pari.math.u-bordeaux.fr), 42 bytes
```
k->n->(y=1-x)/(y-=x)/(x+y/x^k)%x^(n+1)\x^n
```
[Attempt This Online!](https://ato.pxeger.com/run?1=Nc5BCoMwEEDRqwShkNQEO4lau9CL2FiysYgSglhIblLoRiilZ-ptaoxu5s1fDMzra9TY3e5mfreo_DymlhW_Y88qzSrsSmCWJNix0mNjl9imJwfbYB0DudpGbxdPZczgsEKsQmbs9LSskY8ItVjVXJJlgiSEoroGepKLQMHDQ_G9uEeEEnsJTxYqp6nnEgq2exA0W01psZrTs5Qk_DfPwT8)
According to OEIS, the generating function for column \$k\$ is \$\frac{x^k}{(1-\sum\_{i=1}^k x^i)(1-2x)}\$, which could be simplified to \$\frac{(1-x)}{(1-2x)(x+(1-2x)/x^k)}\$.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
1x·∫á‚±ÆS…ì2·πó
```
[Try it online!](https://tio.run/##y0rNyan8/9@w4uGu9kcb1wWfnGz0cOf0/4eXO@hrRv7/H22oYxCrAyQNgaQRmG0EZRsBSWMw2xjKNgaSpmC2mY4JkLQEsw0h2gyNdUxBlImOBYgy0zGPBQA "Jelly ‚Äì Try It Online")
\$k\$ on the left, \$n\$ on the right.
```
   ‚±Æ        For each
     …ì2·πó    sequence of n 1s and 2s,
  ·∫á         does it contain as a sublist
1x          k 1s?
    S       Sum.
```
[Answer]
# [Factor](https://factorcode.org/) + `sequences.repeating`, 58 bytes
```
[ "1"swap cycle swap 2^ iota [ >bin subseq? ] with count ]
```
[Try it online!](https://tio.run/##bZFBSwMxEIXv@RXP3l2a7HbbVViP4sWLeCoV0jDVYJtdkyyllP72Na3EzWpDCOGbN2@SmY1UvrH968vT8@MdPska2sLRV0dGkcsstSS9Nu/YSf9xObJWWkd2EEE61yiH1pL3h9Zq43HP2JEhrCPAgSlOwA1ua0AkmA@YRyxG6iLBiTpPsLhiko/U8wSLKyb5ef83mY29q8jL8KyBLyKuRvJCRHv@50fTqoyR/FxkqCDK2BxeBOOkZ7PflFB8ngQWnLMT65eY8InbyxbqoLaEy1W8QTdeYol6rQ1ctw4je8AKex1GqZouzGnVb37GV@9CRtZ/Aw "Factor ‚Äì Try It Online")
---
Longer but much cooler:
# [Factor](https://factorcode.org/), 67 bytes
```
[| n k | n 2^ ""n [ dup k short tail* sum suffix ] times last - ]
```
[Try it online!](https://tio.run/##bZHBS8MwFMbZNX/F547CZEm7blXYVbx4EU9jQqgpK0vTmryCMve31xSJTd1CksPvfe97yXulLKix/evL0/PjPXRTSO1QSzrgqKxRGk59dMoUykE61xQOrVVEX62tDOGBsRODXyeAA0ucgRsstoCIMB8xD1hM1GmEI3USYXHFJJmo1xEWV0ySYV@arKbeeeCZf9bINwHnE3kqgj3/96NlnoVIMhQZK4gsNIen3jjq2eovxRdfR4EN5@zM@t03DI4YbvGG@Ww2N9jhvWs9dIfGEkhW@hauq/0py@oTe1BV@@Fp6QgL7Pvyd47bWra4638A "Factor ‚Äì Try It Online")
\$2^n\$ minus the \$(n+k-1)\$th k-bonacci number.
Example:
\$n=6, k=4\$
The tetranacci sequence begins:
\$0, 1, 1, 2, 4, 8, 15, 29, \color{red}{56}\$
\$2^6-56=8\$
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~89~~ 88 bytes
```
m;r;a;b;c;f(n,k){for(c=b=1<<n;b--;c-=m<k)for(a=b,m=r=0;a;m=r>m?r:m)r+=a&1?:-r,a/=2;m=c;}
```
[Try it online!](https://tio.run/##bZJvb4IwEMbf71NcTFxAS6SIf0v1xbJPMc0CtTjDqKaQjIzw1ceOSo0uI@W4Pk/vl@sF4R2FaNucaRazhAmWOopkbp2etSN4wmkUKZZ4HhMez6PM7fSYJyTnmvtYgt9NvtXr3NVjHj/T7drTJJ7wAB3BmvakSsjjk3JcqJ8An04oZVG@q7c9cBRqSgBXYNfUrhmBOYEVuqhSFGiI77xhj5zMcnzD8S2NWhrG0ETfMJcEFncMWV2kKOXBUOprXWjqMFnYhK5MYRjgNvRX866pedfvDNNgSWlPFGdVlCA@Yj3CKEUm9RU82FWvwa5aveA7GxC4308HfTUOF5yuqZM6yArLfNanERSnb3lOHduuO@mF0U1hMB6b066BXcdtr6mQ1o/dnNmzBzuzdvavXaDd/RiQuY@GROM2wb@VF41HUmcwPBAYHsDbdHFY7BTev2MRKMhtSgXnct/Tm6em/RHpZ3wsWu/rFw "C (gcc) ‚Äì Try It Online")
*Saved a byte thanks to [ceilingcat](https://codegolf.stackexchange.com/users/52904/ceilingcat)!!!*
[Answer]
**C** (standard compliant), 78 bytes
`int f(int n,int k,int c){return n?n+c-k?k-c?f(n-1,k,0)+f(n-1,k,c+1):1<<n:1:0;}`
For the readable version:
```
int f(int n,int k,int c){
    if(n==0)return 0; // no more coin flip left => no possible path
    if(n==(k-c))return 1; // last coin flip and 1 tail is lacking
    if(k==c)return 1<<n; // we have done k tails in a row, any path is a good path, and there are 2^n
    return f(n-1,k,0) // possible paths if we get a head
    +f(n-1,k,c+1); // possible paths if we get a tail
}
```
[Answer]
# [APL(Dyalog Unicode)](https://dyalog.com), 28 bytes [SBCS](https://github.com/abrudz/SBCS)
```
{1‚ä•‚çµ‚â§‚åà/‚àò(‚â¢¬®‚äÜ‚ç®)‚ç§1‚çâ(‚ç∫‚ç¥2)‚ä§‚ç≥2*‚ç∫}
```
[Try it on APLgolf!](https://razetime.github.io/APLgolf/?h=AwA&c=ATsAxP97MeKKpeKNteKJpOKMiC/iiJgo4omiwqjiiobijagp4o2kMeKNiSjijbrijbQyKeKKpOKNszIq4o26fQ&f=e9Q39VHbBEMThTQFC65HYI4lkG0EZZuC2AA&i=AwA&r=tryapl&l=apl-dyalog&m=dfn&n=f)
Alternatively (same length): `{1‚ä•(‚à®/(‚çµ‚ç¥1)‚ç∑‚ä¢)‚ç§1‚çâ(‚ç∫‚ç¥2)‚ä§‚ç≥2*‚ç∫}`
[Answer]
# [Retina](https://github.com/m-ender/retina/wiki/The-Language), 39 bytes
```
.+,(.+)
<$1*1>
"$+"+%`$
0$"1
<(.*)>.*\1
```
[Try it online!](https://tio.run/##K0otycxLNPz/X09bR0NPW5PLRsVQy9COS0lFW0lbNUGFy0BFyZDLRkNPS9NOTysGqNBUxwgA "Retina ‚Äì Try It Online") No test suite due to the way the program uses history. Explanation:
```
.+,(.+)
<$1*1>
```
Replace the input with a string of `k` `1`s wrapped in `<>`s.
```
"$+"+
```
Repeat `n` times.
```
%`$
0$"1
```
Duplicate each row, appending `0` and `1` to each copy respectively.
```
<(.*)>.*\1
```
Count the number of rows where the binary portion contains `k` `1`s.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 8 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
TI√£$√óŒ¥√•O
```
[Try it online](https://tio.run/##yy9OTMpM/f8/xPPwYpXD089tObzU//9/Yy4jAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfWVCaNj/kMjDiw0jDk8/t@XwUv//Ov@jow11DGJ1gKQhkDQCs42gbCMgaQxmG0PZxkDSFMw20zEBkpZgtiFEm6GxjimIMtGxAFFmOuaxsQA) or [try it step-by-step](https://tio.run/##RY9BSgQxEEX3c4pP47IHzLgTZBaCMCtl9AKZdI0pujtpUgmCF/EA4g28wey9UludcXATqur/9yBR7IFpnpunIh7m@hbN9uVudV6zJxw5SQaHqWSEJd1pem9TJmEbMKXYFZeX4PR54Qxs6Cot5KKOZ7xfWo1p9b3S6p4msrnWDHrYMZaQEY/IPJLACiQnDq/V/aHAQ0wg6/zfXa0VJpsGpoSBJbdwnlwPVotnQb8WfqcOZn1hVAwph3/1z/fpS@XPZWzx5ln12oklIZGUof7scTvPN6vNLw).
**Explanation:**
```
T        # Push 10
 I       # Push the first input `n`
  √£      # Take the cartesian product of the two, to create all possible n-sized strings
         # containing 0s and 1s
   $     # Push 1 and the second input `k`
    √ó    # Repeat the 1 `k` amount of times as string
     Œ¥   # Map over the list we created earlier, using this "1"-string as argument:
      √•  #  Check if the "1"-string is a substring of the string we're mapping over
       O # Sum to get the amount of truthy values
         # (which is output implicitly as result)
```
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 94 bytes
```
.+,(.+)
1$&$*0;$&$*11;$1$*,1,
+`1;1*,(((1)|,)*)
;$1$#3$*1,
+`^(1+)0
$1$1
r`\2;;(1*,)*(1*),$
1
```
[Try it online!](https://tio.run/##HcoxDsIwFAPQ3dcgoP@Tr6pO2gLKAbgEQmVgYGGoGLl7@OniJ9neXt/359mOclvbkEyGpGA4hTjWnmQNDNFoSCsro4kI9WcaFX06FD/18SFMOsIrYlvvuVbxt0ZPtQCwNdoIGpHdvJtR3LJbMLuLTbi67CcWm8HJLuBi5z8 "Retina 0.8.2 ‚Äì Try It Online") Link includes test cases. Explanation:
```
.+,(.+)
1$&$*0;$&$*11;$1$*,1,
```
Create `2‚Åø` in binary, `n+1` in unary, then a list of `k` `0`s and a `1`.
```
+`1;1*,(((1)|,)*)
;$1$#3$*1,
```
Repeat `n+1` times, drop the first element of the list, and append the sum of the remaining elements. This calculates the `n+1`th k-bonacci number.
```
+`^(1+)0
$1$1
```
Convert the `2‚Åø` from binary into unary.
```
   r`\2;;(1*,)*(1*),$
```
Subtract the `n+1`th k-bonacci number from `2‚Åø`.
```
1
```
Convert to decimal.
Rather than trying to count the number of `n` coin tosses with at least `k` tails in a row, it's easier to consider the number of `n` coin tosses that do not have `k` tails in a row. By considering them grouped by the number of tails that they end with, it's possible to determine a recurrence relation for the number of rows. For example, with `k=3`:
* For `0` coin tosses, `1` ends in `0` tails, `0` end in `1` tails, and `0` end in `2` tails. Total `1` matching row.
* For `1` coin toss, `1` ends in `0` tails, `1` ends in `1` tails, and `0` end in `2` tails. Total `2` matching rows.
* For `2` coin tosses, `2` end in `0` tails, `1` ends in `1` tails, and `1` ends in `2` tails. Total `4` matching rows.
* For `3` coin tosses, `4` end in `0` tails, `2` end in `1` tails, and `1` ends in `2` tails. Total `7` matching rows.
* For `4` coin tosses, `7` end in `0` tails, `4` end in `1` tails, and `2` end in `2` tails. Total `13` matching rows.
* For `n` coin tosses:
	+ The number that end in `0` tails is the total for `n-1` coin tosses, since the value is simply that plus an extra toss of heads.
	+ The number that end in `1` tails is the number that end in `0` tails for `n-1` coin tosses, with each row having an extra toss of tails. However, this is also the total for `n-2` coin tosses.
	+ The number that end in `2` tails is the number that end in `1` tails for `n-1` coin tosses, with each row having an extra toss of tails. Recursively, we see that this is also the total for `n-3` coin tosses.
	+ The total is the sum of these which is also the total of the previous three totals. Thus, this forms a `3`-binacci sequence.
In general, the number of `n` coin tosses that do not have `k` tails in a row is a `k`-binacci sequence.
The number of `n` coin tosses with at least `k` tails in a row plus the number of `n` coin tosses that do not have `k` tails in a row is of course the total possible number of rows, `2‚Åø`.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 39 bytes
```
k=>g=(n,r=k)=>r?n&&g(--n,--r)+g(n):2**n
```
[Try it online!](https://tio.run/##ddBNDoMgEAXgvadgZcBKFfC3CfYsxippNdBg0@tTFtJYoSsW33uTYR79u18HfX@@sFS30UzczLwTHMpU8xnxTl9lHAuIsUwx1ugkoEQXmiTSDEquahnPixJwgjmCgCAEsgwAGv0a2RmJ/B7drAj0nLGD0Z2RQI9tVgd67M9MtjMS6JXO2gMWFqsNm0CxdR@kLLKvdwHyvUDeVn6itInvXrSifqKxicJdvwyMqG3AbUgbQswH "JavaScript (Node.js) ‚Äì Try It Online")
```
k=>    // Number of tails required in a row
g=(
  n,   // Number of coins we will flip
  r=k  // Number of tails still required in a row
)=>
  r?   // Do we still require tails?
   n&& // And we have more coins can flip?
    g(--n,--r)+ // Luckily, tail this time
    g(n):       // Nope, head this time
  2**n // We don't care what we get from remaining coins
```
[Answer]
# [R](https://www.r-project.org), ~~72~~ 68 bytes
*Edit: -4 bytes thanks to @Dominic van Essen.*
```
\(n,k)sum(sapply(1:2^n-1,\(x,r=rle(intToBits(x)>0))any(r$l*r$v>=k)))
```
[Attempt This Online!](https://ato.pxeger.com/run?1=VdDPCoIwHAdwuvoKXQZ52ELB_VFnoIfoETpK4CFBNJOpoc_SxYIeqp4ml03cafDh-_vut90fYnim4attUpu_DzEsrRzV7QXWSVUVPcQ7ciptbMWws0QoijPMyuZ43WdNDTsUOQglZQ-FWWyFeYvCHCE0dX1Wa5BCbAHgoA0AdgQAMf6ClWApZJlhSuYMVUK0KbrM-EqINiWFalOu1hNI8kZiiriUYBlihBrj1vqSTuBJlP3u3EY8IpGNyOcnu7-gvMOfjWM8_dEwTOcX)
[Answer]
# BQN, 20 bytes
```
{+¬¥‚•ä‚à®¬¥¬®‚àß¬¥Àò¬®ùï©‚ä∏‚Üï¬®‚Üïùï®‚•ä2}
```
-1 byte thanks to @Razetime!
[Try it here!](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgeyvCtOKliuKIqMK0wqjiiKfCtMuYwqjwnZWp4oq44oaVwqjihpXwnZWo4qWKMn0KCijigKJTaG93IEbCtCnCqCDin6gKIDHigL8wCiAx4oC/MQogMuKAvzAKIDLigL8xCiAy4oC/MgogM+KAvzEKIDPigL8yCiAz4oC/MwogNeKAvzIKIDbigL80CiA54oC/MgoxMuKAvzAKMTPigL81CjE04oC/OAoxNuKAvzcK4p+pCkA=)
## Explanation
* `‚Üïùï®‚•ä2` generate binary sequences of length *n*
* `ùï©‚ä∏‚Üï¬®` convert each binary sequence to subsequences of length *k*
	+ example: `1010` with *k*=3 becomes `101, 010`
* `‚à®¬¥¬®‚àß¬¥Àò¬®` AND each subsequence, then OR each result
* `+¬¥‚•ä` sum to get total number of 1s
[Answer]
# [Pip](https://github.com/dloscutoff/pip), 14 bytes
```
0<1XbNTB_MS,Ea
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m724ILNgWbSSboFS7IKlpSVpuhbrDGwMI5L8QpzifYN1XBMhglC5ZdGWOgpGMJUA)
Brute force, same concept as pxeger's Python answer.
-5 bytes thanks to DLosc
[Answer]
# [Burlesque](https://github.com/FMNSSun/Burlesque), 36 bytes
```
s11rzjCBg1{{gw:pd{-]g1>=}fl}fl}qL[IE
```
[Try it online!](https://tio.run/##TY7LCsIwEEX38xXzA4XeSdOHYBeKC8G9C3Ej1oJ00QelYOi3x7QNUcjmcO69mcfYN9XQjZU1JmbMw9RWdgD6z/t4qGFMPe3ap4nuNcr9/GqW111u55Odr41lMMfMUckstAA2ALEEk6zgjVpBQkwFk60gIeZAhZj@dQri1I1ulBMXQSWiCH//xkVKcBvaNyUVgivm/mLttJvKPObAFw "Burlesque ‚Äì Try It Online")
```
s1     # Save k
1rz    # [0, 1]
jCB    # Combinations up to n
g1     # Get k
{      # Catch k == 0
 {gw   # Group with length ([1, 1, 0] -> [[2, 1], [1, 0]])
  :pd  # Filter for tails
  {    # Filter
   -]  # Head
   g1  # k
   >=  # Greater than or equal
  }
  fl   # Count matches
 }
 fl    # Count matches
}
qL[    # Length of combinations (when k == 0)
IE     # If else
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 15 bytes
```
ÔºÆŒ∏Ôº©Ôº¨Œ¶Ôº∏¬≤ÔºÆ‚Ññ‚çòŒπ¬≤√óŒ∏1
```
[Try it online!](https://tio.run/##S85ILErOT8z5/98zr6C0xK80Nym1SKNQ05oroCgzr0TDObG4RMMnNS@9JEPDLTOnBCgZkF8OJI10FJB1aGrqKDjnlwJ1OCUWpwaXADWna2TqKBgBxUMyc1OLNQp1FJQMlTTBwPr/fyMF0/@6ZTkA "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Takes `k` as the first input and `n` as the second input. Explanation: Uses brute force, so takes exponential time in `n`.
```
ÔºÆŒ∏              Input `k` as an integer
      ¬≤         Literal integer `2`
     Ôº∏          Raised to power
       ÔºÆ        Input `n` as an integer
    Œ¶           Filtered where
          Œπ     Current value
         ‚çò      Converted to base
           ¬≤    Literal integer `2`
        ‚Ññ       Count i.e. contains
              1 Literal string `1`
            √ó   Repeated by
             Œ∏  Input `k`
   Ôº¨            Take the length
  Ôº©             Cast to string
                Implicitly print
```
27 bytes for an efficient version (approximately linear time):
```
ÔºÆŒ∏ÔºÆŒ∑‚äûœÖ¬πÔº¶‚äïŒ∏‚äûœÖ‚Ü®¬π‚úÇ‚ÆåœÖ‚Å∞Œ∑¬πÔº©‚ÅªÔº∏¬≤Œ∏‚äüœÖ
```
[Try it online!](https://tio.run/##TY29DgIhEIR7n2LLJcFELLSw0@oKDdEnQFwDyR3c8XM@Pi6Fid3M5JsZ60yy0YytDWGu5VanJyVcxGnz7x17XbPDKkGxfscEOASbaKJQ6MUFAT/gbDKhkvAYvSW800qJgyok7CS4PiD6XPKh4MXkglcfakYdP/y0l7AwqePMjQ62pg5wbNt1/AI "Charcoal ‚Äì Try It Online") Link is to verbose version of code. Takes `n` as the first input and `k` as the second input. Explanation:
```
ÔºÆŒ∏ÔºÆŒ∑
```
Input `n` and `k`.
```
‚äûœÖ¬π
```
Start with the zeroth term of the k-bonacci sequence.
```
Ôº¶‚äïŒ∏‚äûœÖ‚Ü®¬π‚úÇ‚ÆåœÖ‚Å∞Œ∑¬π
```
Calculate `n+1` additional terms.
```
Ôº©‚ÅªÔº∏¬≤Œ∏‚äüœÖ
```
Subtract the `n+1`th term from `2‚Åø`.
[Answer]
# [Perl 5](https://www.perl.org/) `-pl`, 35 bytes
```
$b=<>;$_=grep/T{$b}/,glob"{H,T}"x$_
```
[Try it online!](https://tio.run/##K0gtyjH9/18lydbGzlol3ja9KLVAP6RaJalWXyc9Jz9JqdpDJ6RWqUIl/v9/Uy6jf/kFJZn5ecX/dQty/uv6muoZGBoAAA "Perl 5 ‚Äì Try It Online")
[Answer]
# [MATLAB](https://www.gnu.org/software/octave/), 71 bytes
```
function f(n,k),sum(contains(string(dec2bin(0:2^n-1)),repmat('1',1,k)))
```
The binary representation of all numbers from 0-2^n-1 will give each combination of coin flips. From that, I can search the resulting string vector for repeated instances of 1 ( my choice for tails) that are at least k long and sum the logical array for the result.
[Try it online!](https://tio.run/##DcvBCoAgDADQX@nmBgvSYx8TmGmMcIaufn/17q8ljW82K48k5SZTAaELaTwVUhONLAOGdpYTjpzCzgLLGjaZPSL1fNeo4Lwj/y9Esw8 "Octave ‚Äì Try It Online")
[Answer]
# Excel, 49 bytes
```
=COUNT(FIND(REPT(1,B2),BASE(SEQUENCE(2^A2)-1,2)))
```
Input for *n* is in `A2` and *k* is in `B2`.
* `SEQUENCE(2^A2)-1` creates an array from 0 to (2^n)-1.
* `BASE(~,2))` converts that array to binary.
* `REPT(1,B2)` creates a string of *k* 1s.
* `FIND(REPT(~),BASE(~))` tries to find that repeated string in each binary element in the array. This returns an array of integers (if it's found in that element) and errors (if it's not).
* `COUNT(FIND(~))` counts the numbers in that array.
[![Screenshot](https://i.stack.imgur.com/6MW1C.png)](https://i.stack.imgur.com/6MW1C.png)
]