A001680 -id:A001680 - cp's OEIS frontend

A111246 Triangle read by rows: a(n,k) = number of partitions of an n-set into exactly k nonempty subsets, each of size <= 3.

1, 1, 1, 1, 3, 1, 0, 7, 6, 1, 0, 10, 25, 10, 1, 0, 10, 75, 65, 15, 1, 0, 0, 175, 315, 140, 21, 1, 0, 0, 280, 1225, 980, 266, 28, 1, 0, 0, 280, 3780, 5565, 2520, 462, 36, 1, 0, 0, 0, 9100, 26145, 19425, 5670, 750, 45, 1, 0, 0, 0, 15400, 102025, 125895, 56595, 11550, 1155

Offset: 1

Ji Young Choi, Oct 31 2005

a(n,k) = 0 if k > n; a(n,k) = 0 if n > 0 and k < 0; a(n,k) can be extended to negative n and k, just as the Stirling numbers or Pascal's triangle can be extended. The present triangle is called the tri-restricted Stirling numbers of the second kind.

Also the Bell transform of the sequence "a(n) = 1 if n<3 else 0". For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			a(1,1)=1;
a(2,1)=1; a(2,2)=1;
a(3,1)=1; a(3,2)=3; a(3,3)=1;
a(4,1)=0; a(4,2)=7; a(4,3)=6; a(4,4)=1;
a(5,1)=0; a(5,2)=10; a(5,3)=25; a(5,4)=10; a(5,5)=1;
a(6,1)=0; a(6,2)=10; a(6,3)=75; a(6,4)=65; a(6,5)=15; a(6,6)=1; ...

J. Y. Choi and J. D. H. Smith, On the combinatorics of multi-restricted numbers, Ars. Com., 75(2005), pp. 44-63.

J. Y. Choi and J. D. H. Smith, The Tri-restricted Numbers and Powers of Permutation Representations, J. Comb. Math. Comb. Comp. 42 (2002), 113-125.
J. Y. Choi and J. D. H. Smith, On the Unimodality and Combinatorics of the Bessel Numbers, Discrete Math., 264 (2003), 45-53.
J. Y. Choi et al., Reciprocity for multirestricted Stirling numbers, J. Combin. Theory 113 A (2006), 1050-1060.

A144385 and A144402 are other versions of this same triangle.

Cf. A001680, A008277 (Stirling numbers).

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0,...) as column 0.
BellMatrix(n -> `if`(n<3,1,0), 10); # Peter Luschny, Jan 27 2016

BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
M = BellMatrix[If[# < 3, 1, 0]&, rows];
Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 24 2018, after Peter Luschny *)

row(n) = {x='x+O('x^(n+1)); polcoeff(serlaplace(exp(y*(x+x^2/2+x^3/6))), n, 'x); }
tabl(nn) = for(n=1, nn, print(Vecrev(row(n)/y))) \\ Jinyuan Wang, Dec 21 2019

a(n, k) = a(n-1, k-1) + k*a(n-1, k) - binomial(n-1, 3)*a(n-4, k-1).
G.f. = Sum_{k_1+k_2+k_3=k, k_1+ 2k_2+3k_3=n} frac{n!}{(1!)^{k_1}(2!)^{k_2}(3!)^{k_3}k_1!k_2!k_3!}.
E.g.f.: exp(y*(x+x^2/2+x^3/6)). - Vladeta Jovovic, Nov 01 2005

More terms from Vladeta Jovovic, Nov 01 2005

Recurrence, offset and example corrected by David Applegate, Jan 16 2009

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

A323951 Number of ways to split an n-cycle into connected subgraphs, all having at least three vertices.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 4, 8, 13, 22, 36, 56, 86, 131, 197, 294, 437, 647, 955, 1407, 2070, 3042, 4467, 6556, 9618, 14106, 20684, 30325, 44455, 65164, 95515, 139997, 205189, 300733, 440760, 645980, 946745, 1387538, 2033552, 2980332, 4367906, 6401495, 9381865, 13749810

Offset: 0

Gus Wiseman, Feb 10 2019

			The a(3) = 1 through a(7) = 8 partitions:
  {{123}}  {{1234}}  {{12345}}  {{123456}}    {{1234567}}
                                {{123}{456}}  {{123}{4567}}
                                {{126}{345}}  {{1234}{567}}
                                {{156}{234}}  {{1237}{456}}
                                              {{1267}{345}}
                                              {{127}{3456}}
                                              {{1567}{234}}
                                              {{167}{2345}}

Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Cf. A000325, A001610, A001680, A005251, A066982, A306351, A323950, A323952, A323954.

cycedsprop[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,i+k,n+i-1}]];
spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
Table[Length[spsu[cycedsprop[n,2],Range[n]]],{n,15}]

