text:
Buildings made from cubes
In this fastest-code challenge, you are provided with a set of \$n\$ identical blocks and need to determine how many unique buildings can be constructed with them. Buildings must satisfy the following rules:

No overhangs - each block must either be on the ground or supported by one or more blocks directly underneath it.
All blocks must be aligned to a unit-sized grid.
All blocks in a building must be connected to at least one other block by at least one face, and the blocks must form a single connected unit.
Buildings are not unique if they can be mapped to another building  by reflection or rotation in the X/Y plane.

e.g. These are the same:

If a building is rotated between horizontal and vertical, that does result in a different building

e.g. These are different:
A building with two storeys each of two rooms:

A building with one storey containing 4 rooms:

The challenge is to determine how many different house designs are possible using a given number of cubes. Input and output are both a single integer (using any standard method).
Clearly for 1 cube, only 1 design is possible. For 2 cubes, 2 designs are possible (lying down and standing up). For 3 cubes, there are 4 possibilities, and for 4 cubes there are 12 (see images below; please note the colours are just for display to make it easier to see the individual cubes, but don’t have any significance beyond that).

The first 8 terms are:
n  | output
1  | 1
2  | 2
3  | 4
4  | 12
5  | 35
6  | 129
7  | 495
8  | 2101

Draft sequence on OEIS.
This is fastest-code. The winning entry is the one that can determine the number of buildings for the highest value of \$n\$. If more than one answer can calculate the result for the same \$n\$ within 10 minutes, the one that is fastest for that value wins. This will be tested on an 8th generation Core i7 with 16 GB RAM running Ubuntu 19.10. There must therefore be a freely available interpreter or compiler for any code posted. Default loopholes and IO rules apply.
Cube images generated using usecubes.
Sandbox link

If the cubes are identical, why are you shading them different colors? I don't get how the rotate horizontal then vertical example is different

@HiddenBabel one is a building with two storeys each of two rooms, the other is a one storey building with four rooms. The colours are just so that the cubes can be seen as separate cubes but are arbitrary.

I've got a good approximation: $\sqrt{x^x}/2$, alternatively $x^{x/2}/2$

Here's an idea if anyone want to develop it. A building is fully specified by its "base" lying on the ground, which is a connected polyomino, and the number of blocks stacked atop each base block. One could generate every possible base, then count how many ways the remaining cubes can be stacked atop that base using a standard partition formula. This is complicated by needing to consider symmetries for cubes stacked atop symmetric bases, though in the limit, most bases won't have any symmetries.

@xnor that sounds sensible. Wikipedia has details of some of the algorithms for enumerating free polyominoes, and your suggestion could be used on top of one of those.

Related: OEIS for counting polyominoes in 2D

