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

Let P(n,k) be the number of set partitions of {1,2,..,n} in which k is the smallest of its block. These numbers were introduced by C. S. Peirce (see reference, page 48). If this triangle is displayed as in A123346 (or A011971) then a(n) = A011971(2n, n) are the central Pierce numbers. - Peter Luschny, Jan 18 2011

Named after the American philosopher, logician, mathematician and scientist Charles Sanders Peirce (1839-1914). - Amiram Eldar, Jun 11 2021

This is another version of Moser's version (A046936) of Aitken's array (A011971).

Although offset 0 is better for A011971 and A046936, for this version offset 1 is more appropriate.

Comments from Don Knuth, Jan 29 2018 (Start):

a(n,k) is the number of set partitions (i.e. equivalence classes) in which (i) 1 is not equivalent to 2, ..., nor k; and (ii) the last part, when parts are ordered by their smallest element, has size 1; (iii) that last part isn't simply "1". (Equivalently, n>1.)

It's not difficult to prove this characterization of a(k,n). For example, if we know that there are 22 partitions of {1,2,3,4,5} with 1 inequivalent to 2, and 6 partitions of {1,2,3,4} with

1 inequivalent to 2, then there are 6 partitions of {1,2,3,4,5} with 1 inequivalent to 2 and 1 equivalent to 3. Hence there are 16 with 1 equivalent to neither 2 nor 3.

The same property, but leaving out conditions (ii) and (iii), characterizes Pierce's triangular array A123346. (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.