cp's OEIS Frontend

Also called the Bell triangle or the Peirce triangle.

a(n,k) is the number of equivalence relations on {0, ..., n} such that k is not equivalent to n, k+1 is not equivalent to n, ..., n-1 is not equivalent to n. - Don Knuth, Sep 21 2002 [Comment revised by Thijs van Ommen (thijsvanommen(AT)gmail.com), Jul 13 2008]

Named after the New Zealand mathematician Alexander Craig Aitken (1895-1967). - Amiram Eldar, Jun 11 2021

a(n,k) is k-th difference of Bell numbers, with a(n,1) = A000110(n) for n>0, a(n,k) = a(n,k-1) - a(n-1, k-1), k<=n, with diagonal (k=n) also equal to Bell numbers (n>=0). - Richard R. Forberg, Jul 13 2013

From Don Knuth, Jan 29 2018: (Start)

If the offset here is changed from 0 to 1, then we can say:

a(n,k) is the number of equivalence classes of [n] in which 1 not equiv to 2, ..., 1 not equiv to k.

In Volume 4A, page 418, I pointed out that a(n,k) is the number of set partitions in which k is the smallest of its block.

And in exercise 7.2.1.5--33, I pointed out that a(n,k) is the number of equivalence relations in which 1 not equiv to 2, 2 not equiv to 3, ..., k-1 not equiv to k. (End)

The triangle algorithm, as understood here, is a transformation that maps a sequence of integers (a(n) : n >= 0) to a polynomial sequence. A polynomial sequence is a sequence of polynomials (P(n,x) : n >= 0) with degree(P(n, x)) = n for all n >= 0.

The polynomials P(n, x) are recursively defined by P(n, x) = p(n, 0, x), where the initial sequence is p(0, m, x) = a(m), and for n > 0 is given by

p(n, m, x) = (m + 1)*p(n - 1, m + 1, x) - (m + 1 - x)*p(n - 1, m, x).

Here we identify the polynomial sequence with the infinite lower triangular array of its coefficients, T(n, k) = [x^k] P(n, x). We call the mapping (a(n) : n >= 0) -> (T(n, k) : 0 <= k <= n) the 'triangle algorithm', following the lead of Kawasaki and Ohno.

Evaluating P(n, x) at different values of x gives rise to a multitude of other sequences; in particular, the transformation a(n) -> b(n) = P(n, 1) will be called the Akiyama-Tanigawa transform of a.

The triangle algorithm was studied by Akiyama and Tanigawa, Chen, Imatomi, Arakawa and Kaneko, Kawasaki and Ohno, and others, at first in connection with the Bernoulli and Poly-Bernoulli numbers.

.

The paradigmatic examples are:

a(n) = 1 -> x^n, the standard base of polynomials, A023531.

a(n) = n + 1 -> binomial(n, k), Pascal triangle, A007318.

a(n) = n + 1 -> P(n, 1) powers of 2, A000079.

a(n) = n + 1 -> P(n, 0) the all 1's sequence A000012.

a(n) = 2^n -> [x^k] P(n, x), A154921.

a(n) = 2^n -> P(n, 0) Fubini numbers, A000670.

a(n) = 2^n -> P(n, 1) ordered set partitions of subsets of [n], A000629.

a(n) = 2^n -> P(n,-1) osp. of [n] with even number of blocks, A052841.

a(n) = 1 / (n + 1) -> [x^k] B(n, x), Bernoulli polynomials, A196838/A196839.

a(n) = 1 / (n + 1) -> B(n, 1), the Bernoulli numbers, A164555/A027642.

a(n) = Chen(n) -> skp(n, x), Swiss-Knife polynomials, A153641.

a(n) = Chen(n) -> P(n, 0), 2^n*Euler(n, 1/2) = Euler(n), A122045.

a(n) = Chen(n) -> P(n, 1), 2^n*Euler(n, 1), A155585.

a(n) = (-1)^n/n! -> [x^k] P(n, x) this "Bell" triangle.

a(n) = (-1)^n/n! -> (-1)^n*P(n, 1) = Bell(n), A000110.

a(n) = (-1)^n/n! -> (-1)^n*P(n,-1) = 2-Bell(n), A005493.

a(n) = 1/n! -> (-1)^n*P(n, 1) = complementary Bell(n), A000587.

a(n) = 1/n! -> (-1)^n*P(n,-1) = complementary 2-Bell(n), A074051.

(For Chen's sequence see A363524.)

.

The present sequence deals with the case of the Bell numbers. In contrast to Aitken's array A011971 and its variants A123346 and A011972, the Bell numbers do not appear as a column of the triangle but as row sums (times (-1)^n), i.e., as values of the associated polynomials at x = 1. Comparing this with a similar situation with the Bernoulli numbers/polynomials, our triangle could be viewed as a more organic generalization of the Bell numbers. Indeed, the names 'Bell triangle' and 'Bell polynomials' would be justified here; but these are already assigned to other concepts.