JavaScript (Node.js), \$N=10\$ in 4m02s1
1: on an Intel Code i7, 7th Gen
This only includes some trivial optimizations and is therefore quite inefficient. It does at least confirm the results listed in the challenge.
function build(n) {
  let layer = [],
      cube = new Set,
      count = 0,
      x, y;

  for(y = 0; y < n; y++) {
    for(layer[y] = [], x = 0; x < n; x++) {
      layer[y][x] = 0;
    }
  }

  function fill(k, alignTop) {
    let x, y;

    if(k == 0) {
      if(!cube.has(layer + '')) {
        let transf;

        count++;

        cube.add(layer + '');
        cube.add((transf = rotate(n, layer)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');

        cube.add((transf = mirror(layer)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');
        cube.add((transf = rotate(n, transf)) + '');
      }
      return;
    }

    let y0;

    for(y0 = 0; !layer[y0].some(v => v); y0++) {}

    for(y = Math.max(0, y0 - 1); y < n; y++) {
      for(x = 0; x < n; x++) {
        if(
          !layer[y][x] && (
            (y && layer[y - 1][x]) ||
            (y < n - 1 && layer[y + 1][x]) ||
            (x && layer[y][x - 1]) ||
            (x < n - 1 && layer[y][x + 1])
          )
        ) {
          for(let i = 1; i <= (alignTop ? k : k - y0 - 1); i++) {
            layer[y][x] = i;
            fill(k - i, alignTop || !y);
            layer[y][x] = 0;
          }
        }
      }
    }
  }

  for(y = 0; y < n; y++) {
    for(let i = 1; i <= n - y; i++) {
      layer[y][0] = i;
      fill(n - i, !y);
      layer[y][0] = 0;
    }
  }

  return count;
}

function rotate(n, layer) {
  let rot = [],
      x, y;

  for(y = 0; y < n; y++) {
    for(rot[y] = [], x = 0; x < n; x++) {
      rot[y][x] = layer[n - x - 1][y];
    }
  }
  return align(rot);
}

function mirror(layer) {
  return align([...layer].reverse());
}

function align(layer) {
  while(!layer[0].some(v => v)) {
    let s = layer.shift();
    layer = [...layer, s];
  }
  while(!layer[0].some((_, y) => layer[y][0])) {
    layer = layer.map(r => {
      return [...r.slice(1), 0];
    });
  }
  return layer;
}

Try it online! (up to \$N=8\$)
Output
N = 1 --> 1
time: 10.352ms
N = 2 --> 2
time: 0.935ms
N = 3 --> 4
time: 0.877ms
N = 4 --> 12
time: 2.530ms
N = 5 --> 35
time: 9.060ms
N = 6 --> 129
time: 33.333ms
N = 7 --> 495
time: 157.160ms
N = 8 --> 2101
time: 1559.707ms
N = 9 --> 9154
time: 18555.900ms
N = 10 --> 41356
time: 242855.989ms

There's got to be some formula for this.

@S.S.Anne I suspect not, but it would be really interesting if there were.

@S.S.Anne There is no known formula to count free polyominoes. Finding a formula for this 3D version is unlikely to be any easier.

Java 8, \$n=14\$ in 2m31s1
1. Using the AdoptOpenJDK8 distribution, on a 2-core Amber Lake Intel Core i5-based Mac. On an Amazon EC2 m5.xlarge, takes 1m16s.
This takes an inductive approach where, for each rank, it builds off all the buildings of the previous rank by placing cubes in all legal positions (on top of and next to existing cubes), and then removing buildings that are (possibly transformed) duplicates of other buildings. This means that to enumerate the buildings in a rank, all previous ranks must be also be computed. Both compute time and memory are constrained resources — this algorithm relies on keeping millions of Building objects in memory — so I've had a hard time computing beyond \$n=14\$ on my machine even without the 10 minute time limit.
This solution includes a parallel-Stream-based approach (which can be enabled with the parallel JVM system property) which is faster on a multi-core system but also more memory-hungry. This approach was used for the timing results above. The non-parallel approach takes almost twice as long to count \$n=14\$ but is able to do so using only a third of the memory.
Garbage collector settings and tuning can have a significant impact on the runtime and ability of the process to complete. I've also tested with OpenJDK 13, but for whatever reason have seen the best results on 8 so far.
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public final class Building {
    /**
     * A flattened two-dimensional matrix of heights (see toIndex).
     * Buildings are always assumed to be "aligned", such that they exactly
     * fit within their (width, height) bounding box.
     */
    private final byte[] stacks;
    private final int hashCode;
    private final byte width;
    private final byte height;

    public Building() {
        this(new byte[]{1}, 1);
    }

    private Building(byte[] stacks, int width) {
        assert stacks.length % width == 0;
        this.stacks = stacks;
        this.width = (byte) width;
        this.height = (byte) (stacks.length / width);
        this.hashCode = 31 * width + Arrays.hashCode(stacks);
    }

    /**
     * Return the building created by adding a cube at the specified coordinates.
     * The coordinates must be within the current building bounds or else
     * directly adjacent to one of the sides, but this is not validated.
     */
    Building add(int x, int y) {
        if (x < 0) {
            byte[] newStacks = widen(true);
            newStacks[y * (width + 1)]++;
            return new Building(newStacks, width + 1);
        } else if (x < width) {
            byte[] newStacks;
            if (y < 0) {
                newStacks = new byte[stacks.length + width];
                System.arraycopy(stacks, 0, newStacks, width, stacks.length);
                y = 0;
            } else if (y * width < stacks.length) {
                newStacks = Arrays.copyOf(stacks, stacks.length);
            } else {
                newStacks = Arrays.copyOf(stacks, stacks.length + width);
            }
            newStacks[toIndex(x, y)]++;
            return new Building(newStacks, width);
        } else {
            byte[] newStacks = widen(false);
            newStacks[x + y * (width + 1)]++;
            return new Building(newStacks, width + 1);
        }
    }

    byte[] widen(boolean shift) {
        byte[] newStacks = new byte[stacks.length + height];
        int writeIndex = shift ? 1 : 0;
        for (int i = 0; i < stacks.length; i++) {
            newStacks[writeIndex++] = stacks[i];
            if (i % width == width - 1) {
                writeIndex++;
            }
        }
        return newStacks;
    }
    int toIndex(int x, int y) {
        return x + y * width;
    }

    boolean inBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < width && y < height;
    }

    /**
     * Return a stream of all legal buildings that can be created by adding a
     * cube to this building.
     */
    Stream<Building> grow() {
        int wider = width + 2;
        int max = (height + 2) * wider;

        return StreamSupport.stream(new Spliterators.AbstractSpliterator<Building>(max, 0) {
            int i = -1;

            @Override
            public boolean tryAdvance(Consumer<? super Building> action) {
                while ((++i) < max) {
                    // Try adding a cube to every position on the grid,
                    // as well as adjacent to it
                    int x = i % wider - 1;
                    int y = i / wider - 1;
                    int index = toIndex(x, y);
                    if (x < 0) {
                        if (y >= 0 && y < height) {
                            if (stacks[index + 1] > 0) {
                                action.accept(add(x, y));
                                return true;
                            }
                        }
                    } else if (x < width) {
                        if (y < 0) {
                            if (stacks[index + width] > 0) {
                                action.accept(add(x, y));
                                return true;
                            }
                        } else if (y < height) {
                            // it is on the existing grid
                            if (stacks[index] > 0) {
                                action.accept(add(x, y));
                                return true;
                            } else {
                                // is it adjacent to a stack?
                                for (Direction d : Direction.values()) {
                                    int x2 = x + d.x, y2 = y + d.y;
                                    if (inBounds(x2, y2) && stacks[toIndex(x2, y2)] > 0) {
                                        action.accept(add(x, y));
                                        return true;
                                    }
                                }
                            }
                        } else if (stacks[index - width] > 0) {
                            action.accept(add(x, y));
                            return true;
                        }
                    } else if (y >= 0 && y < height) {
                        if (stacks[index - 1] > 0) {
                            action.accept(add(x, y));
                            return true;
                        }
                    }
                }
                return false;
            }
        }, false);
    }

    Building reflect() {
        byte[] newStacks = new byte[stacks.length];
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                newStacks[y + x * height] = stacks[toIndex(x, y)];
            }
        }
        return new Building(newStacks, height);
    }

    Building rotate() {
        byte[] newStacks = new byte[stacks.length];
        for (int x = 0; x < width; x++) {
            for (int y = 0, x2 = height - 1; y < height; y++, x2--) {
                newStacks[x2 + x * height] = stacks[toIndex(x, y)];
            }
        }
        return new Building(newStacks, height);
    }

    Collection<Building> transformations() {
        List<Building> bs = new ArrayList<>(7);
        Building b1 = this, b2 = this.reflect();
        bs.add(b2);
        for (int i = 0; i < 3; i++) {
            bs.add((b1 = b1.rotate()));
            bs.add((b2 = b2.rotate()));
        }
        return bs;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Building building = (Building) o;
        return width == building.width &&
                Arrays.equals(stacks, building.stacks);
    }

    @Override
    public int hashCode() {
        return hashCode;
    }

    private enum Direction {
        N(0, 1), E(1, 0), S(0, -1), W(-1, 0);

        final int x;
        final int y;
        Direction(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int count(int rank) {
        long start = System.nanoTime();
        Collection<Building> buildings = new HashSet<>();

        for (int i = 1; i <= rank; i++) {
            if (i == 1) {
                buildings = Arrays.asList(new Building());
            } else if (Boolean.getBoolean("parallel")) {
                // Using parallel streams is generally faster, but requires
                // more memory since more Buildings are retained before being
                // discarded
                ConcurrentMap<Building, Integer> map =
                        new ConcurrentHashMap<>(buildings.size() * 4);
                AtomicInteger atomicInt = new AtomicInteger();
                buildings.parallelStream()
                        .flatMap(Building::grow)
                        .forEach(b -> {
                            map.putIfAbsent(b, atomicInt.incrementAndGet());
                        });
                // Keep only the buildings that do not have a transformation
                // with a lower index
                buildings = map.entrySet().parallelStream()
                        .filter(entry -> {
                            int index = entry.getValue();
                            for (Building b2 : entry.getKey().transformations()) {
                                Integer index2 = map.get(b2);
                                if (index2 != null && index2 < index) {
                                    return false;
                                }
                            }
                            return true;
                        })
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList());
            } else {
                Set<Building> set = new HashSet<>(buildings.size() * 4);
                // Only add a building to the set if it doesn't already have a
                // transformation in it.
                buildings.stream()
                        .flatMap(Building::grow)
                        .forEach(b -> {
                            if (!set.contains(b)) {
                                for (Building t : b.transformations()) {
                                    if (set.contains(t)) return;
                                }
                                set.add(b);
                            }
                        });
                buildings = set;
            }
            System.err.println(i + " --> " + buildings.size());
            long now = System.nanoTime();
            double ms = ((double) now - start) / 1000000;
            System.err.println("time: " + (ms < 1000 ? ms + " ms" : ms / 1000 + " s"));
        }
        return buildings.size();
    }

    public static void main(String[] args) {
        System.out.println(Building.count(Integer.parseInt(args[0])));
    }
}

Try it online! (non-parallel, up to n=12)
Invocation
javac Building.java
java -XX:+UseParallelGC -Xms14g -Xmx14g -Dparallel=true Building 14

ParallelGC is the default on Java 8, but is included in case you are using a later version JDK where G1GC is the default.
Output
1 --> 1
time: 0.410181 ms
2 --> 2
time: 97.807367 ms
3 --> 4
time: 99.648279 ms
4 --> 12
time: 101.00362 ms
5 --> 35
time: 102.4856 ms
6 --> 129
time: 105.723149 ms
7 --> 495
time: 113.747058 ms
8 --> 2101
time: 130.012756 ms
9 --> 9154
time: 193.924776 ms
10 --> 41356
time: 436.551396 ms
11 --> 189466
time: 991.984875 ms
12 --> 880156
time: 3.899371721 s
13 --> 4120515
time: 18.794214388 s
14 --> 19425037
time: 151.782854829 s
19425037

(For reference, \$15 \rightarrow 92{,}038{,}062\$)

Haskell, \$n=16\$ in about 9 minutes
As observed by @xnor in the comments, we can break the problem down into two parts: generate polyominoes (where I reused a lot from here, then count the ways to distribute the remaining cubes.
The symmetries are accounted for by using Burnside's lemma. So we need to know how many buildings of a given symmetric shape are fixed by a symmetry. Consider for example a shape has one mirror symmetry where the axis of reflection goes through \$s\$ squares of the shape and the reflection identifies \$d\$ pairs of further squares of the shape (so its size is \$s+2d\$). Then the buildings of this shape with \$r\$ additional cubes that have this symmetry correspond to the solutions of \$x_1+\dots+x_s+2y_1+\dots+2y_d=r\$ with nonnegative integers. The number of solutions is added to the total number of possibly equivalent buildings, and the sum divided by two. Note that a rotational symmetry always fixes zero or one square of a shape.
Compile the code with something like ghc -O2 -o buildings buildings.hs. The executable takes one optional parameter. If it is given, it will compute the number of buildings with that many cubes. Otherwise, it will compute all values.
{-# LANGUAGE BangPatterns #-}

import Data.List (sort)
import qualified Data.Set as S
import System.Environment (getArgs)

data P = P !Int !Int deriving (Eq, Ord)

start :: P
start = P 0 0

neighs :: P -> [P]
neighs (P x y) = [ p | p <- [P (x+1) y, P (x-1) y, P x (y+1), P x (y-1)],
                       p > start ]

count :: Int -> Int -> S.Set P -> S.Set P -> [P] -> Int
count 0 c _ _ _ = c
count _ c _ _ [] = c
count n c used seen (p:possible) =
  let !c' = count n c used seen possible
      !n' = n-1
      next = S.insert p used
      !sz = S.size next
      !c'' = c' + combinations n' sz (S.toAscList next)
      new = [ n | n <- neighs p, n `S.notMember` seen ]
  in count n' c'' next (foldr S.insert seen new) (new++possible)

class Geom g where
  translate :: Int -> Int -> g -> g
  rot :: g -> g
  mirror :: g -> g

instance Geom P where
  translate !dx !dy (P x y) = P (x+dx) (y+dy)
  rot (P x y) = P (-y) x
  mirror (P x y) = P (-x) y

instance (Geom g, Ord g) => Geom [g] where
  translate !dx !dy = map $ translate dx dy
  rot = sort . map rot
  mirror = sort . map mirror

normalize :: [P] -> [P]
normalize fig = let (P x y) = head fig
                in translate (-x) (-y) fig

-- fixed points of horizontal mirror symmetry
myf :: Int -> Int -> [P] -> Int
myf r sz fig =
  let w = (maximum [ x | P x _ <- fig ])
      wh = w `div` 2
      myb = sum [ 1 | P x _ <- fig, x == wh ]
  in if even w -- odd width!
     then c12 myb ((sz-myb) `div` 2) r
     else c1h sz r

-- fixed points of diagonal mirror symmetry
mdf :: Int -> Int -> [P] -> Int
mdf r sz fig =
  let lo = minimum [ y | P _ y <- fig ]
      mdb = sum [ 1 | P x y <- fig, x == y-lo ]
  in c12 mdb ((sz-mdb) `div` 2) r

combinations :: Int -> Int -> [P] -> Int
combinations r sz fig =
  let rotated = take 4 $ iterate (normalize . rot) fig
      rfig = rotated !! 1
      mirrored = map (normalize . mirror) rotated
      alts = tail rotated ++ mirrored
      cmps = map (compare fig) alts
      -- All fixed points computations assume that the symmetry exists.
      -- fixed points of quarter turn:
      qtfc = if even sz then c1q sz r else sc1x 4 sz r
      -- fixed points of half turn:
      htfc = if even sz then c1h sz r else sc1x 2 sz r
      -- fixed points of reflections:
      mirror_fc = [ fun r sz f |
                    f   <- [ fig, rfig ],
                    fun <- [ myf, mdf ]    ]
      -- all possibilities, i.e. fixed points of identity:
      idfc = c1 sz r
      fsc = [ qtfc, htfc, qtfc] ++ mirror_fc
      -- fixed points of symmetries that really exist:
      allfc = idfc : [ fc | (fc,EQ) <- zip fsc cmps ]
      -- group size of symmetry group:
      gs = length allfc
      res = if r==0 then 1 else sum allfc `div` gs
  in if any (GT ==) cmps
      -- only count if we have the smallest representative
      then 0 else res

-- Number of ways to express t as sum of n nonnegative integers.
-- binomial(n+t-1, n-1)
c1 n t = foldl (\v x -> v * (n+x-1) `div` x) 1 [1..t]

-- Number of ways to express t as twice the sum of n/2 nn-integers
c1h n t | even t    = c1 (n `div` 2) (t `div` 2)
        | otherwise = 0

-- Number of ways to express t as four times the sum of n/4 nn-integers.
c1q n t | t `mod` 4 == 0 = c1 (n `div` 4) (t `div` 4)
        | otherwise      = 0

-- Number of ways to express t as an nn-integer plus m times the sum
-- of n/m nn-integers
sc1x m n t = c1 (1 + n `div` m) (t `div` m)

-- Number of ways to express t as the sum of s nn-integers
-- plus twice the sum of d nn-integers
c12 s d t = sum [ c1 s (t-2*t2) * c1 d t2 | t2 <- [ 0 .. t `div` 2 ] ]

count_buildings :: Int -> Int
count_buildings n = count n 0 S.empty S.empty [start]

output :: Int -> IO ()
output n = putStrLn $ show n ++ ": " ++ show (count_buildings n)

main = do args <- getArgs
          case args of
            []  -> mapM_ output [1..]
            [n] -> output (read n)

Try it online!
Results
15: 92038062
16: 438030079
17: 2092403558
18: 10027947217   (2 1/2 h)
19: 48198234188   (10 h)
20: 232261124908  (40 h)

Okay, I didn't know that we were allowed to use magic. :) As far as I can tell, this solution is able to enumerate polyomino bases with fairly modest memory requirements (using roughly O(n²) memory (I think) where n is the number of cubes), and can count the number of buildings based on those polyominos with O(1) memory, so the program only requires a few megabytes of memory and is only limited by compute time. The math involved is still a bit over my head though.

"Counting polyominoes: yet another attack" by Redelmeier is helpful for understanding the definition of count

@Miles I really enjoy throwing math at problems. Not allowing that, or not allowing magic, is among the things to avoid in challenges.

"Allowed" was supposed to be tongue-in-cheek; it's a very impressive solution.

@Miles That answer also tried to be tongue-in-cheek ;-)

Java 11, \$n=17\$ in about 8.5 minutes
Based on Haskell solution by Christian Sievers – upvote his!
This answer is the result of learning enough Haskell to be able to understand Christian's answer, translating it into Java, applying numerous micro-optimizations, and throwing multiple cores at it. The exact runtime varies significantly depending on the number of cores available; this timing result is from my own two-core machine. A 48-core EC2 c5.24xlarge is able to compute \$n=17\$ in 16 seconds, and \$n=20\$ in 18 minutes.
Parallelism can be disabled by adding the JVM argument -Djava.util.concurrent.ForkJoinPool.common.parallelism=0. Single-threaded performance is slightly better than double that of the Haskell solution.
Some of the optimizations include:

Representing a point using a single int value
Using simplified hand-rolled collections based on int arrays, avoiding the primitive boxing required for the standard Java collections
Reimplementing polyomino enumeration based on this paper -- my initial attempt at a direct translation of the Haskell code performed extra throwaway work that didn't actually contribute to the computation
Replacing higher-level Stream-based implementations with inlined code, making it very ugly and verbose

The bulk of the processing time is spent in Array.sort calls in normalizeInPlace. Finding a way to compare polyomino transformations without sorting could easily result in a further 4x speedup. The forking is also not done very intelligently which leads to unbalanced tasks and unused cores at higher levels of parallelism.
import java.util.Arrays;
import java.util.concurrent.RecursiveTask;
import java.util.function.IntPredicate;
import java.util.function.IntUnaryOperator;
import java.util.function.LongSupplier;
import java.util.function.ToLongFunction;

/**
 * Utility methods for working with an int that represents a pair of short values.
 */
class Point {
    static final int start = p(0, 0);
    static final int[] neighbors = new int[] {-0x10000, -0x1, 0x1, 0x10000};

    static int x(int p) {
        return (p >> 16) - 0x4000;
    }

    static int y(int p) {
        return (short)(p) - 0x4000;
    }

    static int p(int x, int y) {
        return ((x + 0x4000) << 16) | (y + 0x4000);
    }

    static int rot(int p) {
        return p(-y(p), x(p));
    }

    static int mirror(int p) {
        return p(-x(p), y(p));
    }
}

/**
 * Minimal primitive array-based collections.
 */
class IntArrays {
    /** Concatenates the end of the first array with the beginning of the second. */
    static int[] arrayConcat(int[] a, int aOffset, int[] b, int bLen) {
        int aLength = a.length - aOffset;
        int[] result = new int[aLength + bLen];
        System.arraycopy(a, aOffset, result, 0, aLength);
        System.arraycopy(b, 0, result, aLength, bLen);
        return result;
    }

    /** Adds a new value to a sorted set, returning the new result */
    static int[] setAdd(int[] set, int val) {
        int[] dst = new int[set.length + 1];
        int i = 0;
        for (; i < set.length && set[i] < val; i++) {
            dst[i] = set[i];
        }
        dst[i] = val;
        for (; i < set.length; i++) {
            dst[i + 1] = set[i];
        }
        return dst;
    }

    private static final int[] primes = new int[] {
            5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
            67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131
    };

    /**
     * Allocate an array large enough to hold a fixed-capacity hash table
     * that can contain "seen" points for generating polyominos of size n.
     */
    static int[] makeHashTable(int n) {
        return new int[primes[-(Arrays.binarySearch(primes, n * 3) + 1)]];
    }

    /** Inserts a new value to a hash table, in-place */
    static void hashInsert(int[] table, int val) {
        int pos = (val * 137) % table.length, startPos = pos;
        if (table[pos] != 0) {
            while ((table[pos = (pos + 1) % table.length]) != 0) {
                if (pos == startPos) {
                    throw new AssertionError("table full");
                }
            }
        }
        table[pos] = val;
    }

    /** Checks whether a hash table contains the specified value */
    static boolean hashContains(int[] table, int val) {
        int pos = (val * 137) % table.length, startPos = pos;
        while (true) {
            int curr = table[pos];
            if (curr == val) return true;
            if (curr == 0) return false;
            pos = (pos + 1) % table.length;
            if (pos == startPos) {
                throw new AssertionError("table full");
            }
        }
    }
}

/**
 * Recursively generates int arrays representing collections of Points,
 * applying a function to each array to compute a long, and returns the sum
 * of all such values.
 */
class PolyominoVisitor extends RecursiveTask<Long> {
    PolyominoVisitor(ToLongFunction<? super int[]> func, int n) {
        this(func, n, 0, 1, new int[0], IntArrays.makeHashTable(n), new int[]{Point.start});
    }

    private PolyominoVisitor(ToLongFunction<? super int[]> action, int n,
                             int i, int limit, int[] used, int[] seen, int[] untried) {
        this.func = action;
        this.n = n;
        this.start = () -> visit(i, limit, used, seen, untried);
    }

    private final boolean visitSmaller = true;
    private final ToLongFunction<? super int[]> func;
    private final int n;
    private final LongSupplier start;

    @Override
    protected Long compute() {
        return start.getAsLong();
    }

    private long visit(int i, int limit, int[] used, int[] seen, int[] untried) {
        long val = 0;
        if (used.length + 1 == n) {
            // reached the second to last level, so we can apply the function
            // directly to our children
            for (; i < limit; i++) {
                val += func.applyAsLong(IntArrays.setAdd(used, untried[i]));
            }
        } else if (used.length + 6 < n && limit - i >= 2) {
            // eligible to split
            PolyominoVisitor[] tasks = new PolyominoVisitor[limit - i];
            for (int j = 0; j < tasks.length; j++) {
                tasks[j] = new PolyominoVisitor(func, n,
                        i + j, i + j + 1, used, seen, untried);

            }
            invokeAll(tasks);
            for (PolyominoVisitor task : tasks) val += task.getRawResult();
            return val;
        } else {
            // recursively visit children
            int[] newReachable = new int[4];
            IntPredicate inSeen = p -> !IntArrays.hashContains(seen, p);
            for (; i < limit; i++) {
                int candidate = untried[i];
                int[] child = IntArrays.setAdd(used, candidate);
                int reachableCount = neighbors(candidate, inSeen, newReachable);
                int[] newSeen = seen.clone();
                for (int j = 0; j < reachableCount; j++) IntArrays.hashInsert(newSeen, newReachable[j]);
                int[] newUntried = IntArrays.arrayConcat(untried, i + 1, newReachable, reachableCount);
                val += visit(0, newUntried.length, child, newSeen, newUntried);
            }
        }
        if (visitSmaller && used.length > 0 && limit == untried.length) {
            val += func.applyAsLong(used);
        }
        return val;
    }

    /**
     * Write the greater-than-origin neighbors of the given point
     * that pass the provided predicate into the provided array,
     * returning the count written.
     */
    private static int neighbors(int p, IntPredicate pred, int[] dst) {
        int count = 0;
        for (int offset : Point.neighbors) {
            int n = p + offset;
            if (n > Point.start && pred.test(n)) {
                dst[count++] = n;
            }
        }
        return count;
    }
}

/**
 * Function that computes how many buildings are constructable on a given
 * polyomino base. Considers symmetry, returning 0 if the figure is not the
 * canonical version (i.e. has a smaller transformation).
 *
 * Adapted largely unchanged from Christian Sievers
 * https://codegolf.stackexchange.com/a/199919
 */
class BuildingCounter implements ToLongFunction<int[]> {
    private final int n;

    public BuildingCounter(int n) {
        this.n = n;
    }

    @Override
    public long applyAsLong(int[] fig) {
        return combinations(n - fig.length, fig);
    }

    private static int[] map(int[] fig, IntUnaryOperator func) {
        int[] result = new int[fig.length];
        for (int i = 0; i < fig.length; i++) {
            result[i] = func.applyAsInt(fig[i]);
        }
        return result;
    }

    private static int[] normalizeInPlace(int[] fig) {
        Arrays.sort(fig);
        int d = fig[0] - Point.start;
        for (int i = 0; i < fig.length; i++) {
            fig[i] -= d;
        }
        return fig;
    }

    private static int[] rot(int[] ps) {
        return normalizeInPlace(map(ps, Point::rot));
    }

    private static int[] mirror(int[] ps) {
        return normalizeInPlace(map(ps, Point::mirror));
    }

    private static int myf(int r, int sz, int[] fig) {
        int max = Integer.MIN_VALUE;
        for (int p : fig) {
            if (p > max) max = p;
        }
        int w = Point.x(max);
        if (w % 2 == 0) {
            int wh = w / 2;
            int myb = 0;
            for (int p : fig) {
                if (Point.x(p) == wh) myb++;
            }
            return c12(myb, (sz - myb)/2, r);
        } else {
            return c1h(sz, r);
        }
    }

    private static int mdf(int r, int sz, int[] fig) {
        int lo = Integer.MAX_VALUE;
        for (int p : fig) {
            int tmp = Point.y(p);
            if (tmp < lo) lo = tmp;
        }
        int mdb = 0;
        for (int p : fig) {
            if (Point.x(p) == Point.y(p) - lo) mdb++;
        }
        return c12(mdb, (sz-mdb)/2, r);
    }

    private static long combinations(int r, int[] fig) {
        int[][] alts = new int[7][];
        alts[0] = rot(fig);
        alts[1] = rot(alts[0]);
        alts[2] = rot(alts[1]);
        alts[3] = mirror(fig);
        alts[4] = mirror(alts[0]);
        alts[5] = mirror(alts[1]);
        alts[6] = mirror(alts[2]);
        int[] rfig = alts[0];
        int[] cmps = new int[7];
        for (int i = 0; i < 7; i++) {
            if ((cmps[i] = Arrays.compare(fig, alts[i])) > 0) {
                return 0;
            }
        }
        if (r == 0) {
            return 1;
        }
        int sz = fig.length;
        int qtfc = (sz % 2 == 0) ? c1q(sz, r) : sc1x(4, sz, r);
        int htfc = (sz % 2 == 0) ? c1h(sz, r) : sc1x(2, sz, r);
        int idfc = c1(sz, r);
        int[] fsc = new int[] {qtfc, htfc, qtfc,
                myf(r, sz, fig), mdf(r, sz, fig),
                myf(r, sz, rfig), mdf(r, sz, rfig)};
        int gs = 1;
        int allfc = idfc;
        for (int i = 0; i < fsc.length; i++) {
            if (cmps[i] == 0) {
                allfc += fsc[i];
                gs++;
            }
        }
        return allfc / gs;
    }

    private static int c1(int n, int t) {
        int v = 1;
        for (int x = 1; x <= t; x++) {
            v = v * (n+x-1) / x;
        }
        return v;
    }

    private static int c1h(int n, int t) {
        return c1d(n, t, 2);
    }

    private static int c1q(int n, int t) {
        return c1d(n, t, 4);
    }

    private static int c1d(int n, int t, int q) {
        if (t % q == 0) {
            return c1(n / q, t / q);
        } else {
            return 0;
        }
    }

    private static int sc1x(int m, int n, int t) {
        return c1(1 + n / m, t / m);
    }

    private static int c12(int s, int d, int t) {
        int sum = 0;
        for (int i = t/2; i >= 0; i--) {
            sum += c1(s, t-2*i) * c1(d, i);
        }
        return sum;
    }
}

public class Main {
    public static long count(int n) {
        return new PolyominoVisitor(new BuildingCounter(n), n).compute();
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            System.out.println(args[0] + ": " + count(Integer.parseInt(args[0])));
        } else {
            for (int i = 1; i <= 99; i++) {
                System.out.println(i + ": " + count(i));
            }
        }
    }
}

Invocation
javac Main.java
java Main 17

Try it online!
Results
(when run without an argument)
...
16: 438030079
17: 2092403558
18: 10027947217
19: 48198234188
20: 232261124908
21: 1121853426115


text:
Is everything in order?
Challenge:
Input: a string, consisting of only printable ASCII characters
Output: a truthy/falsey value whether its characters are in alphabetical order (based on their UTF-8 unicode values), from any starting point inside the string including wrap-around by going left-to-right
For example: xyzabc would give a truthy result, because we could travel a→b→c→x→y→z, but xzy would give a falsey result, because all possible starting points (x→y→z; y→z→x; z→x→y) are not in the correct order.
This sounds pretty simple, right? But there is one catch, as this is a restricted-source challenge: your program/function has to be in the correct order† as well.
†: Based on the order of the characters in your own codepage. i.e. a program written in Jelly need to be (with the wraparound of course) in the order of its own codepage, instead of UTF-8 order.
Challenge rules:

The input can be in any reasonable format. Can be a string, read from STDIN, a list of characters, etc. (No, you are not allowed to take a list of unicode values - which would basically be an integer list - unless your language does this conversion by default (i.e. Java (char only), Whitespace, etc.)
The input is guaranteed to be printable ASCII (range \$[32,126]\$ / [' ','~']).
If your program/function is written in a different codepage, it does not necessary have to hold a truthy value when used as input for itself. The source code does need to be in the correct order based on the used codepage of course.
The input is guaranteed to be non-empty. (An input of one or two characters will always result in a truthy output.)
The input (and your source) can contain multiple of the same characters.
This is code-bowlingcode-challenge, for which the longest answer counting only distinct bytes wins (i.e. if your source code is ABBCabbc1223 your score would be 9 for 123ABCabc).

General rules:

Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code (i.e. TIO).
Also, adding an explanation for your answer is highly recommended.

Test cases:
Truthy:
~
ab
ba
```
*5a
Test
test
xyzabc
aaabbbccc
aaabbbCCC
AAAbbbccc
msuwy !#),-./0123:;<?@BCFGILMNOQTWX]^_bf
oqqx}}~#$'''*+-./33489=?ABCHLQQQRTW[\]^_abcfgjkklmnno

Falsey:
xzy
C-U
TeSt
tesT
aaaBBBccc
M3"b=J7Uh:kg&F~\p`GLx?9#!%XCOZBv.m_)Y4V*

related

IMHO I find it a bit too bad that a single rule disallows per se most programming languages and allows only cryptic-characters-languages-created-only-for-golfing, it could be more open by for example counting the longest ordered sequence in the code. (But that would mean not counting commented characters to prevent having the whole alphabet as a comment, even if that would damage a bit current aswer)

@Kaddath I can understand your standpoint and kinda agree, but I don't think banning comments would help, since we don't have a clear definition of what a comment is. The current 05AB1E for example doesn't use any comments (in fact, the language doesn't even have comments), although there are still loads of no-ops which cancel each other out so only the code functionality remains. And not allowing no-ops kinda defeats the [code-bowling] part tbh.

I'm willing to change the challenge to allow more answers (if Grimmy agrees), but it should require a clear definition of what is and isn't allowed. Currently I'm thinking of only allowing the 256 default characters of the used code-page perhaps (extended ASCII for most languages), so 256 would be the maximum score, and you can't for example score 137,929 by using all existing characters in for example a Lenguage/Unary answer. And comments are then still allowed. But not sure if that's a good solution.

(if Grimmy agrees) I do. (Note that 256 is already the maximum score, since score is the number of distinct bytes).

@Grimmy Thanks for agreeing, but I'm still not really sure how to change the challenge. If I add that you have to maximize the largest portion of your used code page in your source code, everyone would just put all 256 bytes after one-another in a comment.. I.e. (used ASCII only as example) the source code # !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~. I could ban comments, but what counts as a comment in that case? "this is a comment"\  is what I sometimes add in my 05AB1E answers, but it's not really a comment.. Where to draw the line.

05AB1E, 10 ... 172 distinct bytes
\]^_abcdefghiijklmnopqrstuvwxyz{|}}}~ƵƵ€Λ‚„…†‡ˆ‰ŠĆĆĆŽƶĀ‘‘’’““””••–—™š›œćŸā¡¢¢¢¤¤¦§¨©ª«¬®¯°±´¶·¸º»¼½½¾¿ÀÁÁÂÃÄÅÇÌÍÐÐÐÐÐÐÑÒÓÔÕÖ×ØÙÚÛÜÝßàáâãäåçèéêëìíîïðñòóôõö÷úü
 -.0123456789;<>@ABCDDDHKKOPQRSTUVWXYZ

