Patterns in Permutations
Rust, score ≈ 13
This enumerates permutations σ recursively, sharing as much computation as possible at branches of the search tree, so that only constant work is needed at each leaf.
Times in seconds measured on my Ryzen 7 1800X (8 cores/16 threads):
τ   n = 10    11    12     13      14       15
──────────────────────────────────────────────
1     0.00  0.02  0.25   2.93   38.72   660.86
12    0.00  0.04  0.47   5.89   79.08  1268.18
123   0.00  0.06  0.67   8.47  115.61  1836.36
132   0.01  0.10  1.18  15.50  218.39  3443.56
1234  0.00  0.05  0.59   7.65  104.88  1643.29
1243  0.00  0.06  0.81  10.72  152.60  2417.75
1324  0.01  0.09  1.10  14.52  208.59  3280.18
1342  0.01  0.10  1.21  16.59  242.01  3871.64
1432  0.01  0.09  1.19  16.21  237.93  3808.25
2143  0.00  0.06  0.81  10.72  151.09  2409.76
2413  0.01  0.09  1.20  16.07  232.74  3717.70
──────────────────────────────────────────────
max   0.01  0.10  1.21  16.59  242.01  3871.64

Build and run with:
cargo build --release
target/release/permutations 11 '1 3 4 2'

Or try it online!
(But note, the TIO version lacks parallelism and many other optimizations, so it’s much slower, due to being unable to use external crates.)
All outputs for n = 0…15.
Cargo.toml
[package]
name = &quot;permutations&quot;
version = &quot;0.1.0&quot;
authors = [&quot;Anders Kaseorg &lt;andersk@mit.edu&gt;&quot;]
edition = &quot;2018&quot;

[dependencies]
rayon = &quot;1.5.0&quot;
thread_local = &quot;1.1.3&quot;
typed-arena = &quot;2.0.1&quot;

[profile.release]
lto = &quot;y&quot;
panic = &quot;abort&quot;

src/main.rs
use rayon::prelude::*;
use std::cell::Cell;
use std::env;
use std::iter::Zip;
use std::slice;
use thread_local::ThreadLocal;
use typed_arena::Arena;

enum UpdateIterator&lt;'a&gt; {
    Leave(u16, slice::Iter&lt;'a, (u16, u16)&gt;),
    Take(
        u16,
        u16,
        Zip&lt;slice::Iter&lt;'a, (u16, u16)&gt;, slice::Iter&lt;'a, u16&gt;&gt;,
    ),
}

impl Iterator for UpdateIterator&lt;'_&gt; {
    type Item = (u16, u16);

    fn next(&amp;mut self) -&gt; Option&lt;(u16, u16)&gt; {
        match *self {
            UpdateIterator::Leave(i, ref mut bounds) =&gt; bounds
                .next()
                .map(|&amp;(low, high)| (low + (low &gt; i) as u16, high + (high &gt;= i) as u16)),
            UpdateIterator::Take(i, tau0, ref mut zip) =&gt; {
                zip.next().map(|(&amp;(low, high), &amp;tau1)| {
                    if tau0 &lt; tau1 {
                        (low.max(i) + 1, high + (high &gt;= i) as u16)
                    } else {
                        (low + (low &gt; i) as u16, high.min(i))
                    }
                })
            }
        }
    }

    fn size_hint(&amp;self) -&gt; (usize, Option&lt;usize&gt;) {
        match self {
            UpdateIterator::Leave(_, bounds) =&gt; bounds.size_hint(),
            UpdateIterator::Take(_, _, zip) =&gt; zip.size_hint(),
        }
    }
}

fn update(
    tau: &amp;[u16],
    remaining: usize,
    states: &amp;[(&amp;[(u16, u16)], isize)],
    i: u16,
    mut callback: impl FnMut(UpdateIterator, isize),
) {
    for &amp;(bounds, count) in states {
        if bounds.len() &lt; remaining {
            callback(UpdateIterator::Leave(i, bounds.iter()), count);
        }

        if let Some((&amp;(low0, high0), bounds1)) = bounds.split_first() {
            if low0 &lt;= i &amp;&amp; i &lt;= high0 {
                callback(
                    UpdateIterator::Take(
                        i,
                        tau[tau.len() - bounds.len()],
                        bounds1.iter().zip(&amp;tau[tau.len() - bounds.len() + 1..]),
                    ),
                    count,
                );
            }
        }
    }
}

