A005490 -id:A005490 - cp's OEIS frontend

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

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, 1, 877, 877, 674, 372, 141, 37, 7, 1, 4140, 4140, 3263, 1915, 799, 235, 50, 8, 1, 21147, 21147, 17007, 10481, 4736, 1540, 365, 65, 9, 1, 115975, 115975, 94828, 60814, 29371, 10427, 2727, 537, 82, 10, 1

Offset: 0

Gerald McGarvey, Jun 05 2005

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.
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
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
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
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

			Array A(n,k) begins:
   1,   1,   1,    1,    1,     1,     1,     1,     1,      1, ... A000012;
   1,   2,   3,    4,    5,     6,     7,     8,     9,     10, ... A000027;
   2,   5,  10,   17,   26,    37,    50,    65,    82,    101, ... A002522;
   5,  15,  37,   77,  141,   235,   365,   537,   757,   1031, ... A005491;
  15,  52, 151,  372,  799,  1540,  2727,  4516,  7087,  10644, ... A005492;
  52, 203, 674, 1915, 4736, 10427, 20878, 38699, 67340, 111211, ... ;
Antidiagonal triangle, T(n, k), begins as:
     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,  1;
   877,  877,  674,  372, 141,  37,  7,  1;
  4140, 4140, 3263, 1915, 799, 235, 50,  8,  1;

F. Ruskey, Combinatorial Generation, preprint, 2001.

Alois P. Heinz, Antidiagonals n = 0..140, flattened
I. Mezo, The r-Bell numbers, J. Int. Seq. 14 (2011) # 11.1.1, Figure 1.
J. Riordan, Letter, Oct 31 1977, The array is on the second page.
F. Ruskey, Combinatorial Generation, 2003.
F. Ruskey, Lexicographic Algorithms [Broken link]

Cf. A000012, A000027, A000110, A002522, A005490, A005491.
Cf. A005492, A005493, A005494, A045379, A086659, A124824.
Main diagonal gives A134980.
Antidiagonal sums give A347420.

A108087:= func< n,k | (&+[Binomial(n-k,j)*k^j*Bell(n-k-j): j in [0..n-k]]) >;
[A108087(n,k): k in [0..n], n in [0..13]]; // G. C. Greubel, Dec 02 2022

with(combinat):
A:= (n, k)-> add(binomial(n, i) * k^i * bell(n-i), i=0..n):
seq(seq(A(d-k, k), k=0..d), d=0..12);  # Alois P. Heinz, Jul 18 2012

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 *)

f(n,k)=round (suminf(i=0,(i+k)^n/i!)/exp(1));
g(n,k)=for(k=0,k,print1(f(n,k),",")) \\ prints k+1 terms of n-th row

