A276719 -id:A276719 - cp's OEIS frontend

A276727 Number T(n,k) of set partitions of [n] where k is minimal such that for each block b the smallest integer interval containing b has at most k elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 4, 5, 5, 0, 1, 7, 12, 17, 15, 0, 1, 12, 29, 45, 64, 52, 0, 1, 20, 66, 121, 201, 265, 203, 0, 1, 33, 145, 336, 585, 966, 1197, 877, 0, 1, 54, 315, 901, 1741, 3172, 4971, 5852, 4140, 0, 1, 88, 676, 2347, 5375, 10100, 18223, 27267, 30751, 21147

Offset: 0

Alois P. Heinz, Sep 16 2016

			T(4,1) = 1: 1|2|3|4.
T(4,2) = 4: 12|34, 12|3|4, 1|23|4, 1|2|34.
T(4,3) = 5: 123|4, 13|24, 13|2|4, 1|234, 1|24|3.
T(4,4) = 5: 1234, 124|3, 134|2, 14|23, 14|2|3.
T(5,4) = 17: 1234|5, 124|35, 124|3|5, 134|25, 134|2|5, 13|245, 13|25|4, 14|235, 14|23|5, 1|2345, 1|235|4, 14|25|3, 14|2|35, 14|2|3|5, 1|245|3, 1|25|34, 1|25|3|4.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  2,   2;
  0, 1,  4,   5,   5;
  0, 1,  7,  12,  17,  15;
  0, 1, 12,  29,  45,  64,  52;
  0, 1, 20,  66, 121, 201, 265,  203;
  0, 1, 33, 145, 336, 585, 966, 1197, 877;
  ...

Alois P. Heinz, Rows n = 0..20, flattened

Columns k=0-10 give: A000007, A057427, A000071(n+1), A320553, A320554, A320555, A320556, A320557, A320558, A320559, A320560.
Row sums give A000110.
Main diagonal gives A000110(n-1) for n>0.
T(2n,n) gives A276728.
Cf. A263757, A276719, A276891.