Try it online! or validate all test cases (note: the "all test cases" version omits ] and ë, since those don't play well with the header and footer required to run the code repeatedly).
Uses the 05AB1E code page. Validate restricted-source and scoring.
The useful code is just:
Ć            # append the first character of the input to the input
 Ç           # convert to a list of codepoints
  ü-         # pairwise subtraction
    1@       # >= 1?
      D      # duplicate
       O     # sum
        Q    # equal?
         Z   # maximum

The rest amounts to NOOPs.

Nice answer. I wasn't expecting that the entire alphabet (except for q) could be used as a no-op like that. :) And I've verified that it's indeed correct for 05AB1E's codepage, but you may want to explicitly mention it uses the custom 05AB1E codepage for challenges like this. Btw, you can add a few more no-ops between the Q and Z, like R and S for example, as well as UX or VY. :)

Actually q can be used as well, since it's within a non-executed i} anyway. And yeah, I'm not done bowling, there's still a ton of bytes to add.

@KevinCruijssen I'm done with the low-hanging fruits. Of the 96 missing bytes, 46 are the bytes between ü and -, which can't be separated except by whitespace.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
What's my telephone number?
Introduction
The telephone numbers or involution numbers are a sequence of integers that count the ways \$n\$ telephone lines can be connected to each other, where each line can be connected to at most one other line. These were first studied by Heinrich August Rothe in 1800, when he gave a recurrence equation where they may be calculated. It is sequence A000085 in the OEIS.
Some help

