A278984 -id:A278984 - cp's OEIS frontend

A124303 Number of set partitions of length <= 4; sum of first 4 columns of triangle of Stirling numbers of 2nd kind; dimension of space of symmetric polynomials in 4 noncommuting variables.

1, 1, 2, 5, 15, 51, 187, 715, 2795, 11051, 43947, 175275, 700075, 2798251, 11188907, 44747435, 178973355, 715860651, 2863377067, 11453377195, 45813246635, 183252462251, 733008800427, 2932033104555, 11728128223915, 46912504507051, 187650001250987

Offset: 0

Mike Zabrocki, Oct 25 2006

Apart from initial term, same as A007581. - Valery A. Liskovets, Nov 16 2006

			Number of set partitions of {1,2,3,4,5,6} are given by A008277(6,k) = 1, 31, 90, 65, 15, 1 and hence a(6) = 1+31+90+65 = 187.

Colin Barker, Table of n, a(n) for n = 0..1000
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A124292, A000110, A008277.

A row of the array in A278984.

a:=proc(n); if n<4 then [1,1,2,5][n+1]; else 7*a(n-1)-14*a(n-2)+8*a(n-3); fi; end:

Join[{1}, LinearRecurrence[{7, -14, 8}, {1, 2, 5}, 26]] (* Jean-François Alcover, Nov 20 2017 *)
Table[Sum[StirlingS2[n,k],{k,0,4}],{n,0,40}] (* Robert A. Russell, Mar 29 2018 *)

Vec((1 - 6*x + 9*x^2 - 3*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x)) + O(x^30)) \\ Colin Barker, Nov 03 2017

O.g.f.: (3*q^3 - 9*q^2 + 6*q - 1)/(8*q^3 - 14*q^2 + 7*q - 1) = Sum_{k=0..4} (q^k/Product_{i=1..k} (1-i*q)).
a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3); a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 5, a(n) = Sum_{k=1..4} A008277(n,k).
a(n) = (8 + 3*2^(1+n) + 4^n) / 24 for n>0. - Colin Barker, Nov 03 2017
a(n) = Sum_{k=0..4} Stirling2(n,k). - Robert A. Russell, Mar 29 2018
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=4. - Robert A. Russell, Apr 25 2018
E.g.f.: (9 + 8*exp(x) + 6*exp(2*x) + exp(4*x))/24. - Peter Luschny, Nov 06 2018

A130103 Expansion of e.g.f. e^(2x)-(1+x)*e^x+x.

Original entry on oeis.org

0, 1, 1, 4, 11, 26, 57, 120, 247, 502, 1013, 2036, 4083, 8178, 16369, 32752, 65519, 131054, 262125, 524268, 1048555, 2097130, 4194281, 8388584, 16777191, 33554406, 67108837, 134217700, 268435427, 536870882, 1073741793, 2147483616

Offset: 0

Paul Barry, May 07 2007

Partial sums are A130104.
Essentially the same as the Euler numbers A000295.
Number of binary strings of length n where 0 is not used or is used at least twice and 1 is used at least once. For example, for n=3 the strings are 100, 010, 001, 111. - Enrique Navarrete, Feb 06 2025
Also the number of ordered set partitions of an n-set into 2 sets such that the first set cannot have a single element and the second set has at least one element. For example, for n=3 the ordered set partitions are: { },{1,2,3}; {1,2},{3}; {1,3},{2}; {2,3},{1}. - Enrique Navarrete, Feb 14 2025

			G.f. = x + x^2 + 4*x^3 + 11*x^4 + 26*x^5 + 57*x^6 + 120*x^7 + 247*x^8 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..3321
Dillan Agrawal, Selena Ge, Jate Greene, Tanya Khovanova, Dohun Kim, Rajarshi Mandal, Tanish Parida, Anirudh Pulugurtha, Gordon Redwine, Soham Samanta, and Albert Xu, Chip-Firing on Infinite k-ary Trees, arXiv:2501.06675 [math.CO], 2025. See p. 18.
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000295.

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+n od: seq(a[n], n=0..30); # Zerinvary Lajos, Feb 22 2008

Join[{0,1},LinearRecurrence[{4,-5,2},{1,4,11},40]] (* Harvey P. Dale, May 16 2014 *)
a[ n_] := If[ n < 2, Boole[n == 1], 2^n - (1 + n)]; (* Michael Somos, Aug 17 2015 *)

{a(n) = if( n<2, n==1, 2^n - (1+n))}; /* Michael Somos, Aug 17 2015 */

