A046934 -id:A046934 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane, J. H. Conway and R. K. Guy

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

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

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.

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.

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.

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

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

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

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

# 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

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

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.

A032347 Inverse binomial transform of A032346.

Original entry on oeis.org

1, 0, 1, 2, 6, 21, 82, 354, 1671, 8536, 46814, 273907, 1700828, 11158746, 77057021, 558234902, 4230337018, 33448622893, 275322101318, 2354401779494, 20878592918183, 191682453823420, 1819147694792802

Offset: 0

Joe K. Crump (joecr(AT)carolina.rr.com)

Branko Dragovich, On Summation of p-Adic Series, arXiv:1702.02569 [math.NT], 2017.
N. J. A. Sloane, Transforms

Cf. A032346, A046934.

a[0] = 1; a[1] = 0; a[n_] := a[n] = 1 + Sum[Binomial[n-1, j]*a[j], {j, 2, n-1}]; Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Oct 08 2013, after Jon Perry *)
nmax = 20; Assuming[x > 0, CoefficientList[Series[E^(E^x) * (1/E + ExpIntegralEi[-1] - ExpIntegralEi[-E^x]), {x, 0, nmax}], x] ] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 10 2020 *)

{a(n)=local(A=1+x*O(x^n)); for(i=0, n, A=1 - x * (1 - subst(A, x, x/(1-x)) / (1 - x))); polcoeff(A, n)}
for(n=0, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Jul 10 2020

E.g.f. satisfies A' = exp(x) A - 1.
Recurrence: a(1)=0, a(2)=1, for n > 2, a(n) = 1 + Sum_{j=2..n-1} binomial(n-1, j)*a(j). - Jon Perry, Apr 26 2005
G.f. A(x) satisfies: A(x) = 1 - x * (1 - A(x/(1 - x)) / (1 - x)). - Ilya Gutkovskiy, Jul 10 2020

A032346 Essentially shifts 1 place right under inverse binomial transform.

Original entry on oeis.org

1, 1, 2, 6, 21, 82, 354, 1671, 8536, 46814, 273907, 1700828, 11158746, 77057021, 558234902, 4230337018, 33448622893, 275322101318, 2354401779494, 20878592918183, 191682453823420, 1819147694792802, 17822073621801123

Offset: 0

Joe K. Crump (joecr(AT)carolina.rr.com)

With leading 0 and offset 1, number of permutations beginning with 21 and avoiding 3-12. - Ralf Stephan, Apr 25 2004

N. J. A. Sloane, Transforms
Sergey Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. 48 (2003), Article B48e.
Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298(1-3) (2005), 212-229.
Sergey Kitaev and Toufik Mansour, Simultaneous avoidance of generalized patterns, arXiv:math/0205182 [math.CO], 2002.

Cf. A032347, A046934.

max = 23; f[x_] = x + Exp[Exp[x]]*Integrate[Exp[-Exp[t]]*Sum[t^n/n!, {n, 1, max}], {t, 0, x}]; Rest[ CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]!] (* Jean-François Alcover, Aug 07 2012, after Ralf Stephan *)

With offset 1, e.g.f.: x + exp(exp(x)) * int[0..x, exp(-exp(t))*sum(n>=1, t^n/n!) dt]. - Ralf Stephan, Apr 25 2004

Last digit of a(22) corrected by Jean-François Alcover, Aug 07 2012

A123346 Mirror image of the Bell triangle A011971, which is also called the Pierce triangle or Aitken's array.

Original entry on oeis.org

1, 2, 1, 5, 3, 2, 15, 10, 7, 5, 52, 37, 27, 20, 15, 203, 151, 114, 87, 67, 52, 877, 674, 523, 409, 322, 255, 203, 4140, 3263, 2589, 2066, 1657, 1335, 1080, 877, 21147, 17007, 13744, 11155, 9089, 7432, 6097, 5017, 4140, 115975, 94828, 77821, 64077, 52922, 43833, 36401, 30304, 25287, 21147

Offset: 0

N. J. A. Sloane, Oct 14 2006

a(n,k) is k-th difference of Bell numbers, with a(n,1) = A000110(n) for  n>0, a(n,k) = a(n,k-1) - a(n-1, k-1), k<=n, with diagonal (k=n) also equal to Bell numbers (n>=0). - Richard R. Forberg, Jul 13 2013
From Don Knuth, Jan 29 2018: (Start)
If the offset here is changed from 0 to 1, then we can say:
a(n,k) is the number of equivalence classes of [n] in which 1 not equiv to 2, ..., 1 not equiv to k.
In Volume 4A, page 418, I pointed out that a(n,k) is the number of set partitions in which k is the smallest of its block.
And in exercise 7.2.1.5--33, I pointed out that a(n,k) is the number of equivalence relations in which 1 not equiv to 2, 2 not equiv to 3, ..., k-1 not equiv to k. (End)

			Triangle begins:
    1
    2   1
    5   3   2
   15  10   7  5
   52  37  27 20 15
  203 151 114 87 67 52
  ...

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

Reinhard Zumkeller, Rows n = 0..100 of triangle, flattened
A. Dil, Veli Kurt, Investigating Geometric and Exponential Polynomials with Euler-Seidel Matrices, J. Int. Seq. 14 (2011) # 11.4.6
Don Knuth, Email to N. J. A. Sloane, Jan 29 2018
Eric Weisstein's World of Mathematics, Bell Triangle.

Cf. A011971. Borders give Bell numbers A000110. Diagonals give A005493, A011965, A011966, A011968, A011969, A046934, A011972, A094577, A095149, A106436, A108041, A108042, A108043.