The first terms of the sequence are \$1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496\$
It can be described by the recurrence relation \$T(n)=T(n-1)+(n-1)T(n-2)\$ (starting from \$n=0\$)
It can be expressed exactly by the summation \$T(n)=\sum\limits_{k=0}^{\lfloor n/2 \rfloor}{n\choose 2k}(2k-1)!!=\sum\limits_{k=0}^{\lfloor n/2 \rfloor}\frac{n!}{2^k(n-2k)!k!}\$ (starting from \$n=0\$)
There are other ways to get the telephone numbers which can be found on the Wikipedia and OEIS pages

Challenge
Write a program or function which returns the \$n^{th}\$ telephone number.
I/O examples
(0 based indexing)
input --> output

0  -->            1
10 -->         9496
16 -->     46206736
22 --> 618884638912

Rules

Input will be the index of the sequence
The index origin can be anything
As the numbers can get very large, you only need to support numbers as large as your language can handle
Standard I/O rules apply
No standard loopholes
This is code-golf so shortest code in bytes wins

Oasis, 7 6 5 bytes
àn*+1

Try it online!
# to compute the nth telephone number f(n):
à      # push the telephone numbers f(n-1) and f(n-2)
 n     # push n
  *    # multiply: n * f(n-2)
   +   # add: n * f(n-2) + f(n-1)

1      # base case: f(0) = 1

5 bytes in what charset? in UTF-8 the à character is 2 bytes, so it's 6 bytes in UTF-8. -  is it Windows-1252 perhaps?

@hanshenrik 5 bytes in Oasis' charset, which is certainly not UTF-8. I'm not sure what exactly that charset is, but I don't see why that would matter. You can see all available characters here, maybe you can guess the charset from that.

can you provide a base64 or hex encoded copy of the source code?

@hanshenrik gosh, I'd have to actually download Oasis for that. I only ever used it through TIO, and TIO doesn't provide that functionality. But TIO does tell you the byte count, and that's what matters for code golf, right?

well just to be sure i checked the source code (specifically line 620), it's Windows-1252 indeed, which makes it 5 bytes. and hex-encoded it's e06e2a2b31

Python, 33 bytes
f=lambda n:n<2or~-n*f(n-2)+f(n-1)

Try it online!
Uses the recursive formula.