G.f.: x(1-3x+5x^2-2x^3)/((1-x)^2*(1-2x)).
E.g.f.: e^(2x)-(1+x)*e^x+x.
a(n) = 2^n-n-1+C(1,n)-C(0,n).
a(n) = A130102(n+1)/2.
a(n) = Sum_{i=1..n} i*2^(n-i) - Ctibor O. Zizka, Feb 23 2008

A203647 T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 4, 1, 2, 5, 8, 1, 2, 5, 14, 16, 1, 2, 5, 15, 41, 32, 1, 2, 5, 15, 51, 122, 64, 1, 2, 5, 15, 52, 187, 365, 128, 1, 2, 5, 15, 52, 202, 715, 1094, 256, 1, 2, 5, 15, 52, 203, 855, 2795, 3281, 512, 1, 2, 5, 15, 52, 203, 876, 3845, 11051, 9842, 1024, 1, 2, 5, 15, 52, 203, 877

Offset: 1

R. H. Hardin, Jan 04 2012

Table starts
....1.....1......1......1......1......1......1......1......1......1......1
....2.....2......2......2......2......2......2......2......2......2......2
....4.....5......5......5......5......5......5......5......5......5......5
....8....14.....15.....15.....15.....15.....15.....15.....15.....15.....15
...16....41.....51.....52.....52.....52.....52.....52.....52.....52.....52
...32...122....187....202....203....203....203....203....203....203....203
...64...365....715....855....876....877....877....877....877....877....877
..128..1094...2795...3845...4111...4139...4140...4140...4140...4140...4140
..256..3281..11051..18002..20648..21110..21146..21147..21147..21147..21147
..512..9842..43947..86472.109299.115179.115929.115974.115975.115975.115975
.1024.29525.175275.422005.601492.665479.677359.678514.678569.678570.678570
Lower left triangular part seems to be A102661. - R. J. Mathar, Nov 29 2015

			Some solutions for n=7, k=5:
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..0....0....1....1....1....1....0....0....1....1....1....1....1....1....1....1
..1....0....2....1....2....2....1....1....2....2....2....2....1....2....1....2
..0....1....1....0....3....3....2....2....1....3....1....1....1....0....0....2
..0....0....3....1....0....4....3....0....2....3....1....1....1....0....2....1
..2....2....4....2....2....0....4....2....0....2....2....3....2....3....2....0
..1....3....1....0....2....5....0....0....0....0....0....2....2....1....1....1

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

Column 1 is A000079(n-1).
Column 2 is A007051(n-1).
Column 3 is A007581(n-1).
Column 4 is A056272.
Column 5 is A056273.
Column 6 is A099262.
Column 7 is A099263.
Column 8 is A164863.
Column 9 is A164864.
Column 10 is A203641.
Column 11 is A203642.
Column 12 is A203643.
Column 13 is A203644.
Column 14 is A203645.
Column 15 is A203646.
Diagonal is A000110.

T:= proc(n,k) option remember;  if k = 1 then 2^(n-1)
else 1 + add(binomial(n-1,j-1)*procname(n-j,k-1),j=1..n-1)
fi
end proc:
seq(seq(T(k,m-k),k=1..m-1),m=2..10); # Robert Israel, May 20 2016

T[n_, k_] := Sum[StirlingS2[n, j], {j, 1, k+1}]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 31 2017, after Andrew Howroyd *)

