A259691 -id:A259691 - cp's OEIS frontend

A056857 Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.

1, 1, 1, 2, 2, 1, 5, 6, 3, 1, 15, 20, 12, 4, 1, 52, 75, 50, 20, 5, 1, 203, 312, 225, 100, 30, 6, 1, 877, 1421, 1092, 525, 175, 42, 7, 1, 4140, 7016, 5684, 2912, 1050, 280, 56, 8, 1, 21147, 37260, 31572, 17052, 6552, 1890, 420, 72, 9, 1, 115975, 211470, 186300, 105240, 42630, 13104, 3150, 600, 90, 10, 1

Offset: 1

Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000

Number of successive equalities s_i = s_{i+1} in a set partition {s_1, ..., s_n} of {1, ..., n}, where s_i is the subset containing i, s(1) = 1 and s(i) <= 1 + max of previous s(j)'s.
T(n,c) = number of set partitions of the set {1,2,...,n} in which the size of the block containing the element 1 is k+1. Example: T(4,2)=3 because we have 123|4, 124|3 and 134|2. - Emeric Deutsch, Nov 10 2006
Let P be the lower-triangular Pascal-matrix (A007318), Then this is exp(P) / exp(1). - Gottfried Helms, Mar 30 2007. [This comment was erroneously attached to A011971, but really belongs here. - N. J. A. Sloane, May 02 2015]
From David Pasino (davepasino(AT)yahoo.com), Apr 15 2009: (Start)
As an infinite lower-triangular matrix (with offset 0 rather than 1, so the entries would be B(n - c)*binomial(n, c), B() a Bell number, rather than B(n - 1 - c)*binomial(n - 1, c) as below), this array is S P S^-1 where P is the Pascal matrix A007318, S is the Stirling2 matrix A048993, and S^-1 is the Stirling1 matrix A048994.
Also, S P S^-1 = (1/e)*exp(P). (End)
Exponential Riordan array [exp(exp(x)-1), x]. Equal to A007318*A124323. - Paul Barry, Apr 23 2009
Equal to A049020*A048994 as infinite lower triangular matrices. - Philippe Deléham, Nov 19 2011
Build a superset Q[n] of set partitions of {1,2,...,n} by distinguishing "some" (possibly none or all) of the singletons. Indexed from n >= 0, 0 <= k <= n, T(n,k) is the number of elements in Q[n] that have exactly k distinguished singletons. A singleton is a subset containing one element. T(3,1) = 6 because we have {{1}'{2,3}}, {{1,2}{3}'}, {{1,3}{2}'}, {{1}'{2}{3}}, {{1}{2}'{3}}, {{1}{2}{3}'}. - Geoffrey Critzer, Nov 10 2012
Let Bell(n,x) denote the n-th Bell polynomial, the n-th row polynomial of A048993. Then this is the triangle of connection constants when expressing the basis polynomials Bell(n,x + 1) in terms of the basis polynomials Bell(n,x). For example, row 3 is (5, 6, 3, 1) and 5 + 6*Bell(1,x) + 3*Bell(2,x) + Bell(3,x) = 5 + 6*x + 3*(x + x^2) + (x + 3*x^2 + x^3) = 5 + 10*x + 6*x^2 + x^3 = (x + 1) + 3*(x + 1)^2 + (x + 1)^3 = Bell(3,x + 1). - Peter Bala, Sep 17 2013

			For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 successive equality, at i = 4.
Triangle begins:
    1;
    1,   1;
    2,   2,   1;
    5,   6,   3,   1;
   15,  20,  12,   4,   1;
   52,  75,  50,  20,   5,   1;
  203, 312, 225, 100,  30,   6,   1;
  ...
From _Paul Barry_, Apr 23 2009: (Start)
Production matrix is
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  3,  3,  1,  1;
  1,  4,  6,  4,  1,  1;
  1,  5, 10, 10,  5,  1,  1;
  1,  6, 15, 20, 15,  6,  1,  1;
  1,  7, 21, 35, 35, 21,  7,  1,  1;
  1,  8, 28, 56, 70, 56, 28,  8,  1,  1; ... (End)

W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]

Alois P. Heinz, Rows n = 1..141, flattened
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. See Table III.
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.
A. Hennessy and Paul Barry, Generalized Stirling Numbers, Exponential Riordan Arrays, and Orthogonal Polynomials, J. Int. Seq. 14 (2011) # 11.8.2, Corollary 17.
G. Hurst and A. Schultz, An elementary (number theory) proof of Touchard's congruence, arXiv:0906.0696v2 [math.CO], 2009.
A. O. Munagi, Set partitions with successions and separations, Intl. J. Math. Math. Sci. 2005 (2005) 451-463.
M. Spivey, A generalized recurrence for Bell numbers, J. Int. Seq., 11 (2008), no. 2, Article 08.2.5
W. Yang, Bell numbers and k-trees, Disc. Math. 156 (1996) 247-252.

Cf. Bell numbers A000110 (column c=0), A052889 (c=1), A105479 (c=2), A105480 (c=3).
Cf. A056858-A056863. Essentially same as A056860, where the rows are read from right to left.
Cf. also A007318, A005493, A270953.
See A259691 for another version.
T(2n+1,n+1) gives A124102.
T(2n,n) gives A297926.

with(combinat): A056857:=(n,c)->binomial(n-1,c)*bell(n-1-c): for n from 1 to 11 do seq(A056857(n,c),c=0..n-1) od; # yields sequence in triangular form; Emeric Deutsch, Nov 10 2006
with(linalg): # Yields sequence in matrix form:
A056857_matrix := n -> subs(exp(1)=1, exponential(exponential(
matrix(n,n,[seq(seq(`if`(j=k+1,j,0),k=0..n-1),j=0..n-1)])))):
A056857_matrix(8); # Peter Luschny, Apr 18 2011

t[n_, k_] := BellB[n-1-k]*Binomial[n-1, k]; Flatten[ Table[t[n, k], {n, 1, 11}, {k, 0, n-1}]](* Jean-François Alcover, Apr 25 2012, after Emeric Deutsch *)

B(n) = sum(k=0, n, stirling(n, k, 2));
tabl(nn)={for(n=1, nn, for(k=0, n - 1, print1(B(n - 1 - k) * binomial(n - 1, k),", ");); print(););};
tabl(12); \\ Indranil Ghosh, Mar 19 2017

from sympy import bell, binomial
for n in range(1,12):
    print([bell(n - 1 - k) * binomial(n - 1, k) for k in range(n)]) # Indranil Ghosh, Mar 19 2017

def a(n): return (-1)^n / factorial(n)
@cached_function
def p(n, m):
    R = PolynomialRing(QQ, "x")
    if n == 0: return R(a(m))
    return R((m + x)*p(n - 1, m) - (m + 1)*p(n - 1, m + 1))
for n in range(11): print(p(n, 0).list())  # Peter Luschny, Jun 18 2023