cQuents, 10 bytes
=1:Z+Y($-2

1-indexed.
Try it online!
Explanation
=1           first term in sequence is 1
  :          given n, output nth term in sequence (1-indexed)
             each term is
   Z+                     (n-1) term +
     Y                                 (n-2) term *
      ($-2                                          (index - 2)

TI-BASIC, 28 22 bytes
∑((Ans nCr (2K))(2K)!/(2^KK!),K,0,int(.5Ans

Input is n in Ans.
Output is the nth telephone number.
I was going to use the first formula mentioned in the challenge, but testing it resulted in ERROR: OVERFLOWs even on smaller numbers because TI-BASIC handles n!! as two successive factorials instead of a double factorial.
At least it has a builtin for summation notation!
Update:
I found that \$(2k-1)!!=\frac{(2k)!}{2^kk!}\$, so i replaced the function i was using to \${{n}\choose{2k}}\frac{(2k)!}{2^kk!}\$, which is represented as (Ans nCr (2K))(2K)!/(2^KK!) in TI-BASIC.
Explanation:
∑((Ans nCr (2K))(2K)!/(2^KK!)               ;sum the equation mentioned above
                             ,K             ;using K as the loop variable
                               ,0           ;starting at 0
                                 ,int(.5Ans ;and ending at the floor of half of the input
                                            ;leave the result in Ans
                                            ;implicit print of Ans

Examples:
10:prgmCDGF26
            9496
5:prgmCDGF26
              26

Note: TI-BASIC is a tokenized language.  Character count does not equal byte count.

Jelly, 6 bytes
Œ!ỤƑ€S

A monadic Link accepting a non-negative integer which yields a positive integer.
Try it online! Or see the first 10 (n=10 is too slow)
How?
Builds all permutations of [1...n] (or if n=0 just [[]]) and counts the number which are involutions.
Œ!ỤƑ€S - Link: integer, n     e.g.  0        3
Œ!     - all permutations          [[]]     [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    €  - for each:
   Ƒ   -   is invariant under:
  Ụ    -     grade                ( []       [1,2,3] [1,3,2] [2,1,3] [3,1,2] [2,3,1] [3,2,1] )
       -   }                        [1]     [1,      1,      1,      0,      0,      1]
     S - sum                        1       4

I tried doing something like this in 05AB1E, but it ended up longer than the recurrence relation. Really clever use of "grade"!

JavaScript (ES6), 25 bytes
0-indexed. Uses the recurrence relation.
f=n=>n<2||f(--n)+n*f(n-1)

Try it online!

05AB1E, 12 8 bytes
-4 bytes by porting Stephen's cQuent answer
1λèsN<*+

Try it online!

Haskell, 29 bytes
f n|n<2=1|m<-n-1=f m+m*f(n-2)

Try it online!
Implements the recursive formula.

Nice use of pattern guards!

C (gcc), 40 bytes
long f(long n){n=n<2?1:f(--n)+n*f(n-1);}

Try it online!
Merely copied from @Arnauld answer

Python 3, 81 \$\cdots\$ 57 56 bytes
def f(n):
 a=b=i=1
 while i<n:a,b=a+i*b,a;i+=1
 return a

Try it online!
Uses 0 based indexing and implements the recursive formula.

Perl 6, 26 bytes
{{(1,1,++$×*+*...*)[$_]}}

Try it online!

Why does this require two sets of {}? The behavior of {(1,1,++$×*+*...*)[$_]} is different and I don't understand why.

@SirBogman With out the double braces, the state variable $ isn't reset across multiple runs of the function. The inner braces create a separate lexical scope for $ causing it to be reset whenever the function is run.

Mathematica 46 42 bytes
f=2^(#/2)HypergeometricU[-#/2,.5,-.5]I^-#&

Try it online!
Thanks to mabel for helping me shave 4 bytes by using what I think is an anonymous function.
As seen in https://www.wolframalpha.com/input/?i=OEIS+A000085 and http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheSecondKind.html

hi! you may want to add a link to Try It Online so other people can test out your code. (I've also saved a few trivial bytes)

@mabel Ty for the suggestion and the 4 bytes off ;)

no problem @RGS

J, 25 bytes
($:+]*$:@<:)@<:`1:@.(<&2)

Try it online!
$: is J's recursion operator, so this is a fairly straightforward impl of the recursive def.
I tried a couple other approaches (including using ^: power of operator) but wasn't able to get shorter than this.
Am curious if anyone can improve it...

Hint: generating function

I actually tried this approach with the t. adverb but got a domain error on the Wikipedia generating function

Yeah I found J being restrictive too, but messing around gave (^*^@(]*-:))t.*! which works https://tio.run/##y/r/P83WSiNOK85BI1ZL10pTs0RPSxEoqJCpZ2RQAQA

Interesting... ty!  Feel free to post as separate answer, otherwise Ill update mine in a few hours when Im back on my laptop

I'll leave it to you. And I forgot, ]*-: can obviously become *-:

" The domain of the adverb t. is the same as the left domain of the derivative D."
So that was a lie.

FYI, the t. adverb was removed in J901, released in December 2019.

@SirBogman Oh interesting, thank you

Red, 53 bytes
f: func[n][either 1 > n: n - 1[1][n *(f n - 1)+ f n]]

Try it online!

@RGS Oh, I totally forgot that the function is recusrsive! You're right, I need to include f:  to the bytecount. Thanks!

don't worry ^^ I'm just vouching for clarity :)

PHP, 48 bytes
function f($n){return$n<2?1:f(--$n)+$n*f($n-1);}

Try it online!
Implementation of the recursive function.
Original version: 54 bytes (port of @Noodle9 answer):
for($i=$j=1;++$n<$argn;$j=$k){$k=$i;$i+=$n*$j;}echo$i;

Try it online!

Charcoal, 20 bytes
⊞υ¹ＦＮ⊞υ⁺§υι×ι§υ⊖ιＩ⊟υ

Try it online! Link is to verbose version of code. Uses the recurrence relation. Explanation:
⊞υ¹

T(0)=1
ＦＮ

Loop n times.
⊞υ⁺§υι×ι§υ⊖ι

T(i+1)=T(i)+iT(i-1)
Ｉ⊟υ

Output T(n).

Keg, 21 bytes
:1≤[_1|;:@Tƒ^:;@Tƒ*+]

Try it online!
Simply implements the formula in a recursive manner. The footer is mainly for testing purposes

Retina 0.8.2, 80 bytes
.+
$*_;;_;
{`^_(_*;)(_*;_+)
$1_$2,$2
+`(,_*)_(;_+;(_*))|,
$3$1$2
^;_*;(_*).*
$.1

Try it online! Explanation:
.+
$*_;;_;

Initialise the work area with n, i=0, and T=[1] (note that the list indices are reversed, so that the first element of T is T[i] and the last is T[0]) converted to unary.
{`

Loop n times (actually until the buffer stops changing, but see below).
^_(_*;)(_*;_+)
$1_$2,$2

Decrement n, increment i, and make extra copies of i and T[i].
+`

Repeat i times.
(,_*)_(;_+;(_*))|,
$3$1$2

Decrement the copy of i and add T[i-1] to the copy of T[i], stopping when the copy reaches zero by deleting the , entirely, causing the repeat to terminate. The result is therefore T[i+1]=T[i]+iT[i-1].
^;_*;(_*).*
$.1

When n is zero, replace the work area with T[i] converted to decimal. This causes the loop to terminate as the stages can no longer match.

Japt, 28 26 bytes
_pZÌ+(ZÊÉ *ZgJÑ}g´U1õ ï)gJ

Try it
pZÌ+(ZÊÉ *ZgJÑ   make sequence with next element from previous sequence

_    ...  }g´U    repeat input -1 times
  1õ ï)          starting with [[1,1]]
       gJ        implicit output last element of resulting sequence

GolfScript, 16 bytes
This is inspired by the Fibonacci GolfScript program.
~,1.@{)*1$+\}/\;

Try it online!
Explanation
~,               # Generate exclusive range from input to 0
  1.             # Make 2 copies of 1
    @            # Make the each target on the top
     {      }/   # Foreach over the range
      )          # Increment the current item
       *         # Multiply top by the current item
        1$+      # And add by the second-to-top
           \     # Swap items
              \; # Swap & discard the bottom item

Elm, 45 bytes
f n = if n<2 then 1 else (n-1)*f(n-2)+f(n-1)

Try it online!
Implementation of the recursive function.

k4, 53 bytes
{+/{*/[1+!x]*%*/[y#2]**/*/'1+(!x-2*y;!y)}[x]'!1+_x%2}

   {                                    }[x]'!1+_x%2 /pass inner lambda 2 args - x and each (') enumerate (!) 1+floor float-div 2
                             (!x-2*y;!y)             /enumerate
                           1+                        /add 1 to both list items
                        */'                          /multiply over each - this gives both denominator factorials
                      */                             /multiply them
              */[y#2]                                /make list of 2s of y-length and multiply over - gives y^2
                     *                               /multiply left and right args
             %                                       /reciprocal
    */[1+!x]                                         /x factorial
 +/                                                  /sum

examples:
  {+/{*/[1+!x]*%*/*/[y#2],*/'1+(!x-2*y;!y)}[x]'!1+_x%2}'[0 3 10 14]
1 4 9496 2390480f

K (ngn/k), 27 bytes
{*|x{x,+/(2#|x)*1,#2_x}/!2}

Try it online!

x{...}/!2 setup a do-reduction with x (the input) as the number of iterations to run, seeded with 0 1 (the first two terms of the sequence)
1,#2_x build list containing how to multiply the previous values (i.e. T(n-1) by 1, and T(n-2) by n-1). Note that this infers the value of n from the length of the sequence so far.
(2#|x)* get the last two values of the reversed sequence (i.e. (x[n-1];x[n-2]))
x,+/ take their sum, and append to the sequence
*| return the last value of the generated sequence

Husk, 7 bytes
#S=ηÖPḣ

Try it online! or Verify first 10 values
Same idea as the Jelly answer, and equally as slow.
0-indexed.
Explanation
#S=ηÖPḣ
      ḣ range 1..n
     P  permutations
#       number of arrays which satisfy:
 S      self
  =     equals
   η    indices of
    Ö   ordered elements?

APL (Dyalog Unicode), 37 bytes
{⍵<2:1⋄+/(2⍵-1)×∇¨⍵-⍳2}

Try it online!
-1 byte from Adám.

1, can be 2

Stax, 7 bytes
öƒ◙─v◙6

Run and debug it

Japt, 16 12 11 bytes
1-indexed
È+T°*ZÔÅÎ}g

Try it

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Selfish Programs
The Challenge
Write two programs P and Q such that:

P and Q are written in the same language
The output of P is Q
The output of Q is P
P and Q are both non-empty

Simple enough. Surely that's been done here before. Where this gets interesting is the scoring.
Scoring

P and Q are selfish, they don't want to sheir their precious characters! The primary means of scoring is the number of source characters existing in both P and Q. The lower the number the better.
If two programs share the same number of characters, the sum length of their programs will be the tie breaker.

Clarification and Example
There's two ways to interpret this and I feel an example would best explain which is correct.
We say the programs aabb and bbcc share a single character, b, NOT two characters b and b

I think you should at least require that the two programs are nonempty. You might want to let this sit in the sandbox a while, since there are probably other things I haven't thought of that might hurt your chances at getting interesting answers.

@FryAmTheEggman nice catch!

Possible duplicate: Mutually exclusive quines. If we assume this challenge is also asking for proper quines, the winner of the linked challenge will also win here (primary score 0 and shortest length sum as the tiebreaker). If non-proper quines are allowed, P and Q should at least be distinct, otherwise the answer zone will be flooded with trivial answers like P = Q = 1.

@Bubbler oh wow, that was pretty much my original thought, but I though only allowing no overlap might exclude too many languages. Guess I was wrong XD


text:
Internal Truth Machine
It's a normal truth machine but instead of taking input, it uses the first character of the program. Thus, internal.
The 0 and 1 are plain characters, i.e. ASCII code 0x30 and 0x31 respectively.
Example: 0abcd prints 0 and halts, and 1abcd prints 1 infinitely. Then your submission is abcd, whose score is 4 bytes. The 0 or 1 (the first character of the program) is not counted towards your score.
Of course, you're not allowed to look inside the file itself. Like a quine.
Leaderboard
Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 198288; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '
' + c.body.replace(OVERRIDE_REG, '') + '
';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });

  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/ b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Wait, why did you post it so fast from the Sandbox?

So, to make sure I understand, this requires two programs in the same language that differ only in the first character being either 0 or 1?

Yes, and it acts like an input to the normal truth machine.

Does the input bit count as part of the program?

Well, when I had it in mind, I thought of including it, but now, I guess not.

Must output be STDOUT or is STDERR or exit code also fine?

Quasi-duplicate of Implement a Truth-Machine. The added restriction on input doesn't make it distinct in an interesting way.

I agree with the suggested dupe. Let's dupe-hammer this if Grimmy's comment reaches 4 votes (assuming it's not closed as dupe first by standard votes)

@Grimy, My code would change quite a bit though, shaving ten bytes off, and my answer here wouldn't work.

@LuisMendo, But I think one major qualification for whether a question here is a duplicate is whether the answers here would answer the question for the proposed duplicate (even with trivial changes). But I don't think that is the case. Maybe for a couple of languages. But not for many of these. The Lua answer there would not work here, and in fact, it's impossible to answer this challenge here in Lua. That certainly has to be taken into consideration.

Although I agree with Grimmy and something else could have been chosen as output for 1/0 respectively, I don't really see it as a dupe. Uninteresting since we already have the other challenge: definitely; but dupe: not really. This challenge isn't even possible in Java or Whitespace for example (a.f.a.i.k.), and although the core part is indeed the same, getting around that leading 0/1 will be tricky in some languages. EDIT: Ah, @ouflak already mentioned everything I said I now see..

@ouflak, Kevin: Ok, not a dupe then

Python 3, 29 bytes
 or~print(0)
while 1:print(1)

A full program, which if prefixed with 0 will print 0 then halt, exiting with an error, or if prefixed with 1 will print 1 forever.
Try 0 online!
Try 1 online!
The right of a logical or is only executed if the left is falsey (which 0 is, while 1 is not).
If the prefix is 0 the argument, print(0), of bitwise-not, ~, is evaluated - this has a side-effect of printing 0 and returns None which is an invalid argument for ~ causing an error which halts the program.
If the prefix is 1 the code ~print(0) is not evaluated  and the infinite loop of while 1:print(1) is reached.

That's really clever. Have an upvote.

It's just as long, but exit('0') instead of ~print(0) would work without the error...

@AVee True, although exit prints to stderr which would mean different output streams for the two programs - I'd  want to check that was acceptable.

W, 2 bytes
You know, duplicate the first character and apply while. Simple enough.
:w

Explanation, applied the bits
1:  % The condition and the body is both 1
  w % While the condition 1 is true, output 1

Explanation 2
0:  % The condition and the body is both 0
  w % This while does not get executed
    % The condition 0 gets returned & printed

I really like this solution. Short and to the point. +1

R, 20 bytes
->a
while(print(a))0

0Try it online!
1Try it online!
Uses rightwards assignment ->, which I now seem to use about once a month on this site (and never anywhere else).

I knew this would be here. The only use I've ever thought of for -> outside of the site is at the end of a long pipe expression, but that's actually more confusing for future readers than it's worth.

@Giuseppe maybe you paste some data into console, and then realized that you need assign it to some variable...

@tsh that's pretty much where I use it, when I'm skunkworksing some big pipe expression and need to use it as a vector mask or something

I use it in setClass statements (you certainly don't have to, it just looks nicer to me to do setClass("myClass",...) -> myClass though I can't put my finger on why)

x86-16 machine code, IBM PC DOS, 11 bytes
Binary:
(0 example)
00000000: 3002 ad8a d03c 30cd 2175 fcc3            0....<0.!u..

(1 example)
00000000: 3102 ad8a d03c 30cd 2175 fcc3            1....<0.!u..

Unassembled listing:
?? 02       DB  ?, 2        ; first byte is '1' or '0', second byte is DOS write char fnc
AD          LODSW           ; load input from [SI] into AL, INT 21H function 2 in AH
8A D0       MOV  DL, AL     ; output to DL
3C 30       CMP  AL, '0'    ; is input 0?
        OUTPUT:
CD 21       INT  21H        ; write to console
75 FC       JNZ  OUTPUT     ; if not a '0', keep looping forever
C3          RET             ; return to DOS (only if it was a 0)

Explanation:
The first byte of the program is either a '0' or a '1', and combined with a second byte of 2 (more on that later) decodes to a benign instruction of either XOR [BP+SI], AL or XOR [BP+SI], AX.  In PC DOS, many registers are initialized to known values, so we know that AX is 0, and SI is 100H which is the first byte of the program.  Whatever memory address [BP+SI] translates to, it simply XOR's 0 to it, doing nothing.
The LODSW instruction puts the input byte into the AL register and a 2 into the AH register, which is the DOS INT 21H API function number to write an ASCII char in DL to the console.
The input is compared and ZF (zero flag) is set "true" if input is a 0.  The char is written to the console and if ZF is not zero, it will loop indefinitely.
Output of both variants:

Haskell, 32 bytes
!f=f 0
_!f=f 1*>0!f
main=0!print

I think this is the only answer posted so far where the first character (the digit) isn't the entry point.
Anyway, explanation: I'm creating an operator function called !, and defining it by cases. We enter the top case if the left operand matches the program's first digit, and the bottom case otherwise. The right operand is bound to f in both cases (and it happens to always be print). In the top case, we just print a 0. In the bottom case, we print a 1, and then recursively call ourself with the same operands. (We know the left operand will always be 0.) Finally, main, the entry point, calls our operator with 0 and print.
Try it online with 0!
Try it online with 1!

05AB1E, 3 bytes
µ=0

Try 0µ=0 online!
Try 1µ=0 online!
Also 3 bytes:
i[,

Try 0i[, online!
Try 1i[, online!

Jelly, 3 bytes
Ṅḷ¿

Try 0 online!
Try 1 online!
 Ṅḷ¿ - Main Link: no arguments
.    - set Left to 0 or 1
   ¿ - while...
  ḷ  - ...condition: Left
 Ṅ   - ...do: print and yield (Left)
     - implicit print (Left)

Scratch 3.0, 10 blocks/80 bytes

As SB Syntax:
//1 or 0
repeat until<(n)=[0
say[1
end
say[0
define 0
set [n v]to[0
define 1
set[n v]to[1

It's more of a snippet than a program, but it works.
Try it online Scratch!

><>,  6  5 bytes
-1 thanks to Jo King!
:n?!;

Try 0 online!
Try 1 online!
How?
Instruction pointer starts at the top left (i.e. 0 or 1) facing right. If the instruction pointer leaves the code it wraps around to the other side, continuing in the same direction.
X:n?!; -               X=0                X=1
X      - push X          {0}                {1}
 :     - duplicate       {0,0}              {1,1}
  n    - pop & print     {0,} "0"           {1} "1"
   ?   - pop & if...     {}                 {}
    !  - ...truthy:      skip & wrap to X
     ; - ...falsey:                         exit

Labyrinth, 5 bytes
"
!"@

Try 0 online!
Try 1 online!
How?
Instruction pointer starts at the top left (i.e. 0 or 1) facing right, the stack starts as infinite zeros.
0:
0"
!"@

  - stack = {0,0,0,...} (infinite supply of zeros)
0 - multiply top of stack by 10 and add 0 {0,0,0,...}
  - 2 neighbours, 0 -> go forward
" - no-op {0,0,0,...}
  - 2 neighbours -> go forward
" - no-op {0,0,0,...}
  - 3 neighbours T-junction from stem, 0 -> turn around
" - no-op {0,0,0,...}
  - 2 neighbours -> go forward
0 - multiply top of stack by 10 and add 0 {0,0,0,...}
  - 2 neighbours -> go forward
! - pop top of stack, print as decimal "0" {0,0,0,...}
  - 2 neighbours -> go forward
" - no-op {0,0,0,...}
  - 3 neighbours T-junction from side, 0 -> go forward
@ - exit labyrinth

1:
1"
!"@

  - stack = {0,0,0,...} (infinite supply of zeros)
1 - multiply top of stack by 10 and add 1 {1,0,0,...}
  - 2 neighbours -> go forward
" - no-op {1,0,0,...}
  - 2 neighbours -> go forward
" - no-op {1,0,0,...}
  - 3 neighbours T-junction from stem, 1 -> turn right
! - pop top of stack, print as decimal "1" {0,0,0,...}
  - 2 neighbours -> go forward
1 - multiply top of stack by 10 and add 1 {1,0,0,...}
  - ...etc.

APL (Dyalog Unicode), 8 bytesSBCS
{⍞←⍺}⍣≠1

0Try it online!
1Try it online!
Prints to stderr.
How they work
0{⍞←⍺}⍣≠1
 {⍞←⍺}⍣≠   ⍝ Iterate {⍞←⍺} until (next value)≠(prev value) is true
 {⍞←⍺}     ⍝ First iteration: print and return left arg (0)
       ≠   ⍝ (next value)=0, (prev value)=1, so 0≠1 is true
           ⍝ Function terminates

1{⍞←⍺}⍣≠1
 {⍞←⍺}⍣≠   ⍝ Iterate {⍞←⍺} until (next value)≠(prev value) is true
 {⍞←⍺}     ⍝ First iteration: print and return left arg (1)
       ≠   ⍝ (next value)=1, (prev value)=1, so 1≠1 is false
 {⍞←⍺}     ⍝ Second and subsequent iterations: called with the same arg (1)
           ⍝ Never terminates; prints 1 infinitely

I tried translating this into J to improve my current approach but wasn't able to.  Is J's ^:v^:_ just fundamentally different from the APL iterate or am I missing something?

@Jonah I guess it's because J's ^:_ is special-cased to find the fixed point. So it stops not only when v gives 0, but also when the right argument doesn't change.

Yeah that was the problem.

Befunge-93, 5 bytes
:_.@#

Try 0 online
Try 1 online
First submission, and I only started learning Funge yesterday, so it's very likely there's a shorter solution.
I tried to find a way to remove the need for the ":" but I couldn't.

Welcome to CGCC! This is a very nice solution

Pyth, 65 63 56 bytes
Pyth's prefix operators don't really suit well to this challenge...
Ws@`$__import__("inspect").stack()[1][0].f_locals$_101
1

Edit 1: Saved 2 bytes by letting Pyth do the dictionary index, and using h instead of @<py_code>0 because I remembered it exists.
Edit 2: Saved 7 bytes because @isaacg found an even sillier trick :)
Try it online!

I really like this! I found a even sillier way to shorten it a bit more by removing the need for the "pyth_code" index. 56 bytes: Try it online!

@issacg Clever! also thanks for making such a fun little language to play with, I've sunk more time into it than I'd like to admit >.<>, 12 10 bytes
:?vn;
 n:<

-2 bytes thanks to @JonathanAllan
Answer History
 :?vn;
>:n:<

Try it online!
or
Try it with 1
Try it with 0
Explained

Path visualiser is https://fishlanguage.com/
Gif converter is https://www.onlineconverter.com/video-to-gif

Save two using wrapping.

5 bytes by keeping it 1D.

But then that would be the same as the other 5 byte ><> answer

Oh, didn't notice that.

Raku, 14 11 bytes
,1...&say^1

0Try it online! 1Try it online!
Abuses the range operator to loop infinitely and the XOR Junction (^) to print and to evaluate if the range should stop.

Perl 6, 16 15 bytes
-1 byte thanks to Jo King
&&1 xx*X[&put]$

Try0 it online!
Try1 it online!

Using X with a custom operator is very clever. My thought was to use ..., but that only ties with your old solution. Try it online!

@JoKing You can replace +* with 1 for -1 byte, so both approaches are tied again.

Aha! Figured out how to eliminate another byte from my solution

Cubix, 5 bytes
^O?@u

0 Try it online!
1 Try it online!
Maps onto the cube like
  0
^ O ? @
  u

^ Redirect up onto the top face
0 or 1 pushed to the stack
? test

uO?@ if 0 then u-turn onto the integer output pass through the  test again and halt
O^ if 1 output the integer and redirect up again

Turing Machine Code, 29 bytes or 28 bytes
With the strange rule that the leading '0' or '1' doesn't count towards the byte count.
0 0 1 * 1
* _ 0 * 1
* 1 1 r 1

Try '0' online!
1 0 1 * 1
* _ 0 * 1
* 1 1 r 1

Try '1' online!

PHP, 24 bytes
?:die(0.);for(;;)echo 1;

Uses ternary condition knowing that in PHP one of the alternatives can be empty and i doesn't need to be assigned to a variable.
0: Try it online!
1: Try it online!
Edit: had to add '0' to properly echo zero
Edit2: Had forgotten that die was synonym of exit (thanks manual)
Edit3: saved 1 byte with for(;;) instead of while(1)
Edit4: saved 1 byte with die(0.) instead of die('0') thanks to @Christoph

You can use die(0.); to save a byte only integers get returned instead of printed.

Python 3, 37 bytes
and exec('while 1:print(1)');print(0)

0: Try it online!
1: Try it online!

MathGolf, 3 bytes
Äo↑

Try 0Äo↑ online.
Try 1Äo↑ online.
Explanation:
1     # Push 1
   ↑  # While true without popping,
 Ä    # by using a single builtin as inner block:
  o   #  Print with trailing newline without popping

0     # Push 0
   ↑  # While true without popping
      # (output the entire stack joined together implicitly as result)

PowerShell, 21 bytes
0|?{$_}|%{for(){1}};0

Try it online!

Keg, 4 bytes
{:|④

Try it online!
It seems I'm a bit late to the party! ¯\_(ツ)_/¯
Anyhow, this is simply a modification of the usual truth machine This is literally the same truth machine as it would be if we didn't have to place the digit at the start. Funny how implicit input works.
By this, I mean it doesn't matter if y'all place the digit at the start or you place it in input.
(⌐■◡■)

JavaScript, 34 bytes
?(_=>{for(;;)alert(1)})():alert(0)

Try it online!

Would a recursive function be legal, along the lines of (g=_=>g(alert(1)))()?

?(a=1):(a=0);do alert(a);while(a) is 33 bytes long

?eval('for(;;)alert(1)'):alert(0) is 33 bytes also.

You can also remove brackets from @tsh suggestion ?a=1:a=0;do alert(a);while(a)

?a=1:a=2;for(;a;)alert(a&=1) funny version still based on @tsh suggestion

@AZTECCO I'd post yours as it's own answer, I feel it's a little too novel for me to take...

><>, 15 9 bytes
?\0n;
n1<

Try it online!

-6 bytes thanks to JoKing

My first fish program, doesn't beat the other one but I wanted to post it anyway. Beats the other one now!
Explanation:
For 0:
0? skip the next command
0 push 0 to the stack
n output the top of the stack
; terminate
For 1:
1? don't skip the next command (no-op)
\ mirror down
> switch direction to forward
1 push 1 to the stack
n output, then wrap round

@JoKing "d"o can be replaced with dn I tried that but TIO outputs unrecognised characters... am I missing something?

Oh right I used o not n because apparently I can't read. Thanks!

Charcoal, 6 bytes
1ＷΣ⊟ＫＡＤ

Try it online! Link is to verbose version of code.
0ＷΣ⊟ＫＡＤ

Try it online! Link is to verbose version of code.
Explanation: The leading 1 or 0 simply prints literally to the canvas. There then follows a while loop, the condition of which is the digital sum of the last character on the canvas. Thus if this is zero, the loop never gets off the ground, and the canvas gets implicitly output with the 0 still on it. However, if this is a non-zero digit, such as 1, then the loop will dump a copy of the canvas for ever. (Note that the dump command has a rate limit on it, so that TIO will time out before the output reaches the size limit.)
There are a few variants with the same byte count, such as using Cast rather than Sum, or Maximum or Minimum rather than Pop, or even by using Count or Find instead.

Alchemist, 27 bytes
a->a+Out_b
_+0a->a+b
a+b->_

Try it online with 0!
Try it online with 1!
This was a bit tricky.  Every execution path up to the first application of the first line must be possible in both programs, and the two possible patterns in the first line are mutually exclusive.  Hence, in order for the program to work, execution up to that point must be non-deterministic.  This program swaps infinitely between two states until the first line is applied.
0a->a+Out_b    # the 0 version: from the initial state, add an a to halt and output 0
1a->a+Out_b    # the 1 version: from the a+b state, output 1 and leave the state unchanged
_+0a->a+b      # From the initial state, move to the a+b state
a+b->_         # From the a+b state, move to the initial state

A deterministic solution is possible by starting the first line with a two-digit number, but this is 14 bytes longer.

The second program can be shortened to 36 bytes

Commodore 64 Basic, 26 bytes
Memory address $0039 (or 57 decimal) contains the low byte of the current line number.
0 PRINT PEEK(57):IF PEEK(57)=1 THEN 1

or
1 PRINT PEEK(57):IF PEEK(57)=1 THEN 1

J, 23 bytes
 echo@0`($:[echo@1)@.*1

Try it online!
False
True

Forked, 15 13 12 bytes
%v
>%|
^-:-&

Try it online!
Forked is a very bad two-dimensional esolang I wrote a while ago. For example, the IP will wrap if you run off the bottom of the screen but the program will terminate if you run off the top.
Control flow begins traveling east at the number inputted, hits % to print it, then hits the v which redirects it south. It enters the fork (for some reason I wanted forks to be entered using three additional bytes apiece) and turns west if 1 was pushed, east if 0. To the east it hits & (terminate). To the west the code goes through a couple redirects that put the code in an infinite loop hitting the print command and nop | forever.
Due to the ridiculous fork-entering rule, I believe this is the shortest possible program in Forked to do this.

J, 15 bytes
(-[echo@[)^:_]0

Try it online! (includes both 0 and 1 cases.)
Abuses "fixed point" feature to choose between iterating once or infinitely.
How they work
0(-[echo@[)^:_]0  Case 0
 (-[echo@[)^:_    Try to find the fixed point of (-[echo@[), which does...
    echo@[          Print left argument once, and then
  -[                Return (left - right)
                  The input (right arg, which counts as 0th iteration) is 0
                  1st iteration is also 0, so ^:_ terminates

1(-[echo@[)^:_]0  Case 1
                  Tries to do the same, but...
                  0th iteration is 0
                  1st iteration is 1 - 0 = 1
                  2nd iteration is 1 - 1 = 0
                  3rd iteration is 1 - 0 = 1... so it oscillates between 0 and 1
                  Therefore, there's no fixed point and ^:_ runs infinitely

Python 3, 38 bytes
0 or print(0)or exit()
while 1:print(1)

Try it online!
1 or print(0)or exit()
while 1:print(1)

Try it online!

If output to STDERR is allowed (30 bytes):
0 or exit('0')
while 1:print(1)

Try it online!

If output as exit code is allowed (28 bytes):
0 or exit(0)
while 1:print(1)

Try it online!

I was not expecting that to be possible

Ruby, 17 bytes
>0?loop{p 1}:p(0)

Try it online!

TI-BASIC, 10 bytes
Repeat not(Ans:Disp Ans:End:"

Add either 0: or 1: to the beginning of the code to get the desired output.
Output is either just 0 or an infinite amount of 1s.
Repeat  loops until its condition is true and ignores the condition for the first loop.
Thus, not(Ans will be 1 if 0: is added and 0 if 1: is added.
An empty string is added to the end of the program to prevent it from printing Done.
Examples:
prgmA:  0:Repeat not(Ans:Disp Ans:End:"
prgmB:  1:Repeat not(Ans:Disp Ans:End:"
prgmA
              0

prgmB
              1
              1
              1
              1
              1
              1
              1

Note: TI-BASIC is a tokenized language.  Character count does not equal byte count.

Triangular, 9 bytes
.%).?/%(<

Try it online!
Formatted, it looks like this, with X being the number:
   X
  . %
 ) . ?
/ % ( <

How it works:

The instruction pointer begins at the top going southeast. It hits the first byte which is the number and pushes that to the stack.
% prints the top of the stack as a number.
? skips the next instruction if the top of the stack is not positive. This effectively ends the program if the first byte was zero.
< redirects the IP left.
( creates a jump point, % prints the top of the stack, ) unconditionally jumps to the most recent jump point.

Bash, 46 bytes
 2>t
f()(echo 1;f)
grep -q '0: c' t&&echo 0||f

False Version
True Version - You may have to stop TIO before you'll see the output of ones.
We redirect the error message for the missing command (0 or 1) to a file named t, and then we use grep to find out which error occured and branch off it.

Octave, 22 bytes
;do disp(ans)until!ans

Try 0 online!
Try 1 online!

If additional ans = on each line is allowed, this could be 17 bytes: ;do ans until!ans

Thue, 40 bytes
!::=1
1+::=_+
_::=~1
+1::=~0
::=
1!+0!

Explanation:
Start with zero:
0!::=1 : String becomes 1!+1
+1::=~0 : String becomes 1!, and zero is printed
No more possible substitutions
Start with one:
1!::=1 : String becomes 1+0!
1+::=1_+ : String becomes 1_+0!
_::=~1 : String becomes 1+0! and one is printed
last two steps repeat at infimum
Try it online

38 bytes. I still feel like it could be shorter though

AWK, 26 bytes
{while(1)print 1}{print 0}

Try it online! (0)
Try it online! (1)
This requires some form of input; an empty string will suffice. Otherwise, I couldn't come up with a valid AWK program that begins with 0 or 1.

As @rootbeersoup said, there is no way to implement this in Awk without having at least an empty input, EOF or line feed, for example. Nevertheless, @rootbeersoup, you may substitute the while loop for for(;;), which has the same infinite effect, using one less byte.

Wren, 53 bytes
That extremely long System.print ... but it doesn't matter.
==0?System.print(0):(0..0/0).each{|i|System.print(1)}

Try it online!
Explanation
If x is the given input bit:
x==0  // If the input bit is 0:
?System.print(0) // Output 0 to the console
:     // Otherwise:
(0..0/0) // Generate range from 0 to 0/0 (which yields nan,
         // a negative infinity constant. No matter how
         // you increment 0, you will never get a negative.)
.each{|i|System.print(1)} // Foreach over this infinite list:
                          // Output the number 1

CJam, 6 bytes
You know, the fact that input isn't taken from STDIN helps the CJam code become shorter! (Martin Ender wrote this before)
{_o}h;

Try it online!
Explanation
1       "The input bit";
 {  }h  "A do ... while loop, taking";
        "the non-popped TOS as condition";
  _     "Duplicate the input bit";
   o    "Output to STDOUT, popping";
      ; "If the bit is 0, we discard";
        "the extra copy on the stack";
        "That is printed implicitly to the";
        "output";

Implicit, 3 bytes
(%)

Try it online!
Explanation:
 X         Push number X (only works at start of program)
(           Create jump point
%          Print top of stack
)            Jump to most recent jump point if top of stack is truthy

Japt, 7 bytes
©@Op1}a

0Test it
0          0 / 1
 ©         AND
  @   }a   return first integer that return a truthy value
           when passed through..
   Op1      return undefined and writes 1 to output

1Try it online

PowerShell, 41 bytes
0-ge1|iex -ov a
for(;"$a"-match"True"){1}0

Try it online!
I didn't think this would be possible in PowerShell, but then I remembered -outvariable, which is the key to making this happen. This is the first time I've ever used it, even in my $DayJob.
Checks whether the input digit is -greater-than-orequal to 1. That will yield either False or True for 0 and 1, respectively. We pipe that into iex (short for Invoke-Expression and similar to eval), which barfs out a spectacular error message because neither False nor True are legitimate PowerShell expressions. Thankfully, stderr is ignored by default.
Then we use the handy-dandy -outvariable to put the output of iex into variable $a. Since the -ov captures all output into an arraylist, both stdout and stderr are captured, so we get the error message into $a. We then for loop on the condition whether $a (cast as a string to collapse the arraylist) regex -matches "True". If it does, we output 1 continuously; otherwise we simply exit the for loop without printing anything, output 0, and terminate.

? Try it online!

@mazzy Haha, now I feel silly. Go ahead and post that as a separate answer, since it's significantly different than this one.

I thought I didn't understand something in the task. ok.

Thanks for -outvariable.

Befunge-93, 9 bytes
0>:#1.:_@

or:
1>:#1.:_@

Try it with 0
Try it with 1

Similar to the ><> answer, you don't have to create a loop when you can just use wrapping behaviour. You can do something like this for 7 bytes, though I think there could be a 6 byter out there

Cascade, 8 bytes
0/
?@
#|

Try 0 online! Try 1 online!
Hardcoded input makes this a lot more trivial, since we don't need to store the value of the input or anything.

Zsh, 23 20 bytes
=
<<<${${1+1}:-0}
$0

Try it online!
Try it online!
Normally, the parameter $0 holds the program/function name. Running 0= sets the parameter to the empty string, which causes the recursion to break. Without any arguments, $1 is unset, so the ${:-fallback} 0 is used instead.
Otherwise, 1= sets $1 to the empty string, which causes ${1+1} to expand to 1.

If the program 1 is not in the user's path or another function, then for 16 bytes:
=1
<<<${1:-0}
$0

Try it online!
Same principle, but with the parameter in question set to the value 1 instead of empty.

GolfScript, 7 bytes
{..}do;

It sucks that you need to infinitely print 1, and print exactly one 0 otherwise I could take away a few characters!
If the restriction was "term on 0, hang on 1", then {.}do is enough. The extra point is for infinite 1s, and the semicolon is or exactly one zero (otherwise there'd be 2 with this solution).
This takes the header, then duplicates it twice. Pop the top, if it's 0, stop, pop, done. One 0 left. If it's a 1, recur the inside, duplicating 1s until your computer burns out of memory.
EDIT: Note, the Wikipedia article has ~{..p}do; as its solution. This assumes you use the "input" area, whereas SE has slightly more flexible input rules to allow header starts.
Try it online!

Does this actually output the 1s or just duplicate them in memory?

When programs finish, GS prints the stack.

But the program isn't going to finish, by definition

When the program crashes, it still prints the stack (explosively).

Programs are based on the assumption that they have infinite memory and time. If your program relies on halting in order to output, then it doesn't obey the run forever restriction, and vice versa

I disagree with this, since there are several languages that only actually engage in their "output" once they finish the program. Processing, for example, if you lock it in a while loop, will never output anything until the program eventually crashes, since it holds all output prints until either the draw() call is done or the program crashes.  Since this problem didn't specify we're doing a theory-question that we "don't actually have the ability to calculate" like some complexity problems do, I'd say there isn't an implicit infinite-memory quota.

I don't see any Processing answer on this question. Also, GolfScript has a way to explicitly output. I'm not sure if it is written down on CCCG, but submissions may assume infinite resources at any time unless explicitly restricted from doing so. Regardless, if you're assuming it only outputs on termination, then you can't say that it both outputs and runs forever.

This shows my output is valid.

This is not a function, this is a full program

Golfscript executes programs as insular functions. Arguably, since it needs to take input on the stack and by itself is non-functional, it's closer to the definition of "function" than "full program". Takes in a specific input and presents a specific output. Golfscript treats programs and functions pretty much identically.

Golfscript has explicit function constructs, blocks, so no, you can't count full programs as functions unless you surround them in {}. That doesn't really matter, since this challenge forces hard-coded input, and that rule still doesn't apply since the program still doesn't terminate. I would suggest opening up a meta question on whether non-terminating programs can output by assuming termination

Golfscript full programs use the same run-configuration as a blocked function would. Any program wrapped in {}~ would operate identically because Golfscript uses that format for compiling and running. The entire code is dumped onto the stack as a function then run as one, which runs the program. As for non-termination can output by assuming termination, I agree - I'll make a meta post on that because several solutions here only work when memory floods and the entire output is printed at once. Especially anything stuck in while() loops.

Ok, but no IO rule allows for full programs to have hard coded input. And you can apply that secons statement to any language with a function, that a series of statements works identically to a function with those statments immediately executed. I'm probably also going to end up making a meta post for this function vs program thing

dc, 11 10 bytes
[p1=m]dsmx

Try it online!
Try with 0.
Try with 1.
Thanks to user41805 for eliminating 1 byte.

It seems the program works without d, while producing infinite stack emptys to STDERR.

@user41805 Thanks, that's interesting.  Conditionals in dc are supposed to pop two items off the stack and compare them.  But it seems that if the stack doesn't have two items on it, nothing is popped (even if there is one item), and the test is evaluated as if the two items being compared were equal (so that =, !< and !> are considered true, while !=, <, and > are considered false.  (At least that's true for one version of dc that I tested, but there are different versions floating around, and I wouldn't assume that they all behave in the same way in this regard.)

I did not understand why it worked as it did, thanks for the explanation, it is indeed interesting. Perhaps it's worth adding to the dc tips

1+, 19 15 bytes
11+/1<"#:[#":1#

A fairly trivial ungolfed solution.
Try it 0nline!
Try it on1ine!
Explanation:
Firstly, in this language, 1 pushes 1 and 0 is a NOP.
The program consists of two parts: 11+/1< which converts the internal input into the corresponding number and 1##":"1+1<1+# which is basically the Truth Machine.
Another nice feature of 1+ is the "rotate" operation / which leave the stack unmodified if there's only one number in the stack and swaps the two numbers if there's two.
11+                  [Pushes 2]
   /                 [Rotate the stack]
    1<               [Converts 2 to 0 and leave 1 as-is]
      "#:[#":1#      [See https://codegolf.stackexchange.com/a/208961/87986]

Pxem, filename only: 11 bytes.
0.z1.o.a0.o

0Try it online!
1Try it online!
If you are not familiar with Pxem: .z ... .a is "while stack size<2 or pop!=pop; do something; done" (sorry I misdescript the function).
Also, pushing literates are done backwards; if program begins with 10.z, then 48 is pushed first, then 49 next. Then the branching is done.

Vyxal, 4 bytes
[{1₴

0Try it Online!
1Try it Online!
[       If the top of the stack is truthy (i.e. 1):
 {      Repeat forever:
  1₴    Print 1

sed, 9 bytes
1c0
=;G;D

Try it online!
(sed requires at the minimum an empty line as input to run.)
sed cycles the input line-by-line. The first line is read into the pattern space first, on which the program is run, at the end of which the resulting pattern space will be implicitly output allowing the next cycle to commence with the next line. Commands can be line-addressed, meaning that they will run only on the specified lines. For example, 11c0 will change the 11th line of input to 0, whilst 1c0 changes the 1st line of input to 0.
If 0 is inserted as the first character, the first line becomes 01c0, i.e. the first line is changed to 0, which ends up printed. A new cycle is started immediately afterwards, and since there are no more lines, the program exits.
If 1 is inserted as the first character, the first line becomes 11c0, i.e. change the 11th line to 0. This does not happen, because there is only 1 line of input, the empty line. The program proceeds to = which prints the line number, i.e. 1. G appends a newline followed by the hold space (starts with being the empty line) to the pattern space, which now contains just a newline. D deletes the first line of the pattern space until and including the newline, and restarts the cycle with the resulting pattern space without consuming the next line of input. This creates the infinite loop, and since the line number stays at 1, 1 + newline is printed out forever. source

Stax, 4 bytes
WQ|c

Run and debug it
prepend with 0 or 1.  Bonus: also works as a regular truth machine with input

Perl 5, 23 bytes
?$_=1:say 0;say while$_

True
False

MAWP, 13 bytes
!~M1A?:?.[!:]

Explanation:
               Stack starts with 1.
!              Duplicates 0 or 1  [1,0,0] or [1,1,1]
 ~             Reverses the stack [0,0,1] or [1,1,1]
  M            Adds top 2 elements[0,1]   or [1,2]
   1A          Subtract 1 from top[0,0]   or [1,1]
     ?:        If top of stack is 0, print it, otherwise do nothing
       ?.      If top of stack is 0, end program
         [!:]  Infinite loop which duplicates top of stack and prints it

Try it!

05AB1E, 3 bytes
i[?

0Try it online!
1Try it online!
i[?  # full program
i    # if...
     # (implicit) hardcoded input...
i    # is 1...
 [   # forever...
  ?  # output...
     # (implicit) hardcoded input
     # implicit output