login
Array, read by antidiagonals, where A(n,k) = exp(-1)*Sum_{i>=0} (i+k)^n/i!.
11

%I #61 Sep 02 2024 19:54:00

%S 1,1,1,2,2,1,5,5,3,1,15,15,10,4,1,52,52,37,17,5,1,203,203,151,77,26,6,

%T 1,877,877,674,372,141,37,7,1,4140,4140,3263,1915,799,235,50,8,1,

%U 21147,21147,17007,10481,4736,1540,365,65,9,1,115975,115975,94828,60814,29371,10427,2727,537,82,10,1

%N Array, read by antidiagonals, where A(n,k) = exp(-1)*Sum_{i>=0} (i+k)^n/i!.

%C The column for k=0 is A000110 (Bell or exponential numbers). The column for k=1 is A000110 starting at offset 1. The column for k=2 is A005493 (Sum_{k=0..n} k*Stirling2(n,k).). The column for k=3 is A005494 (E.g.f.: exp(3*z+exp(z)-1).). The column for k=4 is A045379 (E.g.f.: exp(4*z+exp(z)-1).). The row for n=0 is 1's sequence, the row for n=1 is the natural numbers. The row for n=2 is A002522 (n^2 + 1.). The row for n=3 is A005491 (n^3 + 3n + 1.). The row for n=4 is A005492.

%C Number of ways of placing n labeled balls into n+k boxes, where k of the boxes are labeled and the rest are indistinguishable. - Bradley Austin (artax(AT)cruzio.com), Apr 24 2006

%C The column for k = -1 (not shown) is A000296 (Number of partitions of an n-set into blocks of size >1. Also number of cyclically spaced (or feasible) partitions.). - _Gerald McGarvey_, Oct 08 2006

%C Equals antidiagonals of an array in which (n+1)-th column is the binomial transform of n-th column, with leftmost column = the Bell sequence, A000110. - _Gary W. Adamson_, Apr 16 2009

%C Number of partitions of [n+k] where at least k blocks contain their own index element. A(2,2) = 10: 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4. - _Alois P. Heinz_, Jan 07 2022

%D F. Ruskey, Combinatorial Generation, preprint, 2001.

%H Alois P. Heinz, <a href="/A108087/b108087.txt">Antidiagonals n = 0..140, flattened</a>

%H I. Mezo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Mezo/mezo9.html">The r-Bell numbers</a>, J. Int. Seq. 14 (2011) # 11.1.1, Figure 1.

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

%H F. Ruskey, <a href="https://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf">Combinatorial Generation</a>, 2003.

%H F. Ruskey, <a href="http://www.cs.usyd.edu.au/~algo4301/Lexicographic.ps">Lexicographic Algorithms</a> [Broken link]

%F For n> 1, A(n, k) = k^n + sum_{i=0..n-2} A086659(n, i)*k^i. (A086659 is set partitions of n containing k-1 blocks of length 1, with e.g.f: exp(x*y)*(exp(exp(x)-1-x)-1).)

%F A(n, k) = k * A(n-1, k) + A(n-1, k+1), A(0, k) = 1. - Bradley Austin (artax(AT)cruzio.com), Apr 24 2006

%F A(n,k) = Sum_{i=0..n} C(n,i) * k^i * Bell(n-i). - _Alois P. Heinz_, Jul 18 2012

%F Sum_{k=0..n-1} A(n-k,k) = A005490(n). - _Alois P. Heinz_, Jan 05 2022

%F From _G. C. Greubel_, Dec 02 2022: (Start)

%F T(n, n) = A000012(n).

%F T(n, n-1) = A000027(n).

%F T(n, n-2) = A002522(n-1).

%F T(n, n-3) = A005491(n-2).

%F T(n, n-4) = A005492(n+1).

%F T(2*n, n) = A134980(n).

%F T(2*n, n+1) = A124824(n), n >= 1.

%F Sum_{k=0..n} T(n, k) = A347420(n). (End)

%e Array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012;

%e 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... A000027;

%e 2, 5, 10, 17, 26, 37, 50, 65, 82, 101, ... A002522;

%e 5, 15, 37, 77, 141, 235, 365, 537, 757, 1031, ... A005491;

%e 15, 52, 151, 372, 799, 1540, 2727, 4516, 7087, 10644, ... A005492;

%e 52, 203, 674, 1915, 4736, 10427, 20878, 38699, 67340, 111211, ... ;

%e Antidiagonal triangle, T(n, k), begins as:

%e 1;

%e 1, 1;

%e 2, 2, 1;

%e 5, 5, 3, 1;

%e 15, 15, 10, 4, 1;

%e 52, 52, 37, 17, 5, 1;

%e 203, 203, 151, 77, 26, 6, 1;

%e 877, 877, 674, 372, 141, 37, 7, 1;

%e 4140, 4140, 3263, 1915, 799, 235, 50, 8, 1;

%p with(combinat):

%p A:= (n, k)-> add(binomial(n, i) * k^i * bell(n-i), i=0..n):

%p seq(seq(A(d-k, k), k=0..d), d=0..12); # _Alois P. Heinz_, Jul 18 2012

%t Unprotect[Power]; 0^0 = 1; A[n_, k_] := Sum[Binomial[n, i] * k^i * BellB[n - i], {i, 0, n}]; Table[Table[A[d - k, k], {k, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Nov 05 2015, after _Alois P. Heinz_ *)

%o (PARI) f(n,k)=round (suminf(i=0,(i+k)^n/i!)/exp(1));

%o g(n,k)=for(k=0,k,print1(f(n,k),",")) \\ prints k+1 terms of n-th row

%o (Magma)

%o A108087:= func< n,k | (&+[Binomial(n-k,j)*k^j*Bell(n-k-j): j in [0..n-k]]) >;

%o [A108087(n,k): k in [0..n], n in [0..13]]; // _G. C. Greubel_, Dec 02 2022

%o (SageMath)

%o def A108087(n,k): return sum( k^j*bell_number(n-k-j)*binomial(n-k,j) for j in range(n-k+1))

%o flatten([[A108087(n,k) for k in range(n+1)] for n in range(14)]) # _G. C. Greubel_, Dec 02 2022

%Y Cf. A000012, A000027, A000110, A002522, A005490, A005491.

%Y Cf. A005492, A005493, A005494, A045379, A086659, A124824.

%Y Main diagonal gives A134980.

%Y Antidiagonal sums give A347420.

%K nonn,tabl

%O 0,4

%A _Gerald McGarvey_, Jun 05 2005