A110038 -id:A110038 - cp's OEIS frontend

A080510 Triangle read by rows: T(n,k) gives the number of set partitions of {1,...,n} with maximum block length k.

1, 1, 1, 1, 3, 1, 1, 9, 4, 1, 1, 25, 20, 5, 1, 1, 75, 90, 30, 6, 1, 1, 231, 420, 175, 42, 7, 1, 1, 763, 2016, 1015, 280, 56, 8, 1, 1, 2619, 10024, 6111, 1890, 420, 72, 9, 1, 1, 9495, 51640, 38010, 12978, 3150, 600, 90, 10, 1, 1, 35695, 276980, 244035, 91938, 24024, 4950, 825, 110, 11, 1

Offset: 1

Wouter Meeussen, Mar 22 2003

Row sums are A000110 (Bell numbers). Second column is A001189 (Degree n permutations of order exactly 2).
From Peter Luschny, Mar 09 2009: (Start)
Partition product of Product_{j=0..n-1} ((k + 1)*j - 1) and n! at k = -1, summed over parts with equal biggest part (see the Luschny link).
Underlying partition triangle is A036040.
Same partition product with length statistic is A008277.
Diagonal a(A000217) = A000012.
Row sum is A000110. (End)
From Gary W. Adamson, Feb 24 2011: (Start)
Construct an array in which the n-th row is the partition function G(n,k), where G(n,1),...,G(n,6) = A000012, A000085, A001680, A001681, A110038, A148092, with the first few rows
  1,   1,   1,   1,   1,   1,    1, ... = A000012
  1,   2,   4,  10,  26,  76,  232, ... = A000085
  1,   2,   5,  14,  46, 166,  652, ... = A001680
  1,   2,   5,  15,  51, 196,  827, ... = A001681
  1,   2    5   15   52  202   869, ... = A110038
  1,   2,   5   15   52  203   876, ... = A148092
  ...
Rows tend to A000110, the Bell numbers. Taking finite differences from the top, then reorienting, we obtain triangle A080510.
The n-th row of the array is the eigensequence of an infinite lower triangular matrix with n diagonals of Pascal's triangle starting from the right and the rest zeros. (End)

			T(4,3) = 4 since there are 4 set partitions with longest block of length 3: {{1},{2,3,4}}, {{1,3,4},{2}}, {{1,2,3},{4}} and {{1,2,4},{3}}.
Triangle begins:
  1;
  1,    1;
  1,    3,     1;
  1,    9,     4,    1;
  1,   25,    20,    5,    1;
  1,   75,    90,   30,    6,   1;
  1,  231,   420,  175,   42,   7,  1;
  1,  763,  2016, 1015,  280,  56,  8,  1;
  1, 2619, 10024, 6111, 1890, 420, 72,  9,  1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Peter Luschny, Counting with Partitions.
Peter Luschny, Generalized Stirling_2 Triangles.
J. Riordan, Letter, 11/23/1970. See second page of letter.

Cf. A080107, A080337, A008277, A178979, A276922, A327884.
Cf. A157396, A157397, A157398, A157399, A157400, A157401, A157402, A157403, A157404, A157405. - Peter Luschny, Mar 09 2009
Cf. A000012, A000085, A001680, A001681, A110038, A148092. - Gary W. Adamson, Feb 24 2011
Columns k=1..10 give: A000012 (for n>0), A001189, A229245, A229246, A229247, A229248, A229249, A229250, A229251, A229252. - Alois P. Heinz, Sep 17 2013
T(2n,n) gives A276961.
Take differences along rows of A229223. - N. J. A. Sloane, Jan 10 2018

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       add(b(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))
    end:
T:= (n, k)-> b(n, k) -b(n, k-1):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Apr 20 2012

<< DiscreteMath`NewCombinatorica`; Table[Length/@Split[Sort[Max[Length/@# ]&/@SetPartitions[n]]], {n, 12}]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[b[n-i*j, i-1]*n!/i!^j/(n-i*j)!/j!, {j, 0, n/i}]]]; T[n_, k_] := b[n, k]-b[n, k-1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)

E.g.f. for k-th column: exp(exp(x)*GAMMA(k, x)/(k-1)!-1)*(exp(x^k/k!)-1). - Vladeta Jovovic, Feb 04 2005
From Peter Luschny, Mar 09 2009: (Start)
T(n,0) = [n = 0] (Iverson notation) and for n > 0 and 1 <= m <= n.
T(n,m) = Sum_{a} M(a)|f^a| where a = a_1,...,a_n such that
1*a_1 + 2*a_2 + ... + n*a_n = n and max{a_i} = m, M(a) = n!/(a_1!*...*a_n!),
f^a = (f_1/1!)^a_1*...*(f_n/n!)^a_n and f_n = Product_{j=0..n-1} (-1) = (-1)^n. (End)
From Ludovic Schwob, Jan 15 2022: (Start)
T(2n,n) = C(2n,n)*(A000110(n)-1/2) for n>0.
T(n,m) = C(n,m)*A000110(n-m) for 2m > n > 0. (End)

A229223 Number G(n,k) of set partitions of {1,...,n} into sets of size at most k; triangle G(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 4, 5, 0, 1, 10, 14, 15, 0, 1, 26, 46, 51, 52, 0, 1, 76, 166, 196, 202, 203, 0, 1, 232, 652, 827, 869, 876, 877, 0, 1, 764, 2780, 3795, 4075, 4131, 4139, 4140, 0, 1, 2620, 12644, 18755, 20645, 21065, 21137, 21146, 21147

Offset: 0

Alois P. Heinz, Sep 16 2013

John Riordan calls these Allied Bell Numbers. - N. J. A. Sloane, Jan 10 2018
G(n,k) is defined for n,k >= 0.  The triangle contains only the terms with k<=n. G(n,k) = G(n,n) = A000110(n) for k>n.
G(n,k) - G(n,k-1) = A080510(n,k).
A column G(n>=0,k) can be generated by a linear recurrence with polynomial coefficients, where the initial terms correspond with A000110, and the coefficients contain constant factors derived from A008279 (cf. recg(k) in the fourth Maple program below). - Georg Fischer, May 19 2021

			G(4,2) = 10: 1/2/3/4, 12/3/4, 13/2/4, 14/2/3, 1/23/4, 1/24/3, 1/2/34, 12/34, 13/24, 14/23.
Triangle G(n,k) begins:
  1;
  0,  1;
  0,  1,   2;
  0,  1,   4,    5;
  0,  1,  10,   14,   15,
  0,  1,  26,   46,   51,   52;
  0,  1,  76,  166,  196,  202,  203;
  0,  1, 232,  652,  827,  869,  876,  877;
  0,  1, 764, 2780, 3795, 4075, 4131, 4139, 4140;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
J. Riordan, Letter, 11/23/1970

Columns k=0-10 give: A000007, A000012, A000085, A001680, A001681, A110038, A148092, A229224, A229225, A229226, A229227.
Main diagonal gives: A000110. Lower diagonal gives: A058692.
Cf. A066223 (G(2n,2)), A229228 (G(2n,n)), A229229 (G(n^2,n)), A227223 (G(2^n,n)).
Cf. A008279, A080510.

G:= proc(n, k) option remember; `if`(n=0, 1, `if`(k<1, 0,
       add(G(n-k*j, k-1) *n!/k!^j/(n-k*j)!/j!, j=0..n/k)))
    end:
seq(seq(G(n, k), k=0..n), n=0..10);
# second Maple program:
G:= proc(n, k) option remember; local j; if k>n then G(n, n)
      elif n=0 then 1 elif k<1 then 0 else G(n-k, k);
      for j from k-1 to 1 by -1 do %*(n-j)/j +G(n-j,k) od; % fi
    end:
seq(seq(G(n, k), k=0..n), n=0..10);
# third Maple program:
G:= proc(n, k) option remember; `if`(n=0, 1, add(
      G(n-i, k)*binomial(n-1, i-1), i=1..min(n, k)))
    end:
seq(seq(G(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Jun 26 2017
# fourth Maple program (for columns G(n>=0,k)):
init := n -> seq(a(j) = combinat:-bell(j), j=0..n): # A000110
b := (n, k) -> mul((n - j)/(j + 1), j = 0..k-1):
recg := k -> {(k-1)!*(add(j*b(n, j)*a(n-j), j = 1..k) - n*a(n)), init(k-1)}:
column := proc(k, len) local f; f := gfun:-rectoproc(recg(k), a(n), remember):
map(f, [$0..len-1]) end:
seq(print(column(k, 12)), k=1..9); # Georg Fischer, May 19 2021

g[n_, k_] := g[n, k] = If[n == 0, 1, If[k < 1, 0, Sum[g[n - k*j, k - 1] *n!/k!^j/(n - k*j)!/j!, { j, 0, n/k}]]]; Table[Table[g[n, k], { k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)

G(0,k) = 1, G(n,k) = 0 for n>0 and k<1, otherwise G(n,k) = Sum_{j=0..floor(n/k)} G(n-k*j,k-1) * n!/(k!^j*(n-k*j)!*j!).
G(n,k) = G(n-1,k) +(n-1)/1 *(G(n-2,k) +(n-2)/2 *(G(n-3,k) +(n-3)/3 *(G(n-4,k) + ... +(n-(k-1))/(k-1) *G(n-k,k)...))).
E.g.f. of column k: exp(Sum_{j=1..k} x^j/j!).

A148092 The partition function G(n,6).

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 876, 4131, 21065, 115274, 672673, 4163743, 27216840, 187160429, 1349511178, 10173555345, 79982663997, 654277037674, 5557624876513, 48931106059451, 445790174654588, 4196351007814659, 40757862664061104, 407944375184911787

Offset: 0

N. J. A. Sloane, May 13 2009

nonn

Set partitions into sets of size at most 6. The e.g.f. for partitions into sets of size at most s is exp( sum(j=1..s, x^j/j!) ). [Joerg Arndt, Dec 07 2012]

Alois P. Heinz, Table of n, a(n) for n = 0..500
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
F. L. Miksa, L. Moser and M. Wyman, Restricted partitions of finite sets, Canad. Math. Bull., 1 (1958), 87-96.

The sequences G(n,1), G(n,2), G(n,3), G(n,4), G(n,5), G(n,6) are given by A000012, A000085, A001680, A001681, A110038, A148092 respectively.
Column k=6 of A229223.
Cf. A276926.

G:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       add(G(n-i*j, i-1) *n!/i!^j/(n-i*j)!/j!, j=0..n/i)))
    end:
a:= n-> G(n, 6):
seq(a(n), n=0..30);  # Alois P. Heinz, Apr 20 2012
# second Maple program:
a:= proc(n) option remember; `if`(n<6, [1, 1, 2, 5, 15, 52][n+1],
      a(n-1)+(n-1)*(a(n-2) +(n-2)/2*(a(n-3) +(n-3)/3*(a(n-4)
            +(n-4)/4*(a(n-5) +(n-5)/5*a(n-6))))))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 15 2013

G[n_, i_] := G[n, i] = If[n == 0, 1, If[i<1, 0, Sum[G[n-i*j, i-1] *n!/i!^j/(n-i*j)!/j!, {j, 0, n/i}]]]; a[n_] := G[n, 6]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 17 2014, after Alois P. Heinz *)

E.g.f.: exp( x + x^2/2 + x^3/6 + x^4/24 + x^5/120 + x^6/720 ).

a(n) = G(n,6) with G(0,i) = 1, G(n,i) = 0 for n>0 and i<1, otherwise G(n,i) = Sum_{j=0..floor(n/i)} G(n-i*j,i-1) * n!/(i!^j*(n-i*j)!*j!). - Alois P. Heinz, Apr 20 2012

A276925 Number of ordered set partitions of [n] with at most five elements per block.

Original entry on oeis.org

1, 1, 3, 13, 75, 541, 4682, 47278, 545594, 7083258, 102177222, 1621316466, 28065324210, 526301293518, 10628781887724, 229983021824556, 5308071700475544, 130168746864660504, 3379871981604782664, 92634950510491052664, 2672550322299614660904

Offset: 0

Alois P. Heinz, Sep 22 2016

nonn

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

Column k=5 of A276921.

Cf. A110038.

a:= proc(n) option remember; `if`(n=0, 1, add(
       a(n-i)*binomial(n, i), i=1..min(n, 5)))
    end:
seq(a(n), n=0..25);

max = 25; CoefficientList[1/(1-Sum[x^i/i!, {i, 1, 5}]) + O[x]^(max+1), x]* Range[0, max]! (* Jean-François Alcover, May 24 2018 *)

E.g.f.: 1/(1-Sum_{i=1..5} x^i/i!).

A151509 The triangle in A151338 read by rows downwards.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 7, 6, 1, 0, 1, 15, 25, 10, 1, 0, 0, 31, 90, 65, 15, 1, 0, 0, 56, 301, 350, 140, 21, 1, 0, 0, 91, 938, 1701, 1050, 266, 28, 1, 0, 0, 126, 2737, 7686, 6951, 2646, 462, 36, 1, 0, 0, 126, 7455, 32725, 42315, 22827, 5880, 750, 45, 1, 0, 0, 0, 18711, 132055

Offset: 0

N. J. A. Sloane, May 14 2009

The Bell transform of the sequence "g(n) = 1 if n < 5, otherwise 0". For the definition of the Bell transform see A264428. - Peter Luschny, Jan 19 2016

			Triangle begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  3,   1;
  0, 1,  7,   6,    1;
  0, 1, 15,  25,   10,    1;
  0, 0, 31,  90,   65,   15,   1;
  0, 0, 56, 301,  350,  140,  21,  1;
  0, 0, 91, 938, 1701, 1050, 266, 28, 1;

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009 (see Table 6 E4(n,k) page 15).

Cf. A110038 (row sums), A122848, A111246, A144644, A151511.

rows = 10;
BellMatrix[f_Function | f_Symbol, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
B = BellMatrix[If[# < 5, 1, 0]&, rows];
Table[B[[n, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 14 2018, after Peter Luschny *)

# uses[bell_matrix from A264428]
bell_matrix(lambda n: 1 if n<5 else 0, 12) # Peter Luschny, Jan 19 2016

Bivariate e.g.f A151509(x,t) = Sum_{n>=0, k>=0} T(n,k)*x^n*t^k/n! = exp(t*G5(x)), where G5(x) = Sum_{i=1..5} x^i/i! is the e.g.f. of column 1. - R. J. Mathar, May 28 2019

Row 9 added by Michel Marcus, Feb 13 2014

More rows from R. J. Mathar, May 28 2019

A110089 Smallest prime beginning (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

11, 3, 2, 509, 2, 89, 16651, 15514861, 85864769, 26089808579, 665043081119, 554688278429, 758083947856951, 95405042230542329, 69257563144280941

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); and the first and/or last term may be involved in a chain of the other kind (i.e. the chain may be connected to another one). a(1)-a(8) computed by Gilles Sadowski.

			a(1)=11 because 2, 3, 5 and 7 are included in longer chains than one prime long; and 11 (although included in a <2p+1> chain) has no prime connection through <2p-1>.
a(2)=3 because 3 begins (through 2p+1>) the first complete two primes chain: 3-> 7 (even if 3 and 7 are also part of two others chains, but through <2p-1>).
a(3)=2 because (although 2 begins also a five primes chain through <2p+1>) it begins, through <2p-1>, the first complete three primes chain encountered: 2->3->5.

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

a(n) = min(A005602(n), A005603(n)). - R. J. Mathar, Jul 23 2008

a(8)-a(13) via A005602, A005603 from R. J. Mathar, Jul 23 2008

a(14)-a(15) via A005602, A005603 from Jason Yuen, Sep 03 2024

A110092 Smallest prime ending (through <2+1> or <2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

17, 59, 73, 4079, 47, 2879, 1065601

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); and the first and/or last term may not be involved in a chain of the other kind (i.e. the chain may not be connected to another one).

			a(1)=17 because 2, 3, 5, 7, 11 and 13 are part of longer chains whatever the operator; 17 is the first completely isolated prime.
a(2)=59 because it ends the first two primes chain not connected to another one: 29->59.

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, Cf. A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

Terms computed by Gilles Sadowski.

A110093 Smallest prime ending (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Original entry on oeis.org

11, 7, 5, 4079, 47, 2879, 1065601

Offset: 1

Alexandre Wajnberg, Sep 04 2005

The word "complete" indicates each chain is exactly n primes long for the operator in function (i.e. the chain cannot be a subchain of another one); but the first and/or last term may be involved in a chain of the other kind (i.e. the chain may be connected to another one).

			a(1)=11 because 2, 3, 5 and 7 are not ending chains; or are part of chains longer than one prime; 11, although is part of a five primes <2p+1> chain, is isolated through <2p-1>.
a(2)=7 because 7 ends through <2p+1> the first two primes chain: 3->7 (even if both primes are also part of <2p-1> chains).

Chris Caldwell's Prime Glossary, Cunningham chains.

Cf. A023272, A023302, A023330, A005384, A005385, A059452, A059455, A007700, Cf. A059759, A059760, A059761, A059762, A059763, A059764, A059765, A038397, A104349, A091314, A069362, A016093, A014937, A057326, A110059, A110056, A110038, A059766, A110027, A059764, A110025, A110024, A059763, A110022, A109998, A109946, A109927, A109835, A005603.

Terms computed by Gilles Sadowski.

cp's OEIS Frontend

A080510 Triangle read by rows: T(n,k) gives the number of set partitions of {1,...,n} with maximum block length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A229223 Number G(n,k) of set partitions of {1,...,n} into sets of size at most k; triangle G(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A148092 The partition function G(n,6).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276925 Number of ordered set partitions of [n] with at most five elements per block.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A151509 The triangle in A151338 read by rows downwards.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A110089 Smallest prime beginning (through <*2+1> or/and <*2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A110092 Smallest prime ending (through <*2+1> or <*2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A110093 Smallest prime ending (through <*2+1> or/and <*2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

Views

A110089 Smallest prime beginning (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.

A110092 Smallest prime ending (through <2+1> or <2-1> separately) a complete Cunningham chain (of the first or the second kind) of length n.

A110093 Smallest prime ending (through <2+1> or/and <2-1>) a complete Cunningham chain (of the first or the second kind) of length n.