A095149 Triangle read by rows: Aitken's array (A011971) but with a leading diagonal before it given by the Bell numbers (A000110), 1, 1, 2, 5, 15, 52, ...
1, 1, 1, 2, 1, 2, 5, 2, 3, 5, 15, 5, 7, 10, 15, 52, 15, 20, 27, 37, 52, 203, 52, 67, 87, 114, 151, 203, 877, 203, 255, 322, 409, 523, 674, 877, 4140, 877, 1080, 1335, 1657, 2066, 2589, 3263, 4140, 21147, 4140, 5017, 6097, 7432, 9089, 11155, 13744, 17007, 21147
Offset: 0
Examples
Triangle starts:
1;
1, 1;
2, 1, 2;
5, 2, 3, 5;
15, 5, 7, 10, 15;
52, 15, 20, 27, 37, 52;
From _Gus Wiseman_, Aug 11 2020: (Start)
Row n = 3 counts the following set partitions (described in Emeric Deutsch's comment above):
{1}{234} {12}{34} {123}{4} {1234}
{1}{2}{34} {12}{3}{4} {13}{24} {124}{3}
{1}{23}{4} {13}{2}{4} {134}{2}
{1}{24}{3} {14}{23}
{1}{2}{3}{4} {14}{2}{3}
(End)
Links
- Alois P. Heinz, Rows n = 0..150, flattened (first 51 rows from Chai Wah Wu)
- Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv:1108.2642 [math.CO], 2011.
- Anders Claesson, Generalized pattern avoidance, Europ. J. Combin., 22 7 (2001), 961-971. See Proposition 3.
- A. Bernini, M. Bouvel and L. Ferrari, Some statistics on permutations avoiding generalized patterns, PU.M.A. Vol. 18 (2007), No. 3-4, pp. 223-237 (see transposed array p. 227).
Programs
-
Maple
with(combinat): T:=proc(n,k) if k=1 then bell(n-1) elif k=2 and n>=2 then bell(n-2) elif k<=n then add(binomial(k-2,i)*bell(n-2-i),i=0..k-2) else 0 fi end: matrix(8,8,T): for n from 1 to 11 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form Q[1]:=t*s: for n from 2 to 11 do Q[n]:=expand(t^n*subs(t=1,Q[n-1])+s*diff(Q[n-1],s)-Q[n-1]+s*Q[n-1]) od: for n from 1 to 11 do P[n]:=sort(subs(s=1,Q[n])) od: for n from 1 to 11 do seq(coeff(P[n],t,k),k=1..n) od; # yields sequence in triangular form - Emeric Deutsch, Oct 29 2006 A011971 := proc(n,k) option remember ; if k = 0 then if n=0 then 1; else A011971(n-1,n-1) ; fi ; else A011971(n,k-1)+A011971(n-1,k-1) ; fi ; end: A000110 := proc(n) option remember; if n<=1 then 1 ; else add( binomial(n-1,i)*A000110(n-1-i),i=0..n-1) ; fi ; end: A095149 := proc(n,k) option remember ; if k = 0 then A000110(n) ; else A011971(n-1,k-1) ; fi ; end: for n from 0 to 11 do for k from 0 to n do printf("%d, ",A095149(n,k)) ; od ; od ; # R. J. Mathar, Feb 05 2007 # alternative Maple program: b:= proc(n, m, k) option remember; `if`(n=0, 1, add( b(n-1, max(j, m), max(k-1, -1)), j=`if`(k=0, m+1, 1..m+1))) end: T:= (n, k)-> b(n, 0, n-k): seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Dec 20 2018
-
Mathematica
nmax = 10; t[n_, 1] = t[n_, n_] = BellB[n-1]; t[n_, 2] = BellB[n-2]; t[n_, k_] /; n >= k >= 3 := t[n, k] = t[n, k-1] + t[n-1, k-1]; Flatten[ Table[ t[n, k], {n, 1, nmax}, {k, 1, n}]] (* Jean-François Alcover, Nov 15 2011, from formula with offset 1 *) -
Python
# requires Python 3.2 or higher. from itertools import accumulate A095149_list, blist = [1,1,1], [1] for _ in range(2*10**2): b = blist[-1] blist = list(accumulate([b]+blist)) A095149_list += [blist[-1]]+ blist # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014
Formula
With offset 1, T(n,1) = T(n,n) = T(n+1,2) = B(n-1) = A000110(n-1) (the Bell numbers). T(n,k) = T(n,k-1) + T(n-1,k-1) for n >= k >= 3. T(n,n-1) = B(n-1) - B(n-2) = A005493(n-3) for n >= 3 (B(q) are the Bell numbers A000110). T(n,k) = A011971(n-2,k-2) for n >= k >= 2. In other words, deleting the first row and first column we obtain Aitken's array A011971 (also called Bell or Pierce triangle; offset in A011971 is 0). - Emeric Deutsch, Oct 29 2006
T(n,1) = B(n-1); T(n,2) = B(n-2) for n >= 2; T(n,k) = Sum_{i=0..k-2} binomial(k-2,i)*B(n-2-i) for 3 <= k <= n, where B(q) are the Bell numbers (A000110). Generating polynomial of row n is P[n](t) = Q[n](t,1), where Q[n](t,s) = t^n*Q[n-1](1,s) + s*dQ[n-1](t,s)/ds + (s-1) Q[n-1](t,s); Q[1](t,s) = ts. - Emeric Deutsch, Oct 29 2006
Extensions
Corrected and extended by R. J. Mathar, Feb 05 2007
Entry revised by N. J. A. Sloane, Jun 01 2005, Jun 16 2007
Comments