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

A276921 Number A(n,k) of ordered set partitions of [n] with at most k elements per block; 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, 12, 24, 0, 1, 1, 3, 13, 66, 120, 0, 1, 1, 3, 13, 74, 450, 720, 0, 1, 1, 3, 13, 75, 530, 3690, 5040, 0, 1, 1, 3, 13, 75, 540, 4550, 35280, 40320, 0, 1, 1, 3, 13, 75, 541, 4670, 45570, 385560, 362880, 0

Offset: 0

Alois P. Heinz, 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,    12,    13,    13,    13,    13,    13, ...
  0,   24,    66,    74,    75,    75,    75,    75, ...
  0,  120,   450,   530,   540,   541,   541,   541, ...
  0,  720,  3690,  4550,  4670,  4682,  4683,  4683, ...
  0, 5040, 35280, 45570, 47110, 47278, 47292, 47293, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.

Columns k=0..10 give: A000007, A000142, A080599, A189886, A276924, A276925, A276926, A276927, A276928, A276929, A276930.
Main diagonal gives A000670.
Cf. A276922.

A:= proc(n, k) option remember; `if`(n=0, 1, add(
       A(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

A[n_, k_] := A[n, k] = If[n==0, 1, Sum[A[n-i, k]*Binomial[n, i], {i, 1, Min[n, k]}]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 03 2017, translated from Maple *)

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

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

A335508 Number of patterns of length n matching the pattern (1,1,1).

Original entry on oeis.org

0, 0, 0, 1, 9, 91, 993, 12013, 160275, 2347141, 37496163, 649660573, 12142311195, 243626199181, 5224710549243, 119294328993853, 2889836999693355, 74037381200415901, 2000383612949821323, 56850708386783835133, 1695491518035158123115, 52949018580275965241821

Offset: 0

Gus Wiseman, Jun 18 2020

nonn

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(3) = 1 through a(4) = 9 patterns:
  (1,1,1)  (1,1,1,1)
           (1,1,1,2)
           (1,1,2,1)
           (1,2,1,1)
           (1,2,2,2)
           (2,1,1,1)
           (2,1,2,2)
           (2,2,1,2)
           (2,2,2,1)

Alois P. Heinz, Table of n, a(n) for n = 0..424
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The complement A080599 is the avoiding version.
Permutations of prime indices matching this pattern are counted by A335510.
Compositions matching this pattern are counted by A335455 and ranked by A335512.
Patterns are counted by A000670 and ranked by A333217.
Patterns matching the pattern (1,1) are counted by A019472.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matching (1,2,3) are counted by A335515.
Cf. A034691, A056986, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.
Cf. A276922.

b:= proc(n, k) option remember; `if`(n=0, 1, add(
      b(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
a:= n-> b(n$2)-b(n, 2):
seq(a(n), n=0..21);  # Alois P. Heinz, Jan 28 2024

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{_,x_,_,x_,_,x_,_}]&]],{n,0,6}]

a(n) = Sum_{k=3..n} A276922(n,k). - Alois P. Heinz, Jan 28 2024

a(n) = A000670(n) - A080599(n). - Andrew Howroyd, Jan 28 2024

a(9)-a(21) from Alois P. Heinz, Jan 28 2024

A276923 Number of ordered set partitions of [2n] where the maximal block size equals n.

Original entry on oeis.org

1, 2, 42, 860, 21490, 657972, 24011988, 1017804216, 49118959890, 2657929522820, 159340977018652, 10480673825750856, 750335572490293972, 58077997318270046600, 4832536579295065540200, 430136064463753547944560, 40779223639911413185024530

Offset: 0

Alois P. Heinz, Sep 22 2016

nonn

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

Cf. A276922, A276961.

A:= proc(n, k) option remember; `if`(n=0, 1, add(
       A(n-i, k)*binomial(n, i), i=1..min(n, k)))
    end:
a:= n-> A(2*n, n) -`if`(n=0, 0, A(2*n, n-1)):
seq(a(n), n=0..20);

A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[A[n - i, k]*Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := A[2*n, n] - If[n == 0, 0, A[2*n, n - 1]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 13 2018, translated from Maple *)

a(n) = A276922(2n,n).

a(n) ~ 2^(2*n-3/2) * n^(n+1) / (exp(n) * log(2)^(n+2)). - Vaclav Kotesovec, Sep 24 2016

A320758 Number of ordered set partitions of [n] where the maximal block size equals two.

Original entry on oeis.org

1, 6, 42, 330, 2970, 30240, 345240, 4377240, 61122600, 933055200, 15470254800, 277005128400, 5329454130000, 109681187616000, 2404894892400000, 55977698400624000, 1378748676601296000, 35829233832135744000, 979763376201049440000, 28124715476056399200000

Offset: 2

Alois P. Heinz, Oct 20 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..428

Column k=2 of A276922.

Cf. A000142, A080599.

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

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 2}, b[n, k] - b[n, k-1]];
a /@ Range[2, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

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

A(n) = A080599(n) - A000142(n).

A320759 Number of ordered set partitions of [n] where the maximal block size equals three.

Original entry on oeis.org

1, 8, 80, 860, 10290, 136080, 1977360, 31365600, 539847000, 10026139200, 199937337600, 4262167509600, 96744738090000, 2329950823200000, 59348032327584000, 1594257675506496000, 45047749044458160000, 1335740755933584000000, 41473196779273459200000

Offset: 3

Alois P. Heinz, Oct 20 2018

nonn

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

Column k=3 of A276922.

Cf. A080599, A189886.

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

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 3}, b[n, k] - b[n, k-1]];
a /@ Range[3, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

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

a(n) = A189886(n) - A080599(n).

A320760 Number of ordered set partitions of [n] where the maximal block size equals four.

Original entry on oeis.org

1, 10, 120, 1540, 21490, 326970, 5402250, 96500250, 1855334250, 38228190000, 840776937000, 19666511865000, 487617137007000, 12776791730703000, 352825452012033000, 10242418813814187000, 311854958169459705000, 9937942309809373860000, 330821844137019184950000

Offset: 4

Alois P. Heinz, Oct 20 2018

nonn

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

Column k=4 of A276922.

Cf. A189886, A276924.

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

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 4}, b[n, k] - b[n, k-1]];
a /@ Range[4, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

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

a(n) = A276924(n) - A189886(n).

A320761 Number of ordered set partitions of [n] where the maximal block size equals five.

Original entry on oeis.org

1, 12, 168, 2464, 38808, 657972, 11997216, 234594360, 4903616718, 109205019924, 2582909885556, 64686057980544, 1710536977653504, 47637803779229664, 1393903719674129664, 42758329987344875904, 1372254504736418142840, 45989719374155059863360

Offset: 5

Alois P. Heinz, Oct 20 2018

nonn

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

Column k=5 of A276922.

Cf. A276924, A276925.

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

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[b[n - i, k] Binomial[n, i], {i, 1, Min[n, k]}]];
a[n_] := With[{k = 5}, b[n, k] - b[n, k-1]];
a /@ Range[5, 25] (* Jean-François Alcover, Dec 14 2020, after Alois P. Heinz *)

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

