login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049020 Triangle of numbers a(n,k), 0 <= k <= n: number of set partitions of {1,2,...,n} in which exactly k of the blocks have been distinguished. 21

%I #101 Dec 06 2023 14:18:20

%S 1,1,1,2,3,1,5,10,6,1,15,37,31,10,1,52,151,160,75,15,1,203,674,856,

%T 520,155,21,1,877,3263,4802,3556,1400,287,28,1,4140,17007,28337,24626,

%U 11991,3290,490,36,1,21147,94828,175896,174805,101031,34671,6972,786,45,1

%N Triangle of numbers a(n,k), 0 <= k <= n: number of set partitions of {1,2,...,n} in which exactly k of the blocks have been distinguished.

%C Triangle a(n,k) read by rows; given by [1, 1, 1, 2, 1, 3, 1, 4, 1, 5, 1, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is Deléham's operator defined in A084938.

%C Exponential Riordan array [exp(exp(x)-1), exp(x)-1]. - _Paul Barry_, Jan 12 2009

%C Equal to A048993*A007318. - _Philippe Deléham_, Oct 31 2011

%C This lower unitriangular array is the L factor in the LU decomposition of the Hankel matrix (Bell(i+j-2))_i,j >= 1, where Bell(n) = A000110(n). The U factor is A059098 (see Chamberland, p. 1672). - _Peter Bala_, Oct 15 2023

%H Alois P. Heinz, <a href="/A049020/b049020.txt">Rows n = 0..140, flattened</a>

%H M. Aigner, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00108-9">A characterization of the Bell numbers</a>, Discr. Math., 205 (1999), 207-210.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Barry2/barry281.html">Constructing Exponential Riordan Arrays from Their A and Z Sequences</a>, Journal of Integer Sequences, 17 (2014), #14.2.6.

%H Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, <a href="https://arxiv.org/abs/2308.14183">Combinatorial Identities for Vacillating Tableaux</a>, arXiv:2308.14183 [math.CO], 2023. See p. 11.

%H Marc Chamberland, <a href="https://doi.org/10.1016/j.laa.2011.08.030">Factored matrices can generate combinatorial identities</a>, Linear Algebra and its Applications, Volume 438, Issue 4, 15 Feb. 2013, pp. 1667-1677.

%H J. East and R. D. Gray, <a href="http://arxiv.org/abs/1404.2359">Idempotent generators in finite partition monoids and related semigroups</a>, arXiv preprint arXiv:1404.2359 [math.GR], 2014.

%H Tom Halverson and Theodore N. Jacobson, <a href="https://arxiv.org/abs/1808.08118">Set-partition tableaux and representations of diagram algebras</a>, arXiv:1808.08118 [math.RT], 2018.

%H Aoife Hennessy and Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry6/barry161.html">Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials</a>, J. Int. Seq. 14 (2011) # 11.8.2.

%H Marin Knežević, Vedran Krčadinac, and Lucija Relić, <a href="https://arxiv.org/abs/2012.15307">Matrix products of binomial coefficients and unsigned Stirling numbers</a>, arXiv:2012.15307 [math.CO], 2020.

%H W. F. Lunnon et al., <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa35/aa3511.pdf">Arithmetic properties of Bell numbers to a composite modulus I</a>, Acta Arith., 35 (1979), 1-16.

%H J. Riordan, <a href="/A001861/a001861_1.pdf">Letter, Oct 31 1977</a>. The array is on the second page.

%F a(n,k) = a(n-1, k-1) + (k+1)*a(n-1, k) + (k+1)*a(n-1, k+1), n >= 1.

%F a(n,k) = Sum_{i=0..n} Stirling2(n,i)*binomial(i,k). - _Vladeta Jovovic_, Jan 27 2001

%F E.g.f. for the k-th column is (1/k!)*(exp(x)-1)^k*exp(exp(x)-1). - _Vladeta Jovovic_, Jan 27 2001

%F G.f.: 1/(1-x-xy-x^2(1+y)/(1-2x-xy-2x^2(1+y)/(1-3x-xy-3x^2(1+y)/(1-4x-xy-4x^2(1+y)/(1-... (continued fraction). - _Paul Barry_, Apr 29 2009

%F E.g.f.: exp((y+1)*(exp(x)-1)). - _Geoffrey Critzer_, Nov 30 2012

%F Note that A244489 (which is essentially the same triangle) has the formula T(n,k) = Sum_{j=k..n} binomial(n,j)*Stirling_2(j,k)*Bell(n-j), where Bell(n) = A000110(n), for n >= 1, 0 <= k <= n-1. - _N. J. A. Sloane_, May 17 2016

%F a(2n,n) = A245109(n). - _Alois P. Heinz_, Aug 23 2017

%F Empirical: a(n,k) = p(1^n)[st(1^k)] (see A002872 for notation). - _Andrey Zabolotskiy_, Oct 17 2017

%F a(n,k) = Sum_{j=0..k} (-1)^(k-j)*A046716(k, k-j)*Bell(n + j)/k!. - _Peter Luschny_, Dec 06 2023

%e Triangle begins:

%e 1;

%e 1, 1;

%e 2, 3, 1;

%e 5, 10, 6, 1;

%e 15, 37, 31, 10, 1;

%e ...

%e From _Paul Barry_, Jan 12 2009: (Start)

%e Production array begins

%e 1, 1;

%e 1, 2, 1;

%e 0, 2, 3, 1;

%e 0, 0, 3, 4, 1;

%e 0, 0, 0, 4, 5, 1;

%e ... (End)

%p a:= proc(n, k) option remember; `if`(k<0 or k>n, 0,

%p `if`(n=0, 1, a(n-1, k-1) +(k+1)*(a(n-1, k) +a(n-1, k+1))))

%p end:

%p seq(seq(a(n, k), k=0..n), n=0..15); # _Alois P. Heinz_, Nov 30 2012

%t a[n_, k_] = Sum[StirlingS2[n, i]*Binomial[i, k], {i, 0, n}]; Flatten[Table[a[n, k], {n, 0, 9}, {k, 0, n}]]

%t (* _Jean-François Alcover_, Aug 29 2011, after _Vladeta Jovovic_ *)

%o (PARI) T(n,k)=if(k<0 || k>n,0,n!*polcoeff(polcoeff(exp((1+y)*(exp(x+x*O(x^n))-1)),n),k))

%o (Sage)

%o def A049020_triangle(dim):

%o M = matrix(ZZ, dim, dim)

%o for n in (0..dim-1): M[n, n] = 1

%o for n in (1..dim-1):

%o for k in (0..n-1):

%o M[n, k] = M[n-1, k-1]+(k+1)*M[n-1, k]+(k+1)*M[n-1, k+1]

%o return M

%o A049020_triangle(9) # _Peter Luschny_, Sep 19 2012

%Y First column gives A000110, second column = A005493.

%Y Third column = A003128, row sums = A001861, A059340.

%Y See A244489 for another version of this triangle.

%Y Cf. A059098, A245109, A046716.

%K nonn,tabl,nice,easy

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_.

%E Better definition from _Geoffrey Critzer_, Nov 30 2012.

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 04:59 EDT 2024. Contains 371264 sequences. (Running on oeis4.)