|
|
A011971
|
|
Aitken's array: triangle of numbers {a(n,k), n >= 0, 0 <= k <= n} read by rows, defined by a(0,0)=1, a(n,0) = a(n-1,n-1), a(n,k) = a(n,k-1) + a(n-1,k-1).
|
|
59
|
|
|
1, 1, 2, 2, 3, 5, 5, 7, 10, 15, 15, 20, 27, 37, 52, 52, 67, 87, 114, 151, 203, 203, 255, 322, 409, 523, 674, 877, 877, 1080, 1335, 1657, 2066, 2589, 3263, 4140, 4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147, 21147, 25287, 30304, 36401, 43833, 52922, 64077, 77821, 94828, 115975
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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
|
|
REFERENCES
|
Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 205.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 212.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 418).
Charles Sanders Peirce, On the Algebra of Logic, American Journal of Mathematics, Vol. 3, pages 15-57, 1880. Reprinted in Collected Papers (1935-1958) and in Writings of Charles S. Peirce: A Chronological Edition (Indiana University Press, Bloomington, IN, 1986).
Jeffrey Shallit, A triangle for the Bell numbers, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.
|
|
LINKS
|
H. W. Becker, Rooks and rhymes, Math. Mag., Vol. 22, No. 1 (1948/49), pp. 23-26. See Table IV.
H. W. Becker, Rooks and rhymes, Math. Mag., Vol. 22, No. 1 (1948/49), pp. 23-26. [Annotated scanned copy]
Jeffrey Shallit, A triangle for the Bell numbers, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.
|
|
FORMULA
|
Double-exponential generating function: Sum_{n, k} a(n-k, k) x^n y^k / n! k! = exp(e^{x+y}-1+x). - Don Knuth, Sep 21 2002 [U coordinates, reversed]
a(n,k) = Sum_{i=0..k} binomial(k,i)*Bell(n-k+i). - Vladeta Jovovic, Oct 15 2006
|
|
EXAMPLE
|
Triangle begins:
00: 1
01: 1 2
02: 2 3 5
03: 5 7 10 15
04: 15 20 27 37 52
05: 52 67 87 114 151 203
06: 203 255 322 409 523 674 877
07: 877 1080 1335 1657 2066 2589 3263 4140
08: 4140 5017 6097 7432 9089 11155 13744 17007 21147
09: 21147 25287 30304 36401 43833 52922 64077 77821 94828 115975
10: 115975 137122 162409 192713 229114 272947 325869 389946 467767 562595 678570
...
|
|
MAPLE
|
A011971 := proc(n, k) option remember; if n=0 and k=0 then 1 elif k=0 then A011971(n-1, n-1) else A011971(n, k-1)+A011971(n-1, k-1); fi: end;
for n from 0 to 12 do lprint([ seq(A011971(n, k), k=0..n) ]); od:
# Compare the analogue algorithm for the Catalan numbers in A030237.
BellTriangle := proc(len) local P, T, n; P := [1]; T := [[1]];
for n from 1 to len - 1 do P := ListTools:-PartialSums([P[-1], op(P)]);
T := [op(T), P] od; T end:
BellTriangle(6); ListTools:-Flatten(%); # Peter Luschny, Mar 26 2022
|
|
MATHEMATICA
|
a[0, 0] = 1; a[n_, 0] := a[n, 0] = a[n-1, n-1]; a[n_, k_] := a[n, k] = a[n, k-1] + a[n-1, k-1]; Flatten[ Table[ a[n, k], {n, 0, 9}, {k, 0, n}]] (* Robert G. Wilson v, Mar 27 2004 *)
Flatten[Table[Sum[Binomial[k, i]*BellB[n-k+i], {i, 0, k}], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, May 24 2016, after Vladeta Jovovic *)
|
|
PROG
|
(Haskell)
a011971 n k = a011971_tabl !! n !! k
a011971_row n = a011971_tabl !! n
a011971_tabl = iterate (\row -> scanl (+) (last row) row) [1]
(Python)
# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
for _ in range(10**2):
b = blist[-1]
blist = list(accumulate([b]+blist))
(GAP) T:=Flat(List([0..9], n->List([0..n], k->Sum([0..k], i->Binomial(k, i)*Bell(n-k+i))))); # Muniru A Asiru, Oct 26 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|