a(n) = A276925(n) - A276924(n).

A320762 Number of ordered set partitions of [n] where the maximal block size equals six.

Original entry on oeis.org

1, 14, 224, 3696, 64680, 1206744, 24011988, 508864356, 11459682234, 273563089800, 6904861371408, 183819838041840, 5149305370473264, 151447801937560128, 4666989813249123360, 150394712706368466336, 5059062167993588722968, 177346570951333803395376

Offset: 6

Alois P. Heinz, Oct 20 2018

nonn

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

Column k=6 of A276922.

Cf. A276925, A276926.

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

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

a(n) = A276926(n) - A276925(n).

A320763 Number of ordered set partitions of [n] where the maximal block size equals seven.

Original entry on oeis.org

1, 16, 288, 5280, 101640, 2068704, 44595408, 1017804216, 24559319070, 625388375040, 16772475939648, 472802783660064, 13981054231585584, 432866241024085440, 14006847775868101440, 472893544571144089536, 16631451859811919417144, 608402197372214335559040

Offset: 7

Alois P. Heinz, Oct 20 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..425

Column k=7 of A276922.

Cf. A276926, A276927.

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

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

a(n) = A276927(n) - A276926(n).

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

A276921 Number A(n,k) of ordered set partitions of [n] with at most k elements per block; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335508 Number of patterns of length n matching the pattern (1,1,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A276923 Number of ordered set partitions of [2n] where the maximal block size equals n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320758 Number of ordered set partitions of [n] where the maximal block size equals two.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320759 Number of ordered set partitions of [n] where the maximal block size equals three.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320760 Number of ordered set partitions of [n] where the maximal block size equals four.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320761 Number of ordered set partitions of [n] where the maximal block size equals five.

Views

Author