T(n,c) = B(n-1-c)*binomial(n-1, c), where T(n,c) is the number of set partitions of {1, ..., n} that have c successive equalities and B() is a Bell number.
E.g.f.: exp(exp(x)+x*y-1). - Vladeta Jovovic, Feb 13 2003
G.f.: 1/(1-xy-x-x^2/(1-xy-2x-2x^2/(1-xy-3x-3x^2/(1-xy-4x-4x^2/(1-... (continued fraction). - Paul Barry, Apr 23 2009
Considered as triangle T(n,k), 0 <= k <= n: T(n,k) = A007318(n,k)*A000110(n-k) and Sum_{k=0..n} T(n,k)*x^k = A000296(n), A000110(n), A000110(n+1), A005493(n), A005494(n), A045379(n) for x = -1, 0, 1, 2, 3, 4 respectively. - Philippe Deléham, Dec 13 2009
Let R(n,x) denote the n-th row polynomial of the triangle. Then A000110(n+j) = Bell(n+j,1) = Sum_{k = 1..n} R(j,k)*Stirling2(n,k) (Spivey). - Peter Bala, Sep 17 2013

More terms from David Wasserman, Apr 22 2002

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

A350647 Number T(n,k) of partitions of [n] having k blocks containing their own index when blocks are ordered with decreasing largest elements; triangle T(n,k), n>=0, 0<=k<=ceiling(n/2), read by rows.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 3, 1, 6, 7, 2, 16, 25, 10, 1, 73, 91, 35, 4, 298, 390, 163, 25, 1, 1453, 1797, 755, 128, 7, 7366, 9069, 3919, 737, 55, 1, 40689, 49106, 21485, 4304, 380, 11, 238258, 284537, 126273, 26695, 2696, 110, 1, 1483306, 1751554, 785435, 173038, 19272, 976, 16

Offset: 0

Alois P. Heinz, Jan 09 2022

			T(4,0) = 6: 432|1, 42|31, 42|3|1, 4|31|2, 4|3|21, 4|3|2|1.
T(4,1) = 7: 4321, 43|21, 43|2|1, 421|3, 4|321, 4|32|1, 41|3|2.
T(4,2) = 2: 431|2, 41|32.
T(5,2) = 10: 5431|2, 541|32, 531|42, 51|432, 521|4|3, 5|421|3, 5|42|31, 5|42|3|1, 51|4|32, 51|4|3|2.
T(5,3) = 1: 51|42|3.
Triangle T(n,k) begins:
       1;
       0,      1;
       1,      1;
       1,      3,      1;
       6,      7,      2;
      16,     25,     10,     1;
      73,     91,     35,     4;
     298,    390,    163,    25,    1;
    1453,   1797,    755,   128,    7;
    7366,   9069,   3919,   737,   55,   1;
   40689,  49106,  21485,  4304,  380,  11;
  238258, 284537, 126273, 26695, 2696, 110, 1;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Wikipedia, Partition of a set

Columns k=0-1 give: A350649, A350650.
Row sums give A000110.
T(2n,n) gives A000124(n-1) for n>=1.
T(2n+1,n+1) gives A000012.
Cf. A259691, A350648.

b:= proc(n, m) option remember; expand(`if`(n=0, 1, add(
      `if`(j=n, x, 1)*b(n-1, max(m, j)), j=1..m+1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..ceil(n/2)))(b(n, 0)):
seq(T(n), n=0..14);

b[n_, m_] := b[n, m] = Expand[If[n == 0, 1, Sum[
     If[j == n, x, 1]*b[n-1, Max[m, j]], {j, 1, m+1}]]];
T[n_] := With[{p = b[n, 0]},
Table[Coefficient[p, x, i], {i, 0, Ceiling[n/2]}]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jan 11 2022, after Alois P. Heinz *)

Sum_{k=1..ceiling(n/2)} k * T(n,k) = A350648(n).

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

A259697 Triangle read by rows: T(n,k) = number of rook patterns on n X n board where bottom rook is in column k.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 4, 5, 5, 1, 9, 12, 15, 15, 1, 24, 32, 42, 52, 52, 1, 76, 99, 129, 166, 203, 203, 1, 279, 354, 451, 575, 726, 877, 877, 1, 1156, 1434, 1786, 2232, 2792, 3466, 4140, 4140, 1, 5296, 6451, 7883, 9664, 11881, 14621, 17884, 21147, 21147

Offset: 0

N. J. A. Sloane, Jul 05 2015

See Becker (1948/49) for precise definition.

This is the number of arrangements of non-attacking rooks on an n X n right triangular board where the bottom rook is in column k. The case of k=0 corresponds to the empty board where there is no bottom rook. - Andrew Howroyd, Jun 13 2017

			Triangle begins:
  1,
  1,  1,
  1,  2,  2,
  1,  4,  5,   5,
  1,  9, 12,  15,  15,
  1, 24, 32,  42,  52,  52,
  1, 76, 99, 129, 166, 203, 203,
  ...
From _Andrew Howroyd_, Jun 13 2017: (Start)
For n=3, the four solutions with the bottom rook in column 1 are:
  .      .      .      x
  . .    . x    x .    . .
  x . .  x . .  . . .  . . .
For n=3, the five solutions with the bottom rook in column 2 are:
  .      .      x      .       x
  . .    x .    . .    . x     . x
  . x .  . x .  . x .  . . .   . . .
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..1274
H. W. Becker, Rooks and rhymes, Math. Mag. 22 (1948/49), 23-26. See Table V.
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 23-26. [Annotated scanned copy]

Right edge is A000110.
Column k=1 is A005001.
Row sums are A000110(n+1).
Cf. A011971, A259691.

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

A(N)={my(T=matrix(N,N),U=matrix(N,N));T[1,1]=1;U[1,1]=1;
for(n=2,N,for(k=1,n, T[n,k]=if(k==1,T[n-1,n-1],T[n-1,k-1]+T[n,k-1]); U[n,k]=T[n,k]+U[n-1,k]));U}
{my(T=A(10));for(n=0,length(T),for(k=0,n,print1(if(k==0,1,T[n,k]),", "));print)} \\ Andrew Howroyd, Jun 13 2017

from sympy import bell, binomial
def a011971(n, k): return sum([binomial(k, i)*bell(n - k + i) for i in range(k + 1)])
def T(n, k): return 1 if k==0 else sum([a011971(i - 1, k - 1) for i in range(k, n + 1)])
for n in range(10): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Jun 17 2017

T(n,0) = 1, T(n,k) = Sum_{i=k..n} A011971(i-1,k-1) for k>0. - Andrew Howroyd, Jun 13 2017

Terms a(28) and beyond from Andrew Howroyd, Jun 13 2017

A290724 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking rooks on an n X n right triangular board with every square controlled by at least one rook.

Original entry on oeis.org

1, 1, 1, 0, 4, 1, 0, 2, 11, 1, 0, 0, 18, 26, 1, 0, 0, 6, 100, 57, 1, 0, 0, 0, 96, 444, 120, 1, 0, 0, 0, 24, 900, 1734, 247, 1, 0, 0, 0, 0, 600, 6480, 6246, 502, 1, 0, 0, 0, 0, 120, 8520, 39762, 21320, 1013, 1, 0, 0, 0, 0, 0, 4320, 90600, 219312, 70128, 2036, 1

Offset: 1

Andrew Howroyd, Aug 09 2017

See A146304 for algorithm and PARI code to produce this sequence.

Equivalently, the number of maximal independent vertex sets in the n-triangular honeycomb bishop graph with k vertices. A bishop can move along two axes in the triangular honeycomb grid.

			Triangle begins:
1;
1, 1;
0, 4,  1;
0, 2, 11,  1;
0, 0, 18,  26,  1;
0, 0,  6, 100,  57,    1;
0, 0,  0,  96, 444,  120,     1;
0, 0,  0,  24, 900, 1734,   247,     1;
0, 0,  0,  0,  600, 6480,  6246,   502,    1;
0, 0,  0,  0,  120, 8520, 39762, 21320, 1013, 1;
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Row sums are A290615.

Cf. A259691, A259697.

CoefficientList[Table[Sum[k! StirlingS2[m, k] StirlingS2[n + 1 - m, k + 1] x^(n - k), {m, 0, n}, {k, 0, Min[m, n - m]}], {n, 20}]/x, x] // Flatten (* Eric W. Weisstein, Feb 01 2024 *)

cp's OEIS Frontend

A056857 Triangle read by rows: T(n,c) = number of successive equalities in set partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

SageMath

Formula

Extensions

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

A350647 Number T(n,k) of partitions of [n] having k blocks containing their own index when blocks are ordered with decreasing largest elements; triangle T(n,k), n>=0, 0<=k<=ceiling(n/2), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

A259697 Triangle read by rows: T(n,k) = number of rook patterns on n X n board where bottom rook is in column k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions