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

 

Logo
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

%I #125 Mar 26 2022 15:18:24

%S 1,1,2,2,3,5,5,7,10,15,15,20,27,37,52,52,67,87,114,151,203,203,255,

%T 322,409,523,674,877,877,1080,1335,1657,2066,2589,3263,4140,4140,5017,

%U 6097,7432,9089,11155,13744,17007,21147,21147,25287,30304,36401,43833,52922,64077,77821,94828,115975

%N 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).

%C Also called the Bell triangle or the Peirce triangle.

%C 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]

%C Named after the New Zealand mathematician Alexander Craig Aitken (1895-1967). - _Amiram Eldar_, Jun 11 2021

%D Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 205.

%D Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 212.

%D Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 418).

%D 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).

%D 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.

%H T. D. Noe and Chai Wah Wu, <a href="/A011971/b011971.txt">Rows n = 0..200 of triangle, flattened</a> (rows n = 0..50 from T. D. Noe)

%H Alexander Craig Aitken, <a href="https://doi.org/10.1017/S1757748900002334">A problem in combinations</a>, Edinburgh Mathematical Notes, Vol. 28 (1933), pp. xviii-xxiii.

%H H. W. Becker, <a href="http://www.jstor.org/stable/3029709">Rooks and rhymes</a>, Math. Mag., Vol. 22, No. 1 (1948/49), pp. 23-26. See Table IV.

%H H. W. Becker, <a href="/A056857/a056857.pdf">Rooks and rhymes</a>, Math. Mag., Vol. 22, No. 1 (1948/49), pp. 23-26. [Annotated scanned copy]

%H Antonio Bernini, Mathilde Bouvel and Luca Ferrari, <a href="http://puma.dimai.unifi.it/18_3_4/BerniniBouvelFerrari.pdf">Some statistics on permutations avoiding generalized patterns</a>, PU.M.A. Vol. 18, No. 3-4 (2007), pp. 223-237 (see array p. 228).

%H Robert W. Donley, Jr., <a href="https://arxiv.org/abs/1905.01525">Binomial arrays and generalized Vandermonde identities</a>, arXiv:1905.01525 [math.CO], 2019.

%H Martin Cohn, Shimon Even, Karl Menger, Jr. and Philip K. Hooper, <a href="http://www.jstor.org/stable/2310780">On the Number of Partitionings of a Set of n Distinct Objects</a>, Amer. Math. Monthly, Vol. 69, No. 8 (1962), pp. 782-785. MR1531841.

%H Martin Cohn, Shimon Even, Karl Menger, Jr. and Philip K. Hooper, <a href="/A011965/a011965.pdf">On the Number of Partitionings of a Set of n Distinct Objects</a>, Amer. Math. Monthly Vol. 69, No. 8 (1962), pp. 782-785. MR1531841. [Annotated scanned copy]

%H Dominique Dumont, <a href="http://www.mat.univie.ac.at/~slc/opapers/s05dumont.html">Matrices d'Euler-Seidel</a>, Sem. Loth. Comb. B05c (1981) 59-78.

%H Richard K. Guy, <a href="/A002186/a002186.pdf">Letters to N. J. A. Sloane, June-August 1968</a>.

%H Nick Hobson, <a href="/A011971/a011971.py.txt">Python program for this sequence</a>.

%H Don Knuth, <a href="/A040027/a040027.txt">Email to N. J. A. Sloane</a>, Jan 29 2018.

%H Charles Sanders Peirce, <a href="http://www.cspeirce.com/menu/library/bycsp/bycsp.htm">Assorted Papers</a>.

%H Charles Sanders Peirce, <a href="http://www.nlx.com/authors/123">Collected Papers</a>.

%H Charles Sanders Peirce, <a href="http://www.pragmaticism.net/works/">Published Works</a>.

%H Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/shallit-bell-triangle.pdf">A triangle for the Bell numbers</a>, in V. E. Hoggatt, Jr. and M. Bicknell-Johnson, A Collection of Manuscripts Related to the Fibonacci Sequence, 1980, pp. 69-71.

%H Todd Tichenor, <a href="http://dx.doi.org/10.1016/j.disc.2015.12.013">Bounds on graph compositions and the connection to the Bell triangle</a>, Discr. Math., Vol. 339, No. 4 (2016), pp. 1419-1423.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BellTriangle.html">Bell Triangle</a>.

%H Denys Wuilquin, <a href="/A000587/a000587_1.pdf">Letters to N. J. A. Sloane, August 1984</a>.

%F 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]

%F a(n,k) = Sum_{i=0..k} binomial(k,i)*Bell(n-k+i). - _Vladeta Jovovic_, Oct 15 2006

%e Triangle begins:

%e 00: 1

%e 01: 1 2

%e 02: 2 3 5

%e 03: 5 7 10 15

%e 04: 15 20 27 37 52

%e 05: 52 67 87 114 151 203

%e 06: 203 255 322 409 523 674 877

%e 07: 877 1080 1335 1657 2066 2589 3263 4140

%e 08: 4140 5017 6097 7432 9089 11155 13744 17007 21147

%e 09: 21147 25287 30304 36401 43833 52922 64077 77821 94828 115975

%e 10: 115975 137122 162409 192713 229114 272947 325869 389946 467767 562595 678570

%e ...

%p 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;

%p for n from 0 to 12 do lprint([ seq(A011971(n,k),k=0..n) ]); od:

%p # Compare the analogue algorithm for the Catalan numbers in A030237.

%p BellTriangle := proc(len) local P, T, n; P := [1]; T := [[1]];

%p for n from 1 to len - 1 do P := ListTools:-PartialSums([P[-1], op(P)]);

%p T := [op(T), P] od; T end:

%p BellTriangle(6); ListTools:-Flatten(%); # _Peter Luschny_, Mar 26 2022

%t 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 *)

%t 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_ *)

%o (Haskell)

%o a011971 n k = a011971_tabl !! n !! k

%o a011971_row n = a011971_tabl !! n

%o a011971_tabl = iterate (\row -> scanl (+) (last row) row) [1]

%o -- _Reinhard Zumkeller_, Dec 09 2012

%o (Python)

%o # requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.

%o from itertools import accumulate

%o A011971 = blist = [1]

%o for _ in range(10**2):

%o b = blist[-1]

%o blist = list(accumulate([b]+blist))

%o A011971 += blist # _Chai Wah Wu_, Sep 02 2014, updated _Chai Wah Wu_, Sep 19 2014

%o (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

%Y Borders give Bell numbers A000110. Diagonals give A005493, A011965, A011966, etc., A011968, A011969. Cf. A046934, A011972 (duplicates removed).

%Y Main diagonal is in A094577. Mirror image is in A123346.

%Y See also A095149, A106436, A108041, A108042, A108043.

%K tabl,nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_, _J. H. Conway_ and _R. K. Guy_

%E Peirce reference from _Jon Awbrey_, Mar 11 2002

%E Reference to my paper from _Jeffrey Shallit_, Jan 23 2015

%E Moved a comment to A056857 where it belonged. - _N. J. A. Sloane_, May 02 2015

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 07:27 EDT 2024. Contains 371265 sequences. (Running on oeis4.)