G.f.: (x^7-2*x^6+x^3-3*x^2+3*x-1)/((x^3+x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019

More terms from Alois P. Heinz, Feb 10 2019

A323953 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into singletons and connected subsequences of sizes > k.

Original entry on oeis.org

1, 2, 1, 5, 2, 1, 12, 6, 2, 1, 27, 12, 7, 2, 1, 58, 23, 14, 8, 2, 1, 121, 44, 23, 16, 9, 2, 1, 248, 82, 38, 26, 18, 10, 2, 1, 503, 149, 65, 38, 29, 20, 11, 2, 1, 1014, 267, 112, 57, 42, 32, 22, 12, 2, 1, 2037, 475, 189, 90, 57, 46, 35, 24, 13, 2, 1

Offset: 1

Gus Wiseman, Feb 10 2019

			Triangle begins:
     1
     2    1
     5    2    1
    12    6    2    1
    27   12    7    2    1
    58   23   14    8    2    1
   121   44   23   16    9    2    1
   248   82   38   26   18   10    2    1
   503  149   65   38   29   20   11    2    1
  1014  267  112   57   42   32   22   12    2    1
  2037  475  189   90   57   46   35   24   13    2    1
  4084  841  312  146   80   62   50   38   26   14    2    1
Row 4 counts the following connected partitions:
  {{1234}}        {{1234}}        {{1234}}        {{1}{2}{3}{4}}
  {{1}{234}}      {{1}{234}}      {{1}{2}{3}{4}}
  {{12}{34}}      {{123}{4}}
  {{123}{4}}      {{124}{3}}
  {{124}{3}}      {{134}{2}}
  {{134}{2}}      {{1}{2}{3}{4}}
  {{14}{23}}
  {{1}{2}{34}}
  {{1}{23}{4}}
  {{12}{3}{4}}
  {{14}{2}{3}}
  {{1}{2}{3}{4}}

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

First column is A000325. Second column is A323950.

Cf. A001610, A001680, A005251, A066982, A306351, A323951, A323952, A323954.

cyceds[n_,k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i,j]-1,n],{i,n},{j,Prepend[Range[i+k,n+i-1],i]}]];
spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
Table[Length[spsu[cyceds[n,k],Range[n]]],{n,10},{k,n}]

