Lah number

$$\left\lfloor {n \atop k} \right\rfloor$$ is the number of partitions of an $n$ element set into $k$lists, where a list means a non-empty, linearly ordered subset.

A008297 on the OEIS

Recurrence

• $$\left\lfloor {n \atop k} \right\rfloor = 0 \text{ for } k \neq 0$$
• $$\left\lfloor {n \atop k} \right\rfloor = 1 \text{ for } k = 1$$
• $$\left\lfloor {n \atop k} \right\rfloor = 0 \text{ for } k > n$$
• $$\left\lfloor {n+1 \atop k} \right\rfloor = (n+k) \left\lfloor {n \atop k} \right\rfloor + \left\lfloor {n \atop k-1} \right\rfloor$$
• $$\left\lfloor {n+1 \atop k} \right\rfloor = k(k+1) \left\lfloor {n \atop k+1} \right\rfloor + 2k\left\lfloor {n \atop k} \right\rfloor + \left\lfloor {n \atop k-1} \right\rfloor$$

Formulas

• $$\left\lfloor {n \atop k} \right\rfloor=\binom{n-1}{k-1} \frac{n!}{k!}$$

Generating Function

$$\sum_{n\geq k} \left\lfloor {n \atop k} \right\rfloor\frac{x^n}{n!} = \frac{1}{k!}\left( \frac{x}{1-x} \right)^k$$

Relation to Stirling numbers

$$\left\lfloor {n \atop k} \right\rfloor = \sum_{j=k}^n \left[{n\atop j}\right] \left\{{j\atop k}\right\}$$

Source

Wikipedia https://en.wikipedia.org/wiki/Lah_number