T(n,k) = Sum_{j = 1..k+1} Stirling2(n,j). - Andrew Howroyd, Mar 19 2017
T(n,k) = A278984(k+1, n). - Andrew Howroyd, Mar 19 2017
Empirical for column k:
k=1: a(n) = 2*a(n-1)
k=2: a(n) = 4*a(n-1) -3*a(n-2)
k=3: a(n) = 7*a(n-1) -14*a(n-2) +8*a(n-3)
k=4: a(n) = 11*a(n-1) -41*a(n-2) +61*a(n-3) -30*a(n-4)
k=5: a(n) = 16*a(n-1) -95*a(n-2) +260*a(n-3) -324*a(n-4) +144*a(n-5)
k=6: a(n) = 22*a(n-1) -190*a(n-2) +820*a(n-3) -1849*a(n-4) +2038*a(n-5) -840*a(n-6)
k=7: a(n) = 29*a(n-1) -343*a(n-2) +2135*a(n-3) -7504*a(n-4) +14756*a(n-5) -14832*a(n-6) +5760*a(n-7)
k=8: a(n) = 37*a(n-1) -574*a(n-2) +4858*a(n-3) -24409*a(n-4) +74053*a(n-5) -131256*a(n-6) +122652*a(n-7) -45360*a(n-8)
k=9: a(n) = 46*a(n-1) -906*a(n-2) +9996*a(n-3) -67809*a(n-4) +291774*a(n-5) -790964*a(n-6) +1290824*a(n-7) -1136160*a(n-8) +403200*a(n-9)
k=10: a(n) = 56*a(n-1) -1365*a(n-2) +19020*a(n-3) -167223*a(n-4) +965328*a(n-5) -3686255*a(n-6) +9133180*a(n-7) -13926276*a(n-8) +11655216*a(n-9) -3991680*a(n-10)
k=11: a(n) = 67*a(n-1) -1980*a(n-2) +33990*a(n-3) -375573*a(n-4) +2795331*a(n-5) -14241590*a(n-6) +49412660*a(n-7) -113667576*a(n-8) +163671552*a(n-9) -131172480*a(n-10) +43545600*a(n-11)
k=12: a(n) = 79*a(n-1) -2783*a(n-2) +57695*a(n-3) -782133*a(n-4) +7284057*a(n-5) -47627789*a(n-6) +219409685*a(n-7) -703202566*a(n-8) +1519272964*a(n-9) -2082477528*a(n-10) +1606986720*a(n-11) -518918400*a(n-12)
k=13: a(n) = 92*a(n-1) -3809*a(n-2) +93808*a(n-3) -1530243*a(n-4) +17419116*a(n-5) -141963107*a(n-6) +835933384*a(n-7) -3542188936*a(n-8) +10614910592*a(n-9) -21727767984*a(n-10) +28528276608*a(n-11) -21289201920*a(n-12) +6706022400*a(n-13)
k=14: a(n) = 106*a(n-1) -5096*a(n-2) +147056*a(n-3) -2840838*a(n-4) +38786748*a(n-5) -385081268*a(n-6) +2816490248*a(n-7) -15200266081*a(n-8) +59999485546*a(n-9) -169679309436*a(n-10) +331303013496*a(n-11) -418753514880*a(n-12) +303268406400*a(n-13) -93405312000*a(n-14)
k=15: a(n) = 121*a(n-1) -6685*a(n-2) +223405*a(n-3) -5042947*a(n-4) +81308227*a(n-5) -965408015*a(n-6) +8576039615*a(n-7) -57312583328*a(n-8) +287212533608*a(n-9) -1066335473840*a(n-10) +2866534951280*a(n-11) -5367984964224*a(n-12) +6557974412544*a(n-13) -4622628648960*a(n-14) +1394852659200*a(n-15)
From Robert Israel, May 20 2016: (Start)
T(n,k) = 1 + Sum_{j=1..n-1} binomial(n-1,j-1)*T(n-j,k-1).
G.f. for columns g_k(z) satisfies g_k(z) = (z/(1-z))*(1+ g_{k-1}(z/(1-z))) with g_1(z) = z/(1-2z).
Thus g_k is a rational function: it has a simple pole at z=1/j for 1<=j<=k+1 except j=k, and it has a finite limit at infinity (so the degree of the numerator is k).  This implies that column k satisfies the recurrences listed above, whose coefficients correspond to the expansion of (z-1/(k+1))* Product_{j=1..k-1}(z - 1/j).
(End)