b:= proc(n, m, l) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j), [subsop(1=NULL, l)[],
      `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))
    end:
A:= (n, k)-> `if`(n=0, 1, `if`(k<2, k, b(n, 0, [0$(k-1)]))):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

b[n_, m_, l_List] := b[n, m, l] = If[n == 0, 1, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[n == 0, 1, If[k < 2, k, b[n, 0, Array[0&, k - 1]]]]; T [n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]]; Table[T[n, k], {n, 0, 12}, { k, 0, n}] // Flatten (* Jean-François Alcover, Feb 04 2017, translated from Maple *)

T(n,k) = A276719(n,k) - A276719(n,k-1) for k>0, T(n,0) = A000007(n).

A276890 Number A(n,k) of ordered set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 3, 6, 0, 1, 1, 3, 10, 24, 0, 1, 1, 3, 13, 44, 120, 0, 1, 1, 3, 13, 62, 234, 720, 0, 1, 1, 3, 13, 75, 352, 1470, 5040, 0, 1, 1, 3, 13, 75, 466, 2348, 10656, 40320, 0, 1, 1, 3, 13, 75, 541, 3272, 17880, 87624, 362880, 0

Offset: 0

Alois P. Heinz, Sep 21 2016

Column k > 0 is asymptotic to exp(k-1) * n!. - Vaclav Kotesovec, Sep 22 2016

			Square array A(n,k) begins:
  1,    1,     1,     1,     1,     1,     1,     1, ...
  0,    1,     1,     1,     1,     1,     1,     1, ...
  0,    2,     3,     3,     3,     3,     3,     3, ...
  0,    6,    10,    13,    13,    13,    13,    13, ...
  0,   24,    44,    62,    75,    75,    75,    75, ...
  0,  120,   234,   352,   466,   541,   541,   541, ...
  0,  720,  1470,  2348,  3272,  4142,  4683,  4683, ...
  0, 5040, 10656, 17880, 26032, 34792, 42610, 47293, ...

Alois P. Heinz, Antidiagonals n = 0..42, flattened

Columns k=0-10: A000007, A000142, A240172, A276893, A276894, A276895, A276896, A276897, A276898, A276899, A276900.
Main diagonal gives: A000670.
Cf. A276719, A276891.

b:= proc(n, m, l) option remember; `if`(n=0, m!,
      add(b(n-1, max(m, j), [subsop(1=NULL, l)[],
      `if`(j<=m, 0, j)]), j={l[], m+1} minus {0}))
    end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0),
             `if`(k=1, n!, b(n, 0, [0$(k-1)]))):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, m_, l_List] := b[n, m, l] = If[n == 0, m!, Sum[b[n - 1, Max[m, j], Append[ReplacePart[l, 1 -> Nothing], If[j <= m, 0, j]]], {j, Append[l, m + 1] ~Complement~ {0}}]]; A[n_, k_] := If[k==0, If[n==0, 1, 0], If[k==1, n!, b[n, 0, Array[0&, k-1]]]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 06 2017, after Alois P. Heinz *)

A(n,k) = Sum_{j=0..k} A276891(n,j).

A276837 Number A(n,k) of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 6, 5, 1, 0, 1, 1, 2, 6, 12, 8, 1, 0, 1, 1, 2, 6, 24, 25, 13, 1, 0, 1, 1, 2, 6, 24, 60, 57, 21, 1, 0, 1, 1, 2, 6, 24, 120, 150, 124, 34, 1, 0, 1, 1, 2, 6, 24, 120, 360, 399, 268, 55, 1, 0

Offset: 0

Alois P. Heinz, Sep 20 2016

The sequence of column k satisfies a linear recurrence with constant coefficients of order 2^(k-1) for k>0.

			Square array A(n,k) begins:
  1, 1,  1,   1,    1,    1,    1,     1,     1, ...
  0, 1,  1,   1,    1,    1,    1,     1,     1, ...
  0, 1,  2,   2,    2,    2,    2,     2,     2, ...
  0, 1,  3,   6,    6,    6,    6,     6,     6, ...
  0, 1,  5,  12,   24,   24,   24,    24,    24, ...
  0, 1,  8,  25,   60,  120,  120,   120,   120, ...
  0, 1, 13,  57,  150,  360,  720,   720,   720, ...
  0, 1, 21, 124,  399, 1050, 2520,  5040,  5040, ...
  0, 1, 34, 268, 1145, 3192, 8400, 20160, 40320, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019

Columns k=0-10 give: A000007, A000012, A000045(n+1), A214663, A276838, A276839, A276840, A276841, A276842, A276843, A276844.
Main diagonal gives A000142.
Cf. A263757, A276719.

A(n,k+1) - A(n,k) = A263757(n,k) for n>0.

A129847 a(n) = number of set partitions of {1, 2, ..., n} whose blocks consist only of elements that differ by two or less (that is, have only the forms {i}, {i,i+1}, {i,i+2}, or {i,i+1,i+2}).

Original entry on oeis.org

1, 1, 2, 5, 10, 20, 42, 87, 179, 370, 765, 1580, 3264, 6744, 13933, 28785, 59470, 122865, 253838, 524428, 1083466, 2238435, 4624595, 9554390, 19739321, 40781336, 84254032, 174068400, 359624425, 742982225, 1534997482, 3171296957, 6551883314, 13536157460

Offset: 0

Rhodes Peele (rpeele(AT)mail.aum.edu), May 22 2007

(1) Bryce Duncan and I found this sequence while studying a graph invariant we call the Bell number. For a simple graph G = (V,E), we define B(G) to be the number of partitions P of V in which each block of P is an independent set of G. The sequence considered here results from choosing V = {1, 2, ..., n} and E = {(i,j) : |i - j| > 2}. (The classical Bell numbers B(n) come from the edgeless graph on n vertices.)
(2) The constant r in the formula is the dominant root of the characteristic equation of a linear homogeneous recurrence relation that also defines {a(n)}. (This recurrence relation, along with initial conditions, appears in the Mathematica program given below. The formula for a(n) is analogous to one version of the Binet formula for the Fibonacci numbers, namely F(n) = the integer nearest to (1/sqrt(5)) p^n where p is the golden mean. The shifted Fibonacci numbers F(n+1) are also graphical Bell numbers: replace the condition |i - j| > 2 with |i - j| > 1 to obtain them.
(3) Bell numbers for simple graphs satisfy the deletion-contraction identity B(G) = B(G\e) - B(G/e), but not the product identity B(G union H) = B(G)B(H) for disjoint graphs G and H. However, we do have B(B join H) = B(G)B(H) for the join of graphs G and H. The join graph G join H results from adding to their disjoint union, all possible edges that join a vertex of G to a vertex of H.
Diagonal sums of triangle A158687. - Paul Barry, Mar 24 2009
a(n) is the number of compositions (ordered partitions) of n into parts 1, 2, 3, and 4 where there are two kinds of part 3. - Joerg Arndt, Sep 16 2016
a(n) is the number of ways to tile a skew double-strip of n cells using squares, "double", and "triangular triple" tiles. Here is the skew double-strip corresponding to n=12, with 12 cells:
   _ ___ _ ___ _ ___
  |   |   |   |   |   |   |
 |__|___|_|___| |___|
|   |   |   |   |   |   |
|_|___|_|___|_|___|,
and here are the three possible "double" tiles and two possible "triangular triple" tiles:
   _    _                     _      _____
  |   |  |   |                   |   |    |       |
 |  |  |  |     _____     |   |   |     |
|   |      |   |   |       |   |       |    |   |
|_|,     |_|,  |_____|,  |_____|,   |_|
As an example, here is one of the b(12) = 3264 ways to tile the skew double-strip of 12 cells:
   _ ___ _____ _______
  |   |   |       |   |   |
 |__|_  |    |   | _|
|       |   |   |       |
|_____|___|_|___ _|. - Greg Dresden and Ruotong Li, Jun 12 2024

			a(4) = 10, with set partitions {{1},{2},{3}, {4}}; {{1,2}, {3}, {4}}; {{1,3}, {2}, {4}}; {{1}, {2,3}, {4}}; {{1}, {2,4}, {3}}; {{1}, {2}, {3,4}}; {{1,2,3}, {4}}; {{1}, {2,3,4}}; {{1,2}, {3,4}} and {{1,3}, {2,4}}.

Herbert S. Wilf, Generatingfunctiononogy (2nd Edition), Academic Press 1990, pp. 1 - 10 and pp. 20 - 23.
Arthur T. Benjamin and Jennifer J. Quinn, Proofs that Really Count, Dolciani Mathematical Expositions (MAA), (2003), p. 1. (A relevant combinatorial interpretation of Fibonacci numbers.)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Cyclic permutations avoiding patterns in both one-line and cycle forms, arXiv:2312.05145 [math.CO], 2023. See p. 2.
B. Duncan and R. Peele, Bell and Stirling numbers for graphs, JIS 12 (2009), Article 09.7.1.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, Mathematics of Computation 87 (2018), 987-1011.

Cf. A000110, A000045, A141073, A158687, A276893.

Column k=3 of A276719.

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|2|1|1>>^n)[4, 4]:
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 15 2016

a[1] = 1; a[2] = 2; a[3] = 5; a[4] = 10
a[n_] := a[n] = a[n-1] + a[n-2] + 2 a[n-3] + a[n-4]
Table[a[n],{n,1,30}]

a(n) = the integer nearest to s r^n, where r = 2.0659948920 ... and s = 0.53979687305... . (More information in comment (2).)
a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-2k} C(n-j-k,k)*C(2k,j). - Paul Barry, Mar 24 2009
G.f.: 1/(1 - x - x^2 - 2*x^3 - x^4). - Colin Barker, May 02 2012
a(n) = a(n-1) + a(n-2) + 2*(n-3) + a(n-4) with a(0) = a(1) = 1, a(2) = 2, a(3) = 5. - Taras Goy, Aug 04 2017
a(2*n) = a(n)^2 - a(n-1)^2 + a(n-2)^2 + 2*a(n-1)*(a(n+1)-a(n)). - Greg Dresden, Jul 03 2024

a(0)=1 prepended by Alois P. Heinz, Sep 15 2016

A276720 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most four elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 37, 87, 208, 515, 1271, 3112, 7594, 18578, 45510, 111464, 272839, 667809, 1634784, 4002217, 9797781, 23985131, 58715973, 143739040, 351879841, 861416293, 2108779100, 5162371032, 12637686756, 30937555540, 75736343956, 185405513889, 453879917561

Offset: 0

Alois P. Heinz, Sep 16 2016

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

Column k=4 of A276719.

Cf. A276838, A276894.

G.f.: -(x-1)*(x+1)/(x^8+3*x^7-5*x^5-5*x^4-x^3-2*x^2-x+1).

A276721 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most five elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 151, 409, 1100, 3012, 8487, 23949, 67179, 187431, 521889, 1455667, 4066220, 11363476, 31747666, 88659265, 247559056, 691294366, 1930595096, 5391864630, 15058449487, 42054270461, 117445036871, 327989716409, 915985822220, 2558107420307

Offset: 0

Alois P. Heinz, Sep 16 2016

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

Column k=5 of A276719.

Cf. A276839, A276895.

G.f.: -(x^8 +x^6 +3*x^5 +2*x^3 +x^2 -1)/((x+1) *(x^15 +3*x^14 -x^13 +5*x^12 +15*x^11 +14*x^10 +9*x^9 +13*x^8 -17*x^7 -7*x^6 -21*x^5 -3*x^3 -2*x +1)).

A276722 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most six elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 674, 2066, 6184, 18587, 56867, 178317, 561319, 1760125, 5489888, 17057701, 52931331, 164466672, 511758485, 1593612234, 4962950389, 15451453190, 48088784307, 149640967002, 465653853729, 1449146745582, 4510183339086, 14037494547193

Offset: 0

Alois P. Heinz, Sep 16 2016

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

Column k=6 of A276719.

Cf. A276840, A276896.

G.f.: -(x^22 -x^19 -15*x^18 +7*x^17 +18*x^16 +11*x^14 -22*x^13 -26*x^12 -10*x^11 +2*x^10 -28*x^9 +3*x^8 +16*x^7 +14*x^6 -5*x^5 +5*x^4 +5*x^3 +2*x^2 -1) / (x^32 +5*x^31 +x^30 -5*x^29 -6*x^28 -111*x^27 -210*x^26 +52*x^25 +263*x^24 +85*x^23 -346*x^22 -882*x^21 -401*x^20 +584*x^19 +382*x^18 -1058*x^17 -1319*x^16 -200*x^15 +250*x^14 +382*x^13 +589*x^12 +716*x^11 +346*x^10 +49*x^9 -137*x^8 -146*x^7 -84*x^6 -3*x^5 -4*x^4 -5*x^3 -3*x^2 -x +1).

A276723 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most seven elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 3263, 11155, 36810, 120635, 398736, 1340561, 4605989, 15908448, 54826671, 188085307, 642431001, 2188102307, 7446095610, 25366540627, 86531467800, 295449388797, 1009134603216, 3446558809107, 11767813404774, 40167156826109

Offset: 0

Alois P. Heinz, Sep 16 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Wikipedia, Partition of a set

Column k=7 of A276719.

Cf. A276841, A276897.

G.f.: -(x^52 +2*x^50 -9*x^49 +5*x^48 +93*x^47 -46*x^46 -18*x^45 -439*x^44 +166*x^43 +919*x^42 -369*x^41 +1431*x^40 -2154*x^39 +1497*x^38 +2366*x^37 +7382*x^36 +4861*x^35 +3348*x^34 -12721*x^33 +1916*x^32 -7481*x^31 +8799*x^30 +8061*x^29 +10105*x^28 -8760*x^27 +3274*x^26 -9925*x^25 -873*x^24 +8803*x^23 +13626*x^22 -2818*x^21 +2263*x^20 +3291*x^19 -5707*x^18 -3550*x^17 -4115*x^16 -2399*x^15 -2475*x^14 -877*x^13 +461*x^12 +130*x^11 +226*x^10 +182*x^9 +243*x^8 +161*x^7 -4*x^6 +21*x^5 +14*x^4 +5*x^3 +2*x^2 -1) / (x^64 +6*x^63 +3*x^62 -2*x^61 -24*x^60 +7*x^59 +981*x^58 +2410*x^57 +1066*x^56 -2882*x^55 -8931*x^54 -2882*x^53 -4007*x^52 -30225*x^51 -9863*x^50 +20863*x^49 +101214*x^48 +127153*x^47 +158805*x^46 +285147*x^45 +101665*x^44 -513829*x^43 -895778*x^42 -800589*x^41 -572933*x^40 +290605*x^39 +232843*x^38 -841969*x^37 -1610201*x^36 -1642130*x^35 -1731114*x^34 -642745*x^33 +245579*x^32 -62183*x^31 -769603*x^30 -803729*x^29 -905469*x^28 -727539*x^27 -323095*x^26 -229154*x^25 -442563*x^24 -447061*x^23 -251676*x^22 -41018*x^21 -74736*x^20 -74741*x^19 +35465*x^18 +81095*x^17 +72575*x^16 +39983*x^15 +23409*x^14 +14506*x^13 +3868*x^12 -628*x^11 -1927*x^10 -1426*x^9 -935*x^8 -468*x^7 -31*x^6 -20*x^5 -13*x^4 -5*x^3 -3*x^2 -x +1).

A276724 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most eight elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 17007, 64077, 231180, 821132, 2918753, 10483154, 38264066, 142423894, 533308705, 1995314365, 7437442700, 27604521795, 102095937121, 376790770192, 1389739254904, 5130664114644, 18964932885093, 70170215134155, 259770146382666

Offset: 0

Alois P. Heinz, Sep 16 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alois P. Heinz, G.f. for A276724
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Wikipedia, Partition of a set

Column k=8 of A276719.

Cf. A276842, A276898.

G.f.: see link above.

A276725 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most nine elements.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 94828, 389946, 1527058, 5846917, 22257299, 85116719, 329147169, 1292371138, 5165744159, 20781403539, 83617668276, 335483033770, 1340729704086, 5338181115652, 21193583922048, 84001778063348, 332811761809618

Offset: 0

Alois P. Heinz, Sep 16 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..512
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Wikipedia, Partition of a set

Column k=9 of A276719.

Cf. A276843, A276899.

cp's OEIS Frontend

A276727 Number T(n,k) of set partitions of [n] where k is minimal such that for each block b the smallest integer interval containing b has at most k elements; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276890 Number A(n,k) of ordered set partitions of [n] such that for each block b the smallest integer interval containing b has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276837 Number A(n,k) of permutations of [n] such that for each cycle c the smallest integer interval containing all elements of c has at most k elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129847 a(n) = number of set partitions of {1, 2, ..., n} whose blocks consist only of elements that differ by two or less (that is, have only the forms {i}, {i,i+1}, {i,i+2}, or {i,i+1,i+2}).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A276720 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most four elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276721 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most five elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276722 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most six elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276723 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most seven elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A276724 Number of set partitions of [n] such that for each block b the smallest integer interval containing b has at most eight elements.

Views

Author

Keywords

Links