A347420 -id:A347420 - 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)

A259691 Triangle read by rows: T(n,k) number of arrangements of non-attacking rooks on an n X n right triangular board where the top rook is in row k (n >= 0, 1 <= k <= n+1).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 6, 3, 1, 15, 20, 12, 4, 1, 52, 74, 51, 20, 5, 1, 203, 302, 231, 104, 30, 6, 1, 877, 1348, 1116, 564, 185, 42, 7, 1, 4140, 6526, 5745, 3196, 1175, 300, 56, 8, 1, 21147, 34014, 31443, 18944, 7700, 2190, 455, 72, 9, 1

Offset: 0

N. J. A. Sloane, Jul 05 2015

Another version of A056857.
See Becker (1948/49) for precise definition.
The case of n=k+1 corresponds to the empty board where there is no top rook. - Andrew Howroyd, Jun 13 2017
T(n-1,k) is the number of partitions of [n] where exactly k blocks contain their own index element.  T(3,2) = 6: 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4. - Alois P. Heinz, Jan 07 2022

			Triangle begins:
    1;
    1,   1;
    2,   2,   1;
    5,   6,   3,   1;
   15,  20,  12,   4,  1;
   52,  74,  51,  20,  5, 1;
  203, 302, 231, 104, 30, 6, 1;
  ...
From _Andrew Howroyd_, Jun 13 2017: (Start)
For n=3 the 5 solutions with the top rook in row 1 are:
  x      x      x      x      x
  . .    . .    . .    . x    . x
  . . .  . . x  . x .  . . .  . . x
For n=3 the 6 solutions with the top rook in row 2 are:
  .      .      .      .      .      .
  x .    x .    x .    . x    . x    . x
  . . .  . x .  . . x  . . .  x . .  . . x
(End)

Alois P. Heinz, Rows n = 0..140, flattened (first 49 rows from Andrew Howroyd)
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. See Table II.
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]
Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 17.

First column is A000110.
Row sums are A000110(n+1).
Cf. A056857, A259697, A108087, A347420, A350589.

b:= proc(n, m) option remember; `if`(n=0, 1,
     `if`(n<0, 1/m, m*b(n-1, m)+b(n-1, m+1)))
    end:
T:= (n, k)-> k*b(n-k, k):
seq(seq(T(n, k), k=1..n+1), n=0..10);  # Alois P. Heinz, Jan 07 2022

T[n_, k_] := If[k>n, 1, k*Sum[Binomial[n-k, i]*k^i*BellB[n-k-i], {i, 0, n - k}]];
Table[T[n, k], {n, 0, 10}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Jul 03 2018, after Andrew Howroyd *)

bell(n) = sum(k=0, n, stirling(n, k, 2));
T(n,k) = if(k>n, 1, k*sum(i=0,n-k, binomial(n-k,i) * k^i * bell(n-k-i)));
for(n=0,6, for(k=1,n+1, print1(T(n,k),", ")); print) \\ Andrew Howroyd, Jun 13 2017

T(n,n+1) = 1, T(n,k) = k*Sum_{i=0..n-k} binomial(n-k,i) * k^i * Bell(n-k-i) for k<=n. - Andrew Howroyd, Jun 13 2017
From Alois P. Heinz, Jan 07 2022: (Start)
T(n,k) = k * A108087(n-k,k) for 1 <= k <= n.
Sum_{k=1..n+1} k * T(n,k) = A350589(n+1).
Sum_{k=1..n+1} (k+1) * T(n,k) = A347420(n+1). (End)

Name edited and terms a(28) and beyond from Andrew Howroyd, Jun 13 2017

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

Original entry on oeis.org

1, 4, 13, 44, 163, 666, 2985, 14550, 76497, 430746, 2582447, 16403028, 109918745, 774289168, 5715471605, 44087879136, 354521950931, 2965359744446, 25749723493073, 231719153184018, 2157494726318233, 20753996174222510, 205985762120971167, 2106795754056142536

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

Old name was: From expansion of falling factorials.

			a(3) = 13 = 5 + 5 + 3: 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.

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

E. G. Whitehead, Jr., Stirling number identities from chromatic polynomials, J. Combin. Theory, A 24 (1978), 314-317.

Cf. A000035, A000110, A108087, A259691, A347420.

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-k, k), k=0..n-1):
seq(a(n), n=1..24);  # Alois P. Heinz, Jan 05 2022

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 - k, k], {k, 0, n - 1}];
Table[a[n], {n, 1, 24}] (* Jean-François Alcover, Apr 24 2022, after Alois P. Heinz *)

a(n) = Sum_{i=1..n} b(n, i) where b(n, 1) = n and b(n+1, i+1) = (n-i) * b(n, i) + b(n+1, i) [From Whitehead]. - Sean A. Irvine, Jul 01 2016
From Alois P. Heinz, Jan 05 2022: (Start)
a(n) = Sum_{k=0..n-1} A108087(n-k,k).
a(n) = A000110(n) + Sum_{k=1..n-1} A259691(n,k)/k.
a(n) = A347420(n) - 1.
a(n) mod 2 = n mod 2 = A000035(n). (End)

More terms from Sean A. Irvine, Jul 01 2016

New name from Alois P. Heinz, Jan 07 2022

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

A361380 Sum over the j-th term of the (n-j)-th inverse binomial transform of the Bell numbers (A000110) for all j in [n].

Original entry on oeis.org

1, 2, 3, 6, 17, 56, 215, 922, 4305, 21894, 119539, 696632, 4314925, 28237146, 194602079, 1407456694, 10649642837, 84100177424, 691474151187, 5907288773554, 52340230286509, 480153099982726, 4553711640946919, 44584683333637168, 450075389309517849

Offset: 0

Alois P. Heinz, Mar 09 2023

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..576

Antidiagonal sums of A361781.

Cf. A000110, A059841, A290219, A347420.

a:= n-> add(add(binomial(i, j)*(i-n)^(i-j)*combinat[bell](j), j=0..i), i=0..n):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> add(i!*coeff(series(exp(exp(x)-(n-i)*x-1), x, i+1), x, i), i=0..n):
seq(a(n), n=0..25);
# third Maple program:
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, i-n), i=0..n):
seq(a(n), n=0..25);

from math import comb
from sympy import bell
def A361380(n): return sum(comb(i,j)*(i-n)**(i-j)*bell(j) for i in range(n+1) for j in range(i+1)) # Chai Wah Wu, Apr 05 2023

a(n) = Sum_{i=0..n} i! * [x^i] exp(exp(x)-(n-i)*x-1).
a(n) = Sum_{0<=j<=i<=n} binomial(i,j)*(i-n)^(i-j)*Bell(j).
a(n) mod 2 = A059841(n).

A380179 Triangle T(n,k) read by rows: T(n,k) = -binomial(n+1,k) + Sum_{i=0..k} Sum_{j=0..i+1} (i+1)^(n-i+j)(-1)^(k-i)/(j!(k-i)!) for 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 14, 14, 1, 1, 33, 68, 30, 1, 1, 72, 257, 218, 55, 1, 1, 151, 873, 1189, 553, 91, 1, 1, 310, 2812, 5734, 4094, 1204, 140, 1, 1, 629, 8802, 25916, 26484, 11598, 2352, 204, 1, 1, 1268, 27107, 112718, 158840, 96702, 28566, 4236, 285, 1

Offset: 0

Mikhail Kurkov, Jan 14 2025

			Triangle begins:
  1;
  1,    1;
  1,    5,     1;
  1,   14,    14,      1;
  1,   33,    68,     30,      1;
  1,   72,   257,    218,     55,     1;
  1,  151,   873,   1189,    553,    91,     1;
  1,  310,  2812,   5734,   4094,  1204,   140,    1;
  1,  629,  8802,  25916,  26484, 11598,  2352,  204,   1;
  1, 1268, 27107, 112718, 158840, 96702, 28566, 4236, 285, 1;

Cf. A347420.

T(n,k) = if(k >= 0 && n >= k, -binomial(n+1, k) + sum(i=0, k, sum(j=0, i+1, (i+1)^(n-i+j)*(-1)^(k-i)/(j!*(k-i)!))))

Conjecture: A347420(n) = 2^n + Sum_{k=1..n-1} T(n-1, k) for n >= 0.

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

A259691 Triangle read by rows: T(n,k) number of arrangements of non-attacking rooks on an n X n right triangular board where the top rook is in row k (n >= 0, 1 <= k <= n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A361380 Sum over the j-th term of the (n-j)-th inverse binomial transform of the Bell numbers (A000110) for all j in [n].

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Python

Formula

A380179 Triangle T(n,k) read by rows: T(n,k) = -binomial(n+1,k) + Sum_{i=0..k} Sum_{j=0..i+1} (i+1)^(n-i+j)*(-1)^(k-i)/(j!*(k-i)!) for 0 <= k <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A380179 Triangle T(n,k) read by rows: T(n,k) = -binomial(n+1,k) + Sum_{i=0..k} Sum_{j=0..i+1} (i+1)^(n-i+j)(-1)^(k-i)/(j!(k-i)!) for 0 <= k <= n.