def A108087(n,k): return sum( k^j*bell_number(n-k-j)*binomial(n-k,j) for j in range(n-k+1))
flatten([[A108087(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Dec 02 2022

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).)
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
A(n,k) = Sum_{i=0..n} C(n,i) * k^i * Bell(n-i). - Alois P. Heinz, Jul 18 2012
Sum_{k=0..n-1} A(n-k,k) = A005490(n). - Alois P. Heinz, Jan 05 2022
From G. C. Greubel, Dec 02 2022: (Start)
T(n, n) = A000012(n).
T(n, n-1) = A000027(n).
T(n, n-2) = A002522(n-1).
T(n, n-3) = A005491(n-2).
T(n, n-4) = A005492(n+1).
T(2*n, n) = A134980(n).
T(2*n, n+1) = A124824(n), n >= 1.
Sum_{k=0..n} T(n, k) = A347420(n). (End)

A347420 Number of partitions of [n] where the first k elements are marked (0 <= k <= n) and at least k blocks contain their own index.

Original entry on oeis.org

1, 2, 5, 14, 45, 164, 667, 2986, 14551, 76498, 430747, 2582448, 16403029, 109918746, 774289169, 5715471606, 44087879137, 354521950932, 2965359744447, 25749723493074, 231719153184019, 2157494726318234, 20753996174222511, 205985762120971168, 2106795754056142537

Offset: 0

Alois P. Heinz, Jan 05 2022

nonn

			a(3) = 14 = 5 + 5 + 3 + 1: 123, 12|3, 13|2, 1|23, 1|2|3, 1'23, 1'2|3, 1'3|2, 1'|23, 1'|2|3, 1'3|2', 1'|2'3, 1'|2'|3, 1'|2'|3'.

Alois P. Heinz, Table of n, a(n) for n = 0..575
Wikipedia, Partition of a set

Antidiagonal sums of A108087.

Cf. A000110, A005490, A059841, A259691, A350589, A361380.

b:= proc(n, m) option remember;
     `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
    end:
a:= n-> add(b(i, n-i), i=0..n):
seq(a(n), n=0..25);

b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];
a[n_] := Sum[b[i, n - i], {i, 0, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 11 2022, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} A108087(n-k,k).
a(n) = 1 + A005490(n).
a(n) = A000110(n) + Sum_{k=1..n} k * A259691(n-1,k).
a(n) = Sum_{k=1..n} (k+1) * A259691(n-1,k).
a(n) = A000110(n) + A350589(n).
a(n) mod 2 = A059841(n).

A350589 Sum over all partitions of [n] of the number of blocks containing their own index.

Original entry on oeis.org

0, 1, 3, 9, 30, 112, 464, 2109, 10411, 55351, 314772, 1903878, 12189432, 82274309, 583389847, 4332513061, 33607736990, 271657081128, 2283282938288, 19916981288017, 179994994948647, 1682624910161483, 16247280435775188, 161833756265886822, 1660836884761337248

Offset: 0

Alois P. Heinz, Jan 07 2022

nonn

Also the number of partitions of [n] where the first k elements are marked (1 <= k <= n) and at least k blocks contain their own index: a(3) = 9 = 5 + 3 + 1: 1'23, 1'2|3, 1'3|2, 1'|23, 1'|2|3, 1'3|2', 1'|2'3, 1'|2'|3, 1'|2'|3'.

			a(3) = 9 = 1 + 1 + 2 + 2 + 3: 123, 12|3, 13|2, 1|23, 1|2|3.

Alois P. Heinz, Table of n, a(n) for n = 0..575
Wikipedia, Partition of a set

Cf. A000110, A005490, A088911, A108087, A259691, A347420, A350648.

b:= proc(n, m) option remember;
     `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
    end:
a:= n-> add(b(n-i, i), i=1..n):
seq(a(n), n=0..25);

b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];
a[n_] := Sum[b[n - i, i], {i, 1, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 11 2022, after Alois P. Heinz *)

a(n) = Sum_{k=1..n} A108087(n-k,k).
a(n) = Sum_{k=1..n} k * A259691(n-1,k).
a(n) = Sum_{k=1..n} A259691(n,k)/k.
a(n) = A347420(n) - A000110(n).
a(n) = 1 + A005490(n) - A000110(n).
a(n) mod 2 = A088911(n+5).

A005492 From expansion of falling factorials.

Original entry on oeis.org

4, 15, 52, 151, 372, 799, 1540, 2727, 4516, 7087, 10644, 15415, 21652, 29631, 39652, 52039, 67140, 85327, 106996, 132567, 162484, 197215, 237252, 283111, 335332, 394479, 461140, 535927, 619476, 712447, 815524, 929415, 1054852, 1192591, 1343412, 1508119, 1687540

Offset: 4

N. J. A. Sloane, Simon Plouffe

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 4..1004
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
E. G. Whitehead, Jr., Stirling number identities from chromatic polynomials, J. Combin. Theory, A 24 (1978), 314-317.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Row n=4 of A108087 (shifted and first term prepended).

Cf. A005490.

[n^4 -16*n^3 +102*n^2 -300*n +340: n in [4..50]]; // G. C. Greubel, Dec 01 2022

A005492:=-(15-23*z+41*z**2-13*z**3+4*z**4)/(z-1)**5; # Conjectured by Simon Plouffe in his 1992 dissertation. Gives sequence except for the leading 4.

LinearRecurrence[{5,-10,10,-5,1},{4,15,52,151,372},50] (* Harvey P. Dale, Dec 25 2012 *)

[n^4 -16*n^3 +102*n^2 -300*n +340 for n in range(4,51)] # G. C. Greubel, Dec 01 2022

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).
a(n) = n^4 - 16*n^3 + 102*n^2 - 300*n + 340.
G.f.: x^4*(4-5*x+17*x^2+x^3+7*x^4)/(1-x)^5. - Harvey P. Dale, Dec 25 2012
E.g.f.: (1/6)*(-2040 - 762*x - 108*x^2 - 7*x^3 + (2040 - 1278*x + 366*x^2 - 60*x^3 + 6*x^4)*exp(x)). - G. C. Greubel, Dec 01 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 09 2004

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A347420 Number of partitions of [n] where the first k elements are marked (0 <= k <= n) and at least k blocks contain their own index.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A350589 Sum over all partitions of [n] of the number of blocks containing their own index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A005492 From expansion of falling factorials.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions