login
This site is supported by donations 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). 46
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also called the Bell triangle or the Peirce triangle.

Let P be the lower-triangular Pascal-matrix, Then this is exp(P) / exp(1). - Gottfried Helms, Mar 30 2007.

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]

REFERENCES

A. C. Aitken, A problem on combinations, Edinburgh Math. Notes 28 (1933), 18-33.

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 205.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 212.

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

LINKS

Chai Wah Wu, Rows n=0..200 of triangle, flattened Rows n=0..50 from T. D. Noe.

Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K.; Mathematical Notes: On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841 - From N. J. A. Sloane, Jul 31 2012

D. Dumont, Matrices d'Euler-Seidel, Sem. Loth. Comb. B05c (1981) 59-78.

Nick Hobson, Python program for this sequence

C. S. Peirce, Assorted Papers

C. S. Peirce, Collected Papers

C. S. Peirce, Published Works

Eric Weisstein's World of Mathematics, Bell Triangle

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:

MATHEMATICA

a[0, 0] = 1; a[n_, 0] := a[n - 1, n - 1]; 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)

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

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: A008507 A028364 A239482 * 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

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 22 08:28 EDT 2014. Contains 248388 sequences.