|
| |
|
|
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,...
|
|
5
| |
|
|
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
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| Or, prefix Aitken's array (A011971) with a leading diagonal of zeros and take the differences of each row to get the new triangle.
With offset 1, triangle read by rows: T(n,k) is the number of partitions of the set {1,2,...,n} in which k is the largest entry in the block containing 1 (1<=k<=n). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 29 2006
Row term sums = the Bell numbers starting with A000110(1): 1, 2, 5, 15...
The k-th term in the n-th row is the number of permutations of length n starting with k and avoiding the dashed pattern 23-1. Equivalently, the number of permutations of length n ending with k and avoiding 1-32. - Andrew Baxter (baxter(AT)math.rutgers.edu), Jun 13 2011.
|
|
|
REFERENCES
| Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, Arxiv preprint arXiv:1108.2642, 2011
Claesson, Anders. Generalized pattern avoidance. European J. Combin.,
22 (7):961--971, 2001. See Proposition 3.
|
|
|
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 first row and first column we obtain Aitken's array A011971 (also called Bell or Pierce triangle; offset in A011971 is 0). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 29 2006
T(n,1)=B(n-1); T(n,2)=B(n-2) for n>=2; T(n,k)=Sum(binom(k-2,i)*B(n-2-i), i=0..k-2) 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 (deutsch(AT)duke.poly.edu), Oct 29 2006
|
|
|
EXAMPLE
| Triangle starts:
1;
1,1;
2,1,2;
5,2,3,5;
15,5,7,10,15;
52,15,20,27,37,52;
|
|
|
MAPLE
| 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 (mathar(AT)strw.leidenuniv.nl), Feb 05 2007
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 (deutsch(AT)duke.poly.edu), Oct 29 2006
|
|
|
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}]] (* From Jean-François Alcover, Nov 15 2011, from formula with offset 1 *)
|
|
|
CROSSREFS
| Cf. A000110, A005493, A011971, A188919.
Sequence in context: A153206 A144155 A109631 * A064192 A124218 A025165
Adjacent sequences: A095146 A095147 A095148 * A095150 A095151 A095152
|
|
|
KEYWORD
| nonn,tabl,easy,nice
|
|
|
AUTHOR
| Gary W. Adamson (qntmpkt(AT)yahoo.com), May 30 2004
|
|
|
EXTENSIONS
| Corrected and extended by R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Feb 05 2007
Entry revised by N. J. A. Sloane (njas(AT)research.att.com), Jun 01 2005, Jun 16 2007
|
| |
|
|