T(n,k) = {1 + if(kAndrew Howroyd, Jan 19 2023

T(n,k) = 2 - n + Sum_{i=1..floor(n/k)} n*binomial(n-i*k+i-1, 2*i-1)/i for 1 <= k < n. - Andrew Howroyd, Jan 19 2023

A188449 T(n,k)=Number of (n*k)Xk binary arrays with nonzero rows in decreasing order, no more than 3 ones in any row and exactly n ones in every column.

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 14, 8, 0, 0, 46, 66, 5, 0, 0, 166, 722, 139, 1, 0, 0, 652, 9955, 4944, 139, 0, 0, 0, 2780, 165252, 244490, 16683, 66, 0, 0, 0, 12644, 3221806, 15980350, 2876300, 30090, 14, 0, 0, 0, 61136, 72445292, 1330789145, 703845255, 18014566, 30090, 1, 0, 0

Offset: 1

R. H. Hardin Mar 31 2011

Table starts
.1.2.5..14....46.......166..........652...........2780...........12644
.0.1.8..66...722......9955.......165252........3221806........72445292
.0.0.5.139..4944....244490.....15980350.....1330789145....137418347276
.0.0.1.139.16683...2876300....703845255...235994839738.105035943170557
.0.0.0..66.30090..18014566..15978843654.20633840650794
.0.0.0..14.30090..64224371.203200240829
.0.0.0...1.16683.135725210
.0.0.0...0..4944
.0.0.0...0
.0.0.0

			All solutions for 9X3
..1..1..0....1..1..1....1..1..1....1..1..1....1..1..1
..1..0..1....1..1..0....1..1..0....1..0..1....1..1..0
..1..0..0....1..0..1....1..0..0....1..0..0....1..0..1
..0..1..1....0..1..1....0..1..1....0..1..1....0..1..0
..0..1..0....0..0..0....0..0..1....0..1..0....0..0..1
..0..0..1....0..0..0....0..0..0....0..0..0....0..0..0
..0..0..0....0..0..0....0..0..0....0..0..0....0..0..0
..0..0..0....0..0..0....0..0..0....0..0..0....0..0..0
..0..0..0....0..0..0....0..0..0....0..0..0....0..0..0

R. H. Hardin, Table of n, a(n) for n = 1..80

Row 1 is A001680

A229414 Number of set partitions of {1,...,3n} into sets of size at most 3.

Original entry on oeis.org

1, 5, 166, 12644, 1680592, 341185496, 97620050080, 37286121988256, 18280749571449664, 11168256342434121152, 8306264068494786829696, 7380771881944947770497280, 7715405978050522488223499776, 9365880670184268387214967727104, 13058232187415887547449498864463872

Offset: 0

Alois P. Heinz, Sep 22 2013

nonn

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

Row n=3 of A229243.

a:= proc(n) option remember; `if`(n<3, [1, 5, 166][n+1],
      ((108*n^2-72*n+4)*a(n-1)-6*(n-1)*(3*n-5)*(27*n^2-48*n+10)*a(n-2)
       +9*(n-1)*(n-2)*(3*n-1)*(3*n-7)*(3*n-5)*(3*n-8)*a(n-3))/8)
    end:
seq(a(n), n=0..20);

G[n_, k_] := G[n, k] = Module[{j, g}, Which[k > n, G[n, n], n == 0, 1, k < 1, 0, True, g = G[n - k, k]; For[j = k - 1, j >= 1, j--, g = g(n-j)/j + G[n - j, k]]; g]];
a[n_] := G[3n, 3];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 10 2020, after Alois P. Heinz in A229243 *)

a(n) = (3n)! * [x^(3n)] exp(x + x^2/2 + x^3/6).

a(n) = A001680(3n) = A229223(3n,3).

A014775 Expansion of exp ( - x - (1/2)x^2 - (1/6)x^3).

Original entry on oeis.org

1, -1, 0, 1, 2, -6, -14, 20, 204, 28, -2584, -6876, 33760, 219296, -121848, -6020456, -15177904, 126126960, 950679424, -898745392, -38731873824, -123922308896, 1126028191520, 10547325457536, -5093629711808

Offset: 0

N. J. A. Sloane

sign

Cf. A001464, A001680.

With[{nmax = 30}, CoefficientList[Series[Exp[-x - x^2/2 - x^3/6], {x, 0, nmax}], x] * Range[0, nmax]!] (* Vaclav Kotesovec, Feb 09 2020 *)

A108947 Triangle: T(n,k) is the partition function G(n-k,k).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 4, 2, 1, 1, 0, 1, 10, 5, 2, 1, 1, 0, 1, 26, 14, 5, 2, 1, 1, 0, 1, 76, 46, 15, 5, 2, 1, 1, 0, 1, 232, 166, 51, 15, 5, 2, 1, 1, 0, 1, 764, 652, 196, 52, 15, 5, 2, 1, 1, 0, 1, 2620, 2780, 827, 202, 52, 15, 5, 2, 1, 1

Offset: 0

Paul Boddington, Jul 21 2005

See entries for A001680 and A001681 for appropriate references.

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

Cf. A000110. First differences of a sequence G(k, 0), G(k, 1), ... give a row of A080510 (e.g., 0, 1, 10, 14, 15, 15, ... gives 1, 9, 4, 1).

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:
T:= (n, k)-> G(n-k, k):
seq(seq(T(n, k), k=0..n), n=0..12);  # 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}]]]; T[n_, k_] := G[n-k, k]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 24 2015, after Alois P. Heinz *)

E.g.f. for sequence G(0, k), G(1, k), ... is exp(x + (1/2)*x^2 + ... + (1/k!)*x^k).

One term corrected by Alois P. Heinz, Sep 15 2013

A144417 Triangle in A144385 read upwards by columns.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 6, 7, 0, 0, 1, 10, 25, 10, 0, 0, 1, 15, 65, 75, 10, 0, 0, 1, 21, 140, 315, 175, 0, 0, 0, 1, 28, 266, 980, 1225, 280, 0, 0, 0, 1, 36, 462, 2520, 5565, 3780, 280, 0, 0, 0, 1, 45, 750, 5670, 19425, 26145, 9100, 0, 0, 0, 0, 1, 55

Offset: 0

David Applegate and N. J. A. Sloane, Dec 07 2008

			Triangle begins:
1
1,0
1,1,0
1,3,1,0
1,6,7,0,0
1,10,25,10,0,0
1,15,65,75,10,0,0
1,21,140,315,175,0,0,0

Column sums give A001680. Cf. A144385.

A347666 E.g.f.: exp( exp(x) * (1 + x + x^2 / 2 + x^3 / 6) - 1 ).

Original entry on oeis.org

1, 2, 8, 40, 239, 1648, 12778, 109476, 1023520, 10341878, 112067820, 1294254184, 15847382977, 204827368606, 2784056034014, 39665514607872, 590684848605779, 9170941154737032, 148120725648168260, 2483657480026985432, 43157660169344697996, 775898068395820783674

Offset: 0

Ilya Gutkovskiy, Sep 10 2021

nonn

Exponential transform of A000125.

Cf. A000125, A001680, A209801, A347665.

nmax = 21; CoefficientList[Series[Exp[Exp[x] (1 + x + x^2/2 + x^3/6) - 1], {x, 0, nmax}], x] Range[0, nmax]!
a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 1, k - 1] ((k^3 + 5 k + 6)/6) a[n - k], {k, 1, n}]; Table[a[n], {n, 0, 21}]

a(0) = 1; a(n) = Sum_{k=1..n} binomial(n-1,k-1) * A000125(k) * a(n-k).

cp's OEIS Frontend

A111246 Triangle read by rows: a(n,k) = number of partitions of an n-set into exactly k nonempty subsets, each of size <= 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A148092 The partition function G(n,6).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A323951 Number of ways to split an n-cycle into connected subgraphs, all having at least three vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A323953 Regular triangle read by rows where T(n, k) is the number of ways to split an n-cycle into singletons and connected subsequences of sizes > k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A188449 T(n,k)=Number of (n*k)Xk binary arrays with nonzero rows in decreasing order, no more than 3 ones in any row and exactly n ones in every column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A229414 Number of set partitions of {1,...,3n} into sets of size at most 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A014775 Expansion of exp ( - x - (1/2)*x^2 - (1/6)*x^3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A108947 Triangle: T(n,k) is the partition function G(n-k,k).

Views

Author

Keywords

Comments

Links

A014775 Expansion of exp ( - x - (1/2)x^2 - (1/6)x^3).