fn search_step(
    tau: &amp;[u16],
    remaining: usize,
    states: &amp;[(&amp;[(u16, u16)], isize)],
    arena_len: usize,
    i: u16,
    search: impl FnOnce(&amp;[(&amp;[(u16, u16)], isize)], usize),
) {
    let arena = Arena::with_capacity(2 * arena_len + 1 - states.len());
    let mut new_states = Vec::with_capacity(states.len() * 2);
    update(tau, remaining, states, i, |bounds, count| {
        new_states.push((&amp;*arena.alloc_extend(bounds), count))
    });
    new_states.sort_by_key(|&amp;(bounds, _)| bounds);
    new_states.dedup_by(|(bounds0, count0), (bounds1, count1)| {
        bounds0 == bounds1 &amp;&amp; {
            *count1 += *count0;
            true
        }
    });
    search(&amp;new_states, arena.len());
}

fn search(
    n: usize,
    tau: &amp;[u16],
    k: usize,
    states: &amp;[(&amp;[(u16, u16)], isize)],
    arena_len: usize,
    output: &amp;[Cell&lt;u64&gt;],
) {
    if n - k == 1 {
        let mut deltas = vec![0; n + 1];
        let mut total = 0;
        for &amp;(bounds, count) in states {
            match bounds {
                [] =&gt; total += count,
                &amp;[(low, high)] =&gt; {
                    deltas[low as usize] += count;
                    deltas[high as usize + 1] -= count;
                }
                _ =&gt; {}
            }
        }
        for delta in &amp;deltas[..n] {
            total += delta;
            output[total as usize].set(output[total as usize].get() + 1);
        }
    } else if n - k == 2 {
        for i in 0..=k as u16 {
            let mut deltas = vec![0; n + 1];
            let mut total = 0;
            update(tau, n - k, states, i, |mut bounds, count| {
                if let Some((low, high)) = bounds.next() {
                    deltas[low as usize] += count;
                    deltas[high as usize + 1] -= count;
                    debug_assert!(bounds.next().is_none());
                } else {
                    total += count;
                }
            });
            for delta in &amp;deltas[..n] {
                total += delta;
                output[total as usize].set(output[total as usize].get() + 1);
            }
        }
    } else {
        for i in 0..=k as u16 {
            search_step(tau, n - k, states, arena_len, i, |states, arena_len| {
                search(n, tau, k + 1, states, arena_len, output)
            })
        }
    }
}

fn par_search(
    n: usize,
    tau: &amp;[u16],
    k: usize,
    states: &amp;[(&amp;[(u16, u16)], isize)],
    arena_len: usize,
    comb: usize,
    outputs: &amp;ThreadLocal&lt;Vec&lt;Cell&lt;u64&gt;&gt;&gt;,
) {
    if n - k &lt;= 4 {
        search(
            n,
            tau,
            k,
            states,
            arena_len,
            outputs.get_or(|| vec![Cell::new(0); comb + 1]),
        );
    } else {
        (0..=k as u16).into_par_iter().for_each(|i| {
            search_step(tau, n - k, states, arena_len, i, |states, arena_len| {
                par_search(n, tau, k + 1, states, arena_len, comb, outputs)
            })
        });
    }
}

fn counts(n: usize, tau: &amp;[u16]) -&gt; Vec&lt;u64&gt; {
    if n &gt; tau.len() {
        let mut comb = 1;
        for i in 0..tau.len() {
            comb = comb * (n - i) / (i + 1);
        }
        let outputs = ThreadLocal::new();
        par_search(
            n,
            &amp;tau,
            0,
            &amp;[(&amp;vec![(0, 0); tau.len()], 1)],
            tau.len(),
            comb,
            &amp;outputs,
        );
        let mut output = vec![0; comb + 1];
        for thread_output in outputs {
            for (x, y) in output.iter_mut().zip(thread_output) {
                *x += y.get();
            }
        }
        output.truncate(
            output
                .iter()
                .rposition(|&amp;count| count != 0)
                .map_or(0, |i| i + 1),
        );
        output
    } else if n == tau.len() {
        vec![(1..=n as u64).product::&lt;u64&gt;() - 1, 1]
    } else {
        vec![(1..=n as u64).product()]
    }
}

fn main() {
    let args: Vec&lt;String&gt; = env::args().collect();
    if let [_, n, tau] = &amp;*args {
        let n: usize = n.parse().unwrap();
        let tau: Vec&lt;u16&gt; = tau.split_whitespace().map(|n| n.parse().unwrap()).collect();
        for count in counts(n, &amp;tau) {
            println!(&quot;{}&quot;, count);
        }
    } else {
        panic!(&quot;usage: permutations n 'τ₁ τ₂ … τₘ'&quot;)
    }
}