A056862
Triangle T(n,k) is the number of restricted growth strings (RGS) of set partitions of {1..n} that have a decrease at index k (1<=k
0, 0, 1, 0, 3, 4, 0, 10, 14, 16, 0, 37, 54, 63, 68, 0, 151, 228, 271, 296, 311, 0, 674, 1046, 1264, 1396, 1478, 1530, 0, 3263, 5178, 6349, 7084, 7555, 7862, 8065, 0, 17007, 27488, 34139, 38448, 41287, 43184, 44467, 45344, 0, 94828, 155642, 195494, 222044, 239976, 252230, 260690, 266584, 270724
Offset: 2
A363732 Triangle read by rows. The triangle algorithm applied to (-1)^n/n!.
1, -2, 1, 5, -4, 1, -15, 15, -6, 1, 52, -60, 30, -8, 1, -203, 260, -150, 50, -10, 1, 877, -1218, 780, -300, 75, -12, 1, -4140, 6139, -4263, 1820, -525, 105, -14, 1, 21147, -33120, 24556, -11368, 3640, -840, 140, -16, 1, -115975, 190323, -149040, 73668, -25578, 6552, -1260, 180, -18, 1
Offset: 0
Comments
The triangle algorithm, as understood here, is a transformation that maps a sequence of integers (a(n) : n >= 0) to a polynomial sequence. A polynomial sequence is a sequence of polynomials (P(n,x) : n >= 0) with degree(P(n, x)) = n for all n >= 0.
The polynomials P(n, x) are recursively defined by P(n, x) = p(n, 0, x), where the initial sequence is p(0, m, x) = a(m), and for n > 0 is given by
p(n, m, x) = (m + 1)*p(n - 1, m + 1, x) - (m + 1 - x)*p(n - 1, m, x).
Here we identify the polynomial sequence with the infinite lower triangular array of its coefficients, T(n, k) = [x^k] P(n, x). We call the mapping (a(n) : n >= 0) -> (T(n, k) : 0 <= k <= n) the 'triangle algorithm', following the lead of Kawasaki and Ohno.
Evaluating P(n, x) at different values of x gives rise to a multitude of other sequences; in particular, the transformation a(n) -> b(n) = P(n, 1) will be called the Akiyama-Tanigawa transform of a.
The triangle algorithm was studied by Akiyama and Tanigawa, Chen, Imatomi, Arakawa and Kaneko, Kawasaki and Ohno, and others, at first in connection with the Bernoulli and Poly-Bernoulli numbers.
.
The paradigmatic examples are:
a(n) = 1 -> x^n, the standard base of polynomials, A023531.
a(n) = n + 1 -> binomial(n, k), Pascal triangle, A007318.
a(n) = n + 1 -> P(n, 1) powers of 2, A000079.
a(n) = n + 1 -> P(n, 0) the all 1's sequence A000012.
a(n) = 2^n -> [x^k] P(n, x), A154921.
a(n) = 2^n -> P(n, 0) Fubini numbers, A000670.
a(n) = 2^n -> P(n, 1) ordered set partitions of subsets of [n], A000629.
a(n) = 2^n -> P(n,-1) osp. of [n] with even number of blocks, A052841.
a(n) = Chen(n) -> skp(n, x), Swiss-Knife polynomials, A153641.
a(n) = Chen(n) -> P(n, 0), 2^n*Euler(n, 1/2) = Euler(n), A122045.
a(n) = Chen(n) -> P(n, 1), 2^n*Euler(n, 1), A155585.
a(n) = (-1)^n/n! -> [x^k] P(n, x) this "Bell" triangle.
a(n) = (-1)^n/n! -> (-1)^n*P(n, 1) = Bell(n), A000110.
a(n) = (-1)^n/n! -> (-1)^n*P(n,-1) = 2-Bell(n), A005493.
a(n) = 1/n! -> (-1)^n*P(n, 1) = complementary Bell(n), A000587.
a(n) = 1/n! -> (-1)^n*P(n,-1) = complementary 2-Bell(n), A074051.
(For Chen's sequence see A363524.)
.
The present sequence deals with the case of the Bell numbers. In contrast to Aitken's array A011971 and its variants A123346 and A011972, the Bell numbers do not appear as a column of the triangle but as row sums (times (-1)^n), i.e., as values of the associated polynomials at x = 1. Comparing this with a similar situation with the Bernoulli numbers/polynomials, our triangle could be viewed as a more organic generalization of the Bell numbers. Indeed, the names 'Bell triangle' and 'Bell polynomials' would be justified here; but these are already assigned to other concepts.
Examples
The triangle T(n, k) starts: [0] 1; [1] -2, 1; [2] 5, -4, 1; [3] -15, 15, -6, 1; [4] 52, -60, 30, -8, 1; [5] -203, 260, -150, 50, -10, 1; [6] 877, -1218, 780, -300, 75, -12, 1; [7] -4140, 6139, -4263, 1820, -525, 105, -14, 1; [8] 21147, -33120, 24556, -11368, 3640, -840, 140, -16, 1;
Links
- Peter Luschny, Table of n, a(n) for row 0..100.
- Kwang-Wu Chen, Algorithms for Bernoulli numbers and Euler numbers, J. Integer Sequences, 4 (2001), #01.1.6.
- Masanobu Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. Integer Sequences, 3 (2000), #00.2.9.
- Naho Kawasaki and Yasuo Ohno, The triangle algorithm for Bernoulli polynomials, Integers, vol. 23 (2023). (See figure 4.)
- D. Merlini, R. Sprugnoli, and M. C. Verri, The Akiyama-Tanigawa Transformation, Integers, 5 (1) (2005) #A05.
Crossrefs
Programs
-
Maple
TA := proc(a, n, m, x) option remember; if n = 0 then a(m) else normal((m + 1)*TA(a, n - 1, m + 1, x) - (m + 1 - x)*TA(a, n - 1, m, x)) fi end: seq(seq(coeff(TA(n -> (-1)^n/n!, n, 0, x), x, k), k = 0..n), n = 0..10);
-
Mathematica
(* rows[0..n], n[0..oo] *) (* row[n]= *) n=9;r={};For[a=n+1,a>0,a--,AppendTo[r,(-1)^(a+1)*Sum[StirlingS2[a,k],{k,0,a}]*Product[(2*(a+j))/(2*j+2),{j,0,n-a}]]];r (* columns[1..n], n[0..oo] *) (* column[n]= *) n=0;c={};For[a=1,a<15,a++,AppendTo[c,(-1)^(a+1)*Sum[StirlingS2[a,k],{k,0,a}]*Product[(2*(a+j-1))/(2*j),{j,1,n}]]];c (* sequence *) s={};For[n=0,n<15,n++,For[a=n+1,a>0,a--,AppendTo[s,(-1)^(a+1)*Sum[StirlingS2[a,k],{k,0,a}]*Product[(2*(a+j))/(2*j+2),{j,0,n-a}]]]];s (* Detlef Meya, Jun 22 2023 *) -
SageMath
def a(n): return (-1)^n / factorial(n) @cached_function def p(n, m): R = PolynomialRing(QQ, "x") if n == 0: return R(a(m)) return R((m + 1)*p(n - 1, m + 1) - (m + 1 - x)*p(n - 1, m)) for n in range(10): print(p(n, 0).list())
A056859 Triangle of number of falls in set partitions of n.
1, 2, 0, 4, 1, 0, 8, 7, 0, 0, 16, 32, 4, 0, 0, 32, 121, 49, 1, 0, 0, 64, 411, 360, 42, 0, 0, 0, 128, 1304, 2062, 624, 22, 0, 0, 0, 256, 3949, 10163, 6042, 730, 7, 0, 0, 0, 512, 11567, 45298, 45810, 12170, 617, 1, 0, 0, 0, 1024, 33056, 187941, 296017, 141822, 18325, 385, 0, 0, 0, 0
Offset: 1
Comments
Number of falls s_i > s_{i+1} in a set partition {s_1, ..., s_n} of {1, ..., n}, where s_i is the subset containing i, s(1) = 1 and s(i) <= 1 + max of previous s(j)'s.
The maximum number of falls is in a set partition like 1,2,1,3,2,1,... - Franklin T. Adams-Watters, Jun 08 2006
Examples
For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 fall, at i = 2.
T(n=3,f=0)=4 counts the partitions {1,1,1}, {1,1,2}, {1,2,2}, and {1,2,3}. T(n=3,f=1) counts the partition {1,2,1}. - _R. J. Mathar_, Mar 04 2016
1;
2,0;
4,1,0;
8,7,0,0;
16,32,4,0,0;
32,121,49,1,0,0;
64,411,360,42,0,0,0;
128,1304,2062,624,22,0,0,0;
256,3949,10163,6042,730,7,0,0,0;
512,11567,45298,45810,12170,617,1,0,0,0;
1024,33056,187941,296017,141822,18325,385,0,0,0,0;
2048,92721,739352,1708893,1318395,330407,21605,176,0,0,0,0;
References
- W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]
Links
- Alois P. Heinz, Rows n = 1..100, flattened
Programs
-
Maple
b:= proc(n, i, m) option remember; `if`(n=0, x, expand(add(b(n-1, j, max(m, j))* `if`(j -
Mathematica
b[n_, i_, m_] := b[n, i, m] = If[n == 0, x, Expand[Sum[b[n - 1, j, Max[m, j]]*If[j < i, x, 1], {j, 1, m + 1}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1, 0]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, May 24 2016, after Alois P. Heinz *)
Extensions
Corrected and extended by Franklin T. Adams-Watters, Jun 08 2006
Comments
Examples
For example, [1, 2, 1, 2, 2, 3] is the RGS of a set partition of {1, 2, 3, 4, 5, 6} and has 1 fall, at i = 2. 0; 0,1; 0,3,4; 0,10,14,16; 0,37,54,63,68; 0,151,228,271,296,311; 0,674,1046,1264,1396,1478,1530; 0,3263,5178,6349,7084,7555,7862,8065; 0,17007,27488,34139,38448,41287,43184,44467,45344; 0,94828,155642,195494,222044,239976,252230,260690,266584,270724; 0,562595,935534,1186845,1358452,1476959,1559602,1617737,1658952,1688379, 1709526;References
Links
Crossrefs
Programs
Maple
b:= proc(n, i, m, t) option remember; `if`(n=0, [1, 0], add((p-> p+[0, `if`(j (p-> seq(coeff(p, x, i), i=1..n-1))(b(n, 1, 0$2)[2]):
seq(T(n), n=2..12); # Alois P. Heinz, Mar 24 2016 Mathematica
b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, {1, 0}, Sum[Function[p, p + {0, If[jJean-François Alcover, May 23 2016, after Alois P. Heinz *) Formula
Extensions