A320750 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented row of length n using k or fewer colors (subsets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 6, 1, 1, 2, 4, 10, 10, 1, 1, 2, 4, 11, 25, 20, 1, 1, 2, 4, 11, 31, 70, 36, 1, 1, 2, 4, 11, 32, 107, 196, 72, 1, 1, 2, 4, 11, 32, 116, 379, 574, 136, 1, 1, 2, 4, 11, 32, 117, 455, 1451, 1681, 272, 1

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
In an unoriented row, chiral pairs are counted as one.
T(n,k) = Pi_k(P_n) which is the number of non-equivalent partitions of the path on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Mohammad Hadi Shekarriz, Aug 21 2019
From Allan Bickle, Apr 05 2022: (Start)
The columns count unlabeled k-paths with n+k+2 vertices. (A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.)
Recurrences for the columns appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			Array begins with T(1,1):
  1   1     1     1      1      1      1      1      1      1      1 ...
  1   2     2     2      2      2      2      2      2      2      2 ...
  1   3     4     4      4      4      4      4      4      4      4 ...
  1   6    10    11     11     11     11     11     11     11     11 ...
  1  10    25    31     32     32     32     32     32     32     32 ...
  1  20    70   107    116    117    117    117    117    117    117 ...
  1  36   196   379    455    467    468    468    468    468    468 ...
  1  72   574  1451   1993   2135   2151   2152   2152   2152   2152 ...
  1 136  1681  5611   9134  10480  10722  10742  10743  10743  10743 ...
  1 272  5002 22187  43580  55091  58071  58461  58486  58487  58487 ...
  1 528 14884 87979 211659 301633 333774 339764 340359 340389 340390 ...
For T(4,3)=10, the patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, AAAB, AABA, AABC, ABAC, the last four being chiral with partners ABBB, ABAA, ABCC, and ABCB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.

Columns 1-7 are A000012, A005418, A001998(n-1), A056323, A056324, A056325, A345207.
As k increases, columns converge to A103293(n+1).
Cf. transpose of A278984 (oriented), A320751 (chiral), A305749 (achiral).
Partial column sums of A284949.

Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
Table[Sum[StirlingS2[n,j] + Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten

T(n,k) = Sum_{j=1..k} (S2(n,j) + Ach(n,j))/2, where S2 is the Stirling subset number A008277 and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
T(n,k) = (A278984(k,n) + A305749(n,k)) / 2 = A278984(k,n) - A320751(n,k) = A320751(n,k) + A305749(n,k).
T(n,k) = Sum_{j=1..k} A284949(n,j).

A099262 a(n) = (1/5040)7^n + (1/240)5^n + (1/72)4^n + (1/16)3^n + (11/60)*2^n + 53/144. Partial sum of Stirling numbers of second kind S(n,i), i=1..7 (i.e., a(n) = Sum_{i=1..7} S(n,i)).

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4139, 21110, 115179, 665479, 4030523, 25343488, 164029595, 1084948961, 7291973067, 49582466986, 339971207051, 2345048898523, 16244652278171, 112871151708404, 785938550025147, 5480960778389365, 38264428799608235, 267342497477336542, 1868866831126685483

Offset: 1

Nelma Moreira, Oct 10 2004

Density of regular language L over {1,2,3,4,5,6,7} (i.e., number of strings of length n in L) described by regular expression with c=7: Sum_{i=1..c} Product_{j=1..i} (j(1+...+j)*) where Sum stands for union and Product for concatenation.

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
N. Moreira and R. Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
Index entries for linear recurrences with constant coefficients, signature (22,-190,820,-1849,2038,-840).

Cf. A007051, A007581, A056272, A056273, A099263.

A row of the array in A278984.

Table[Sum[StirlingS2[n, k], {k, 0, 7}], {n, 1, 30}] (* Robert A. Russell, Apr 25 2018 *)

a(n) = (1/5040)*7^n + (1/240)*5^n + (1/72)*4^n + (1/16)*3^n + (11/60)*2^n + 53/144; \\ Altug Alkan, Apr 25 2018

For c=7, a(n) = (c^n)/c! + Sum_{k=1..c-2} ((k^n)/k!*(Sum_{j=2..c-k}(((-1)^j)/j!))) or = Sum_{k=1..c} (g(k, c)*k^n) where g(1, 1)=1, g(1, c) = g(1, c-1)+((-1)^(c-1))/(c-1)!, c > 1, g(k, c) = g(k-1, c-1)/k, for c > 1 and 2 <= k <= c.
G.f.: -x*(531*x^5-881*x^4+535*x^3-151*x^2+20*x-1) / ((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(7*x-1)). - Colin Barker, Dec 05 2012
a(n) = Sum_{k=0..7} Stirling2(n,k).
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=7. - Robert A. Russell, Apr 25 2018

More terms from Michel Marcus, Jan 05 2025

A099263 a(n) = (1/40320)8^n + (1/1440)6^n + (1/360)5^n + (1/64)4^n + (11/180)3^n + (53/288)2^n + 103/280. Partial sum of Stirling numbers of second kind S(n,i), i=1..8 (i.e., a(n) = Sum_{i=1..8} S(n,i)).

Original entry on oeis.org

1, 2, 5, 15, 52, 203, 877, 4140, 21146, 115929, 677359, 4189550, 27243100, 184941915, 1301576801, 9433737120, 69998462014, 529007272061, 4054799902003, 31415584940850, 245382167055488, 1928337630016767, 15222915798289765, 120582710957928740, 957566218595705122, 7618489083072350433

Offset: 1

Nelma Moreira, Oct 10 2004

Density of regular language L over {1,2,3,4,5,6,7,8} (i.e., number of strings of length n in L) described by a regular expression with c = 8: Sum_{i=1..c} Product_{j=1..i} (j(1+...+j)*), where "Sum" stands for union and "Product" for concatenation.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
N. Moreira and R. Reis, On the density of languages representing finite set partitions, Technical Report DCC-2004-07, August 2004, DCC-FC& LIACC, Universidade do Porto.
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Index entries for linear recurrences with constant coefficients, signature (29,-343,2135,-7504,14756,-14832,5760).

Cf. A007051, A007581, A056272, A056273, A099262.
A row of the array in A278984.
Cf. A008277 (Stirling2), A248925.

[(1/40320)*8^n+(1/1440)*6^n+(1/360)*5^n+(1/64)*4^n +(11/180)*3^n+(53/288)*2^n+103/280: n in [1..30]]; // Vincenzo Librandi, Jul 27 2017

CoefficientList[Series[-(3641 x^6 - 6583 x^5 + 4566 x^4 - 1579 x^3 + 290 x^2 - 27 x + 1) / ((x - 1) (2 x - 1) (3 x - 1) (4 x - 1) (5 x - 1) (6 x - 1) (8 x - 1)), {x, 0, 30}], x] (* Vincenzo Librandi, Jul 27 2017 *)
Table[Sum[StirlingS2[n, k], {k, 0, 8}], {n, 1, 30}] (* Robert A. Russell, Apr 25 2018 *)
LinearRecurrence[{29,-343,2135,-7504,14756,-14832,5760},{1,2,5,15,52,203,877},30] (* Harvey P. Dale, Aug 27 2019 *)

a(n) = (1/40320)*8^n + (1/1440)*6^n + (1/360)*5^n + (1/64)*4^n + (11/180)*3^n + (53/288)*2^n + 103/280; \\ Altug Alkan, Apr 25 2018

For c = 8, a(n) = c^n/c! + Sum_{k=1..c-2} k^n/k! * Sum_{j=2..c-k} (-1)^j/j!, or = Sum_{k=1..c} g(k, c)*k^n, where g(1, 1) = 1, g(1, c) = g(1, c-1) + (-1)^(c-1)/(c-1)! for c > 1, and g(k, c) = g(k-1, c-1)/k for c > 1 and 2 <= k <= c.
G.f.: -x*(3641*x^6 - 6583*x^5 + 4566*x^4 - 1579*x^3 + 290*x^2 - 27*x + 1) / ((x-1)*(2*x-1)*(3*x-1)*(4*x-1)*(5*x-1)*(6*x-1)*(8*x-1)). [Colin Barker, Dec 05 2012]
a(n) = Sum_{k=0..8} Stirling2(n,k).
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} (1 - j*x) with k = 8. - Robert A. Russell, Apr 25 2018

More terms from Michel Marcus, Jan 05 2025

A320751 Array read by antidiagonals: T(n,k) is the number of chiral pairs of color patterns (set partitions) in a row of length n using k or fewer colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 0, 1, 4, 6, 0, 0, 0, 1, 4, 16, 12, 0, 0, 0, 1, 4, 20, 52, 28, 0, 0, 0, 1, 4, 20, 80, 169, 56, 0, 0, 0, 1, 4, 20, 86, 336, 520, 120, 0, 0, 0, 1, 4, 20, 86, 400, 1344, 1600, 240, 0, 0, 0, 1, 4, 20, 86, 409, 1852, 5440, 4840, 496, 0

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
A chiral row is not equivalent to its reverse.
T(n,k)=Xi_k(P_n) which is the number of non-equivalent distinguishing partitions of the path on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. A distinguishing partition is a partition of the vertex set of G such that no nontrivial automorphism of G can preserve it. - Bahman Ahmadi, Sep 02 2019

			Array begins with T(1,1):
0   0     0      0       0       0       0       0       0       0 ...
0   0     0      0       0       0       0       0       0       0 ...
0   1     1      1       1       1       1       1       1       1 ...
0   2     4      4       4       4       4       4       4       4 ...
0   6    16     20      20      20      20      20      20      20 ...
0  12    52     80      86      86      86      86      86      86 ...
0  28   169    336     400     409     409     409     409     409 ...
0  56   520   1344    1852    1976    1988    1988    1988    1988 ...
0 120  1600   5440    8868   10168   10388   10404   10404   10404 ...
0 240  4840  21760   42892   54208   57108   57468   57488   57488 ...
0 496 14641  87296  210346  299859  331705  337595  338155  338180 ...
0 992 44044 349184 1038034 1699012 2012202 2091458 2102518 2103348 ...
For T(4,2)=2, the chiral pairs are AAAB-ABBB and AABA-ABAA.
For T(4,3)=4, the above, AABC-ABCC, and ABAC-ABCB.

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.

Columns 1-6 are A000004, A122746(n-3), A107767(n-1), A320934, A320935, A320936.
As k increases, columns converge to A320937.
Cf. transpose of A278984 (oriented), A320750 (unoriented), A305749 (achiral).
Partial column sums of A320525.

Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
Table[Sum[StirlingS2[n,j] - Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten

T(n,k) = Sum_{j=1..k} (S2(n,j) - Ach(n,j)) / 2, where S2 is the Stirling subset number A008277 and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
T(n,k) = (A278984(k,n) - A305749(n,k)) / 2 = A278984(k,n) - A320750(n,k) = A320750(n,k) - A305749(n,k).
T(n,k) = Sum_{j=1..k} A320525(n,j).

A320955 Square array read by ascending antidiagonals: A(n, k) (n >= 0, k >= 0) = Sum_{j=0..n-1} (!j/j!)*((n - j)^k/(n - j)!) if k > 0 and 1 if k = 0. Here !n denotes the subfactorial of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 8, 1, 0, 1, 1, 2, 5, 14, 16, 1, 0, 1, 1, 2, 5, 15, 41, 32, 1, 0, 1, 1, 2, 5, 15, 51, 122, 64, 1, 0, 1, 1, 2, 5, 15, 52, 187, 365, 128, 1, 0, 1, 1, 2, 5, 15, 52, 202, 715, 1094, 256, 1, 0

Offset: 0

Peter Luschny, Nov 05 2018

Arndt and Sloane (see the link and A278984) identify the sequence to give "the number of words of length n over an alphabet of size b that are in standard order" and provide the formula Sum_{j = 1..b} Stirling_2(n, j) assuming b >= 1 and j >= 1. Compared to the array as defined here this misses the first row and the first column of our array.
The method used here is the special case of a general method described in A320956 applied to the function exp. For applications to other functions see the cross references.
A(k,n) is the number of color patterns (set partitions) for an oriented row of length n using up to k colors (subsets). Two color patterns are equivalent if the colors are permuted. For A(3,4) = 14, the six achiral patterns are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA; the eight chiral patterns are the four chiral pairs AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - Robert A. Russell, Nov 10 2018

			Array starts:
n\k   0  1  2  3   4   5    6    7     8      9  ...
----------------------------------------------------
[0]   1, 0, 0, 0,  0,  0,   0,   0,    0,     0, ...  A000007
[1]   1, 1, 1, 1,  1,  1,   1,   1,    1,     1, ...  A000012
[2]   1, 1, 2, 4,  8, 16,  32,  64,  128,   256, ...  A011782
[3]   1, 1, 2, 5, 14, 41, 122, 365, 1094,  3281, ...  A124302
[4]   1, 1, 2, 5, 15, 51, 187, 715, 2795, 11051, ...  A124303
[5]   1, 1, 2, 5, 15, 52, 202, 855, 3845, 18002, ...  A056272
[6]   1, 1, 2, 5, 15, 52, 203, 876, 4111, 20648, ...  A056273, ?A284727
[7]   1, 1, 2, 5, 15, 52, 203, 877, 4139, 21110, ...
[8]   1, 1, 2, 5, 15, 52, 203, 877, 4140, 21146, ...
[9]   1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, ...
----------------------------------------------------
Seen as a triangle given by the descending antidiagonals:
[0]             1
[1]            0, 1
[2]          0, 1, 1
[3]        0, 1, 1, 1
[4]       0, 1, 2, 1, 1
[5]     0, 1, 4, 2, 1, 1
[6]    0, 1, 8, 5, 2, 1, 1
[7]  0, 1, 16, 14, 5, 2, 1, 1

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

Cf. A008290, A000110, A137650, A211561, A000240, A000387, A000449, A103816/A053556.
Cf. A124302, A124303, A056272, A056273, A284727, A278984.
Antidiagonal sums (and row sums of the triangle): A320964.
Cf. this sequence (exp), A320962 (log(x+1)), A320956 (sec+tan), A320958 (arcsin), A320959 (arctanh).
Cf. A320750 (unoriented), A320751 (chiral), A305749 (achiral).

A := (n, k) -> if k = 0 then 1 else add(A008290(n, n-j)*(n-j)^k, j=0..n-1)/n! fi:
seq(lprint(seq(A(n, k), k=0..9)), n=0..9); # Prints the array row-wise.
seq(seq(A(n-k, k), k=0..n), n=0..11); # Gives the array as listed.

T[n_, 0] := 1; T[n_, k_] := Sum[(Subfactorial[j]/Factorial[j])((n - j)^k/(n - j)!), {j, 0, n - 1}]; Table[T[n - k, k], {n, 0, 11}, {k, 0, n}] // Flatten
Table[Sum[StirlingS2[k, j], {j, 0, n-k}], {n, 0, 11}, {k, 0, n}] // Flatten (* Robert A. Russell, Nov 10 2018 *)

A(n, k) = (1/n!)*Sum_{j=0..n-1} A008290(n, n-j)*(n-j)^k if k > 0.
If one drops the special case A(n, 0) = 1 from the definition then column 0 becomes Sum_{k=0..n} (-1)^k/k! = A103816(n)/A053556(n).
Row n is given for k >= 1 by a_n(k), where
a_0(k) = 0^k/0!.
a_1(k) = 1^k/1!.
a_2(k) = (2^k)/2!.
a_3(k) = (3^k + 3)/3!.
a_4(k) = (6*2^k + 4^k + 8)/4!.
a_5(k) = (20*2^k + 10*3^k + 5^k + 45)/5!.
a_6(k) = (135*2^k + 40*3^k + 15*4^k + 6^k + 264)/6!.
a_7(k) = (924*2^k + 315*3^k + 70*4^k + 21*5^k + 7^k + 1855)/7!.
a_8(k) = (7420*2^k + 2464*3^k + 630*4^k + 112*5^k + 28*6^k + 8^k + 14832)/8!.
Note that the coefficients of the generating functions a_n are the recontres numbers A000240, A000387, A000449, ...
Rewriting the formulas with exponential generating functions for the rows we have egf(n) = Sum_{k=0..n} !k*binomial(n,k)*exp(x*(n-k)) and A(n, k) = (k!/n!)*[x^k] egf(n). In this formulation no special rule for the case k = 0 is needed.
The rows converge to the Bell numbers. Convergence here means that for every fixed k the terms in column k differ from A000110(k) only for finitely many indices.
A(n, n) are the Bell numbers A000110(n) for n >= 0.
Let S(n, k) = Bell(n+k+1) - A(n, k+n+1) for n >= 0 and k >= 0, then the square array S(n, k) read by descending antidiagonals equals provable the triangle A137650 and equals empirical the transpose of the array A211561.

A164863 Number of ways of placing n labeled balls into 9 indistinguishable boxes; word structures of length n using a 9-ary alphabet.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115974, 678514, 4211825, 27602602, 190077045, 1368705291, 10254521370, 79527284317, 635182667816, 5199414528808, 43426867585575, 368654643520692, 3170300933550687, 27542984610086665, 241205285284001240

Offset: 0

Alois P. Heinz, Aug 28 2009

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Moreira, N.; Reis, R. "On the Density of Languages Representing Finite Set Partitions", Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Eric Weisstein's World of Mathematics, Set Partition
Index entries for linear recurrences with constant coefficients, signature (37, -574, 4858, -24409, 74053, -131256, 122652, -45360).

Cf. A000110, A048993, A008291, A098825, A000012, A000079, A007051, A007581, A124303, A056272, A056273, A099262, A099263, A164864.

A row of the array in A278984.

# first program:
a:= n-> ceil(103/560*2^n +53/864*3^n +11/720*4^n +5^n/320 +6^n/2160 +7^n/10080 +9^n/362880): seq(a(n), n=0..25);
# second program:
a:= n-> add(Stirling2(n, k), k=0..9): seq(a(n), n=0..25);

Table[Sum[StirlingS2[n, k], {k, 0, 9}], {n, 0, 30}] (* Robert A. Russell, Apr 25 2018 *)

a(n) = Sum_{k=0..9} stirling2 (n,k).
a(n) = ceiling (103/560*2^n +53/864*3^n +11/720*4^n +5^n/320 +6^n/2160 +7^n/10080 +9^n/362880).
G.f.: (16687*x^8 -67113*x^7 +88620*x^6 -56993*x^5 +20529*x^4 -4353*x^3 +539*x^2 -36*x+1) / ((9*x-1) *(7*x-1) *(6*x-1) *(5*x-1) *(4*x-1) *(3*x-1) *(2*x-1) *(x-1)).
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=9. - Robert A. Russell, Apr 25 2018

A278987 Array read by antidiagonals downwards: T(b,n) = number of words of length n over an alphabet of size b that are in standard order and which have the property that every letter that appears in the word is repeated.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 4, 1, 1, 0, 1, 11, 4, 1, 1, 0, 1, 26, 11, 4, 1, 1, 0, 1, 57, 41, 11, 4, 1, 1, 0, 1, 120, 162, 41, 11, 4, 1, 1, 0, 1, 247, 610, 162, 41, 11, 4, 1, 1, 0, 1, 502, 2165, 715, 162, 41, 11, 4, 1, 1, 0, 1, 1013, 7327, 3425, 715, 162, 41, 11, 4, 1, 1, 0

Offset: 1

Joerg Arndt and N. J. A. Sloane, Dec 06 2016

We study words made of letters from an alphabet of size b, where b >= 1. We assume the letters are labeled {1,2,3,...,b}. There are b^n possible words of length n.

We say that a word is in "standard order" if it has the property that whenever a letter i appears, the letter i-1 has already appeared in the word. This implies that all words begin with the letter 1.

			The array begins:
0,.1,..1,...1,...1,...1,...1,....1..; b=1,
0,.1,..4,...8,..16,..32,..64,..128..; b=2,
0,.1,..4,..14,..41,.122,.365,.1094..; b=3,
0,.1,..4,..14,..51,.187,.715,.2795..; b=4,
0,.1,..4,..14,..51,.202,.855,.3845..; b=5,
0,.1,..4,..14,..51,.202,.876,.4111..; b=6,
...
Rows b=1 through b=4 of the array are A000012, A000295 (or A130103), A278988, A278989.

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

The words for b=9 are listed in A273978.

with(combinat);
A008299 := proc(n,k) local i,j,t1;
if k<1 or k>floor(n/2) then t1:=0; else
t1 := add( (-1)^i*binomial(n, i)*add( (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), j = 0..k - i), i = 0..k); fi; t1; end;
f3:=proc(L,b) global A008299; local i; add(A008299(L,i),i=1..b); end;
Q3:=b->[seq(f3(L,b),L=1..40)];
for b from 1 to 6 do lprint(Q3(b)); od:

The number of words of length n over an alphabet of size b that are in standard order and in which every symbol that appears in a word is repeated is Sum_{j = 1..b} A008299(n,j).

cp's OEIS Frontend

A124303 Number of set partitions of length <= 4; sum of first 4 columns of triangle of Stirling numbers of 2nd kind; dimension of space of symmetric polynomials in 4 noncommuting variables.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A130103 Expansion of e.g.f. e^(2x)-(1+x)*e^x+x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A203647 T(n,k) = number of arrays of n 0..k integers with new values introduced in order 0..k but otherwise unconstrained. Array read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A320750 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented row of length n using k or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A099262 a(n) = (1/5040)*7^n + (1/240)*5^n + (1/72)*4^n + (1/16)*3^n + (11/60)*2^n + 53/144. Partial sum of Stirling numbers of second kind S(n,i), i=1..7 (i.e., a(n) = Sum_{i=1..7} S(n,i)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A099263 a(n) = (1/40320)*8^n + (1/1440)*6^n + (1/360)*5^n + (1/64)*4^n + (11/180)*3^n + (53/288)*2^n + 103/280. Partial sum of Stirling numbers of second kind S(n,i), i=1..8 (i.e., a(n) = Sum_{i=1..8} S(n,i)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A320751 Array read by antidiagonals: T(n,k) is the number of chiral pairs of color patterns (set partitions) in a row of length n using k or fewer colors (subsets).

Views

Author

Keywords

A099262 a(n) = (1/5040)7^n + (1/240)5^n + (1/72)4^n + (1/16)3^n + (11/60)*2^n + 53/144. Partial sum of Stirling numbers of second kind S(n,i), i=1..7 (i.e., a(n) = Sum_{i=1..7} S(n,i)).

A099263 a(n) = (1/40320)8^n + (1/1440)6^n + (1/360)5^n + (1/64)4^n + (11/180)3^n + (53/288)2^n + 103/280. Partial sum of Stirling numbers of second kind S(n,i), i=1..8 (i.e., a(n) = Sum_{i=1..8} S(n,i)).