a123346 n k = a123346_tabl !! n !! k
a123346_row n = a123346_tabl !! n
a123346_tabl = map reverse a011971_tabl
-- Reinhard Zumkeller, Dec 09 2012

a[n_, k_] := Sum[Binomial[n - k, i - k] BellB[i], {i, k, n}];
Table[a[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Aug 03 2018 *)

# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A123346_list = blist = [1]
for _ in range(2*10**2):
    b = blist[-1]
    blist = list(accumulate([b]+blist))
    A123346_list += reversed(blist)
# Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

a(n,k) = Sum_{i=k..n} binomial(n-k,i-k)*Bell(i). - Vladeta Jovovic, Oct 14 2006

More terms from Alexander Adamchuk and Vladeta Jovovic, Oct 14 2006

A352685 Array of Aitken-Bell triangles of order m (read by rows) read by ascending antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 2, 1, 1, 4, 4, 3, 3, 2, 1, 5, 5, 4, 5, 5, 2, 1, 6, 6, 5, 7, 8, 5, 3, 1, 7, 7, 6, 9, 11, 8, 7, 4, 1, 8, 8, 7, 11, 14, 11, 11, 10, 6, 1, 9, 9, 8, 13, 17, 14, 15, 16, 15, 6, 1, 10, 10, 9, 15, 20, 17, 19, 22, 24, 15, 8, 1, 11, 11, 10, 17, 23, 20, 23, 28, 33, 24, 20, 11, 1, 12, 12, 11, 19, 26, 23, 27, 34, 42, 33, 32, 27, 15

Offset: 0

Peter Luschny, Mar 29 2022

An Aitken-Bell triangle of order m is defined by T(0, 0) = 1, T(1, 0) = m, T(n, 0) = T(n-1, n-1) and T(n, k) = T(n, k-1) + T(n-1, k-1), for n >= 0 and 0 <= k <= n. The case m = 1 is Aitken's array A011971 with the first column the Bell numbers A000110, case m = 0 is the triangle A046934 with the first column A032347 and case m = 2 is the triangle A046937 with the first column A038561.

			Array starts:
[0] 1, 0,  1,  1,  1,  2,  2,  3,  4,  6,  6,   8,  11,  15, ... A046934
[1] 1, 1,  2,  2,  3,  5,  5,  7, 10, 15, 15,  20,  27,  37, ... A011971
[2] 1, 2,  3,  3,  5,  8,  8, 11, 16, 24, 24,  32,  43,  59, ... A046937
[3] 1, 3,  4,  4,  7, 11, 11, 15, 22, 33, 33,  44,  59,  81, ...
[4] 1, 4,  5,  5,  9, 14, 14, 19, 28, 42, 42,  56,  75, 103, ...
[5] 1, 5,  6,  6, 11, 17, 17, 23, 34, 51, 51,  68,  91, 125, ...
[6] 1, 6,  7,  7, 13, 20, 20, 27, 40, 60, 60,  80, 107, 147, ...
[7] 1, 7,  8,  8, 15, 23, 23, 31, 46, 69, 69,  92, 123, 169, ...
[8] 1, 8,  9,  9, 17, 26, 26, 35, 52, 78, 78, 104, 139, 191, ...
[9] 1, 9, 10, 10, 19, 29, 29, 39, 58, 87, 87, 116, 155, 213, ...

The main diagonals of the triangles are in A352682.

Cf. A000110, A046934, A011971, A046937, A032347, A038561.

function BellTriangle(m, len)
    a = m; P = [1]; T = []
    for n in 1:len
        T = vcat(T, P)
        P = cumsum(vcat(a, P))
        a = P[end]
    end
T end
for n in 0:9 BellTriangle(n, 4) |> println end

alias(PS = ListTools:-PartialSums):
BellTriangle := proc(m, len) local a, k, P, T; a := m; P := [1]; T := [];
for n from 1 to len  do T := [op(T), P]; P := PS([a, op(P)]); a := P[-1] od;
ListTools:-Flatten(T) end:
for n from 0 to 9 do print(BellTriangle(n, 5)) od; # Prints array by rows.

nmax = 13;
row[m_] := row[m] = Module[{T}, T[0, 0] = 1; T[1, 0] = m; T[n_, 0] := T[n, 0] = T[n-1, n-1]; T[n_, k_] := T[n, k] = T[n, k-1] + T[n-1, k-1]; Table[T[n, k], {n, 0, nmax}, {k, 0, n}] // Flatten];
A[n_, k_] := row[n][[k+1]];
Table[A[n-k, k], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 07 2024 *)

Given a list T let PS(T) denote the list of partial sums of T. Given two list S and T let [S, T] denote the concatenation of the lists. Further let P[end] denote the last element of the list P. The Aitken-Bell triangle T of order m with n rows can be computed by the following procedure:
     A = [m], P = [1], T = [];
     Repeat n times: T = [T, P], P = PS([A, P]), A = [P[end]];
     Return T.

cp's OEIS Frontend

A046935 Sequence formed from rows of triangle A046934.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A275871 Row sums and second diagonal of A046934.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

Python

Formula

Extensions

A032347 Inverse binomial transform of A032346.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A032346 Essentially shifts 1 place right under inverse binomial transform.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A123346 Mirror image of the Bell triangle A011971, which is also called the Pierce triangle or Aitken's array.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A352685 Array of Aitken-Bell triangles of order m (read by rows) read by ascending antidiagonals.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia