The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 T. D. Noe and Chai Wah Wu, Rows n = 0..200 of triangle, flattened (rows n = 0..50 from T. D. Noe) Alexander Craig Aitken, A problem in combinations, Edinburgh Mathematical Notes, Vol. 28 (1933), pp. xviii-xxiii. 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] Antonio Bernini, Mathilde Bouvel and Luca Ferrari, Some statistics on permutations avoiding generalized patterns, PU.M.A. Vol. 18, No. 3-4 (2007), pp. 223-237 (see array p. 228). Clarence H. Best, Jerry Griggs, and Ira Gessel, Partitions of finite sets, Advanced Problem 6151, The American Mathematical Monthly, Vol. 86, No. 1 (Jan., 1979), pp. 64-65. Robert W. Donley, Jr., Binomial arrays and generalized Vandermonde identities, arXiv:1905.01525 [math.CO], 2019. Martin Cohn, Shimon Even, Karl Menger, Jr. and Philip K. Hooper, On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly, Vol. 69, No. 8 (1962), pp. 782-785. MR1531841. Martin Cohn, Shimon Even, Karl Menger, Jr. and Philip K. Hooper, On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly Vol. 69, No. 8 (1962), pp. 782-785. MR1531841. [Annotated scanned copy] Dominique Dumont, Matrices d'Euler-Seidel, Sem. Loth. Comb. B05c (1981) 59-78. Richard K. Guy, Letters to N. J. A. Sloane, June-August 1968. Nick Hobson, Python program for this sequence. Don Knuth, Email to N. J. A. Sloane, Jan 29 2018. Charles Sanders Peirce, Assorted Papers. Charles Sanders Peirce, Collected Papers. Charles Sanders Peirce, Published Works. 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. Todd Tichenor, Bounds on graph compositions and the connection to the Bell triangle, Discr. Math., Vol. 339, No. 4 (2016), pp. 1419-1423. Eric Weisstein's World of Mathematics, Bell Triangle. Denys Wuilquin, Letters to N. J. A. Sloane, August 1984. 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] -- Reinhard Zumkeller, Dec 09 2012 (Python) # requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs. from itertools import accumulate A011971 = blist = [1] for _ in range(10**2): b = blist[-1] blist = list(accumulate([b]+blist)) A011971 += blist # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 19 2014 (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 Borders give Bell numbers A000110. Diagonals give A005493, A011965, A011966, etc., A011968, A011969. Cf. A046934, A011972 (duplicates removed). Main diagonal is in A094577. Mirror image is in A123346. See also A095149, A106436, A108041, A108042, A108043. Sequence in context: A028364 A239482 A280470 * A060048 A110699 A035537 Adjacent sequences: A011968 A011969 A011970 * A011972 A011973 A011974 KEYWORD tabl,nonn,easy,nice AUTHOR N. J. A. Sloane, J. H. Conway and R. K. Guy EXTENSIONS Peirce reference from Jon Awbrey, Mar 11 2002 Reference to my paper from Jeffrey Shallit, Jan 23 2015 Moved a comment to A056857 where it belonged. - N. J. A. Sloane, May 02 2015. STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 25 11:06 EDT 2024. Contains 374588 sequences. (Running on oeis4.)