A000670 -id:A000670 - cp's OEIS frontend

A060223 Number of orbits of length n under the map whose periodic points are counted by A000670.

1, 1, 1, 4, 18, 108, 778, 6756, 68220, 787472, 10224702, 147512052, 2340963570, 40527565260, 760095923082, 15352212731820, 332228417589720, 7668868648772700, 188085259069430744, 4884294069438337428, 133884389812214097774, 3863086904690670182596

Offset: 0

Thomas Ward, Mar 21 2001

From Gus Wiseman, Oct 14 2016: (Start)
A finite sequence is normal if it spans an initial interval of positive integers. The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, (2 2 1) * (2 1 3) = (2 1 2 2 1 3). If Q is the set of compositions (finite sequences of positive integers) then (Q,*) is an Abelian group freely generated by a set P of prime sequences. The number of normal prime sequences of length n is equal to a(n). See example 2 and Mathematica program 2.
If N is the species (endofunctor over the category of finite sets and permutations) of unlabeled necklaces and N(S) represents the set of all non-isomorphic primitive necklaces of length n=|S|, then the numbers |N(S)| are equal to the numbers a(|S|) for any finite set S. This is because the number of orderless *-factorizations (see A034691 and A269134) of any finite sequence q is equal to the number of multiset partitions (see A007716 and A255906) of the multiset of prime factors of q. (End)

			a(5) = 108 since A000670(5) is 541 and A000670(1) is 1, so there must be (541-1)/5 = 108 orbits of length 5.
From _Gus Wiseman_, Oct 14 2016: (Start)
The a(4) = 18 normal prime sequences are the columns:
[2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4]
[1 2 2 1 1 1 2 2 2 2 3 3 1 1 2 2 3 3]
[1 1 2 1 2 2 1 1 2 3 1 2 2 3 1 3 1 2]
[1 1 1 2 1 2 1 2 1 1 2 1 3 2 3 1 2 1].
The symmetric function A(x_1,x_2,x_3,...) expanded in terms of monomial symmetric functions m(y) (indexed by integer partitions y) is equal to:
A = m(1) +
    m(11) +
    (2*m(21) + 2*m(111) +
    (m(22) + 2*m(31) + 9*m(211) + 6*m(1111)) +
    (4*m(32) + 2*m(41) + 18*m(221) + 12*m(311) + 48*m(2111) + 24*m(11111)) +
    (3*m(33) + 4*m(42) + 2*m(51) + 14*m(222) + 60*m(321) + 15*m(411) + 180*m(2211) + 80*m(3111) + 300*m(21111) + 120*m(111111)) + ... (End)

Alois P. Heinz, Table of n, a(n) for n = 0..200
Yash Puri and Thomas Ward, A dynamical property unique to the Lucas sequence, Fibonacci Quarterly, Volume 39, Number 5 (November 2001), pp. 398-402.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
T. Ward, Exactly realizable sequences

Cf. A000670, A034691 (multisets of compositions), A269134, A007716, A277427, A215474, A255906.

Row sums of A254040.

a[n_] := DivisorSum[n, MoebiusMu[#] HurwitzLerchPhi[1/2, -n/#, 0]/2 &] / n; a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2016 *)
thufbin[{},b_List]:=b;thufbin[a_List,{}]:=a;thufbin[a_List]:=a;
thufbin[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{thufbin[{a},{x,b}],thufbin[{x,a},{b}]}]],{1,2},Prepend[thufbin[{a},{y,b}],x],{2,1},Prepend[thufbin[{x,a},{b}],y]];
thufbin[a_List,b_List,c__List]:=thufbin[a,thufbin[b,c]];
priseqs[n_]:=Fold[Select,Tuples[Range[n],n],{Union[#]===Range[First[#]]&,Function[q,Select[Table[List[Take[q,{1,j}],Take[q,{j+1,n}]],{j,1,n-1}],thufbin@@Sort[#]===q&,1]==={}]}];
Table[Length[priseqs[n]],{n,1,7}] (* Gus Wiseman, Oct 14 2016 *)

\\ here b(n) is A000670
b(n)={polcoeff(serlaplace(1/(2-exp(x+O(x*x^n)))), n)}
a(n)={if(n<1, n==0, sumdiv(n, d, moebius(d)*b(n/d))/n)} \\ Andrew Howroyd, Dec 12 2017

a(n) = (1/n)* Sum_{d|n} mu(d)*A000670(n/d) for n > 0, where mu is A008683, the Moebius function. - Edited by Michel Marcus, Mar 30 2016
Let A = Sum_{q in P} Prod_i x_{q_i} = Sum_y c_y m(y) be the symmetric function whose coefficient of m(y) is equal to the number of permutations of the normal multiset [k]^y that belong to P, where the multiplicity of i in [k]^y is defined to be y_i. Then a(n) is the sum of c_y taken over all integer partitions of n. See example 3. - Gus Wiseman, Oct 14 2016
a(n) = Sum_{d|n} mu(d) * A019536(n/d) for n >= 1. - Petros Hadjicostas, Aug 19 2019

More terms from Alois P. Heinz, Jan 23 2015

A075729 Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a "preferential arrangement" or "weak order" as in A000670.

Original entry on oeis.org

1, 1, 4, 23, 173, 1602, 17575, 222497, 3188806, 50988405, 899222457, 17329515172, 362164300173, 8155216185781, 196789115887252, 5064722539020379, 138457553073641465, 4006059432756066914, 122284085809137076203, 3926775294104305483621, 132313462760902116605534

Offset: 0

Thomas Wieder and N. J. A. Sloane, Oct 06 2002

If all individuals form a single society ("uniparate society"), then the number of different hierarchies for that single society is equal to the ordered Bell number Bell_ordered(n) (A000670).

Represent a labeled pre-order (quasi-order, topology, A000798) as a directed graph. a(n) is the number of such digraphs in which the underlying graph of each component is complete. a(3)=23 because there are 29 such digraphs but o->o<-o and o<-o->o are not counted. Each has 3 labelings. 29 - 6 = 23. - Geoffrey Critzer, Jul 30 2014

			a(3) = 23: Let the n = 3 individuals be named 1, 2 and 3. Let a pair of parentheses () indicate a society and let square brackets [] denote a set of disparate societies. Finally, let the ranks be ordered from left to right and separated by a colon, e.g., (1,2:3) is a society with individual 3 on top and individuals 1 and 2 on the same bottom rank.
Then the hierarchical ordering for n = 3 is composed of the following sets: [(1),(2),(3)], [(1,2)(3)], [(3,2)(1)], [(3,1)(2)], [(1:2)(3)], [(3:2)(1)], [(1:3)(2)], [(2:1)(3)], [(2:3)(1)], [(3:1)(2)], [(3:2:1)], [(1:3:2)], [(2:1:3)], [(1:2:3)], [(3:1:2)], [(2:3:1)], [(1,3:2)], [(3,2:1)], [(2,1:3)], [(3:1,2)], [(1:2,3)], [(2:3,1)], [(1,2,3)].

Alois P. Heinz, Table of n, a(n) for n = 0..419 (first 101 terms from T. D. Noe)
José A. Adell and Sithembele Nkonkobe, A unified generalization of Touchard and Fubini polynomial extensions, Integers (2023) 23, #A80.
INRIA, Algolib: The Algorithms Project's Library
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 571.
Robert Gill, The number of elements in a generalized partition semilattice, Discrete mathematics 186.1-3 (1998): 125-134. See Example 2.
Norihiro Nakashima and Shuhei Tsujie, Enumeration of Flats of the Extended Catalan and Shi Arrangements with Species, arXiv:1904.09748 [math.CO], 2019.
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem [J. Phys. A 37 (2004), 3475-3487]
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
Kruchinin Vladimir Victorovich, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. - _Thomas Wieder_, Nov 14 2009
Index entries for sequences related to parenthesizing

Cf. A000670, A075744. See A075900 for the unlabeled case.

A075729 := n->n!*exp(1/4/ln(2)-3/4)/2/sqrt(Pi)/(2*ln(2))^(1/4)*exp(-n*ln(ln(2)))*exp(sqrt(2*n/ln(2)))*n^(-3/4);
with(combstruct); SetSeqSetL := [T, {T=Set(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},labeled]; seq(count(SetSeqSetL,size=j),j=1..12);
# alternative Maple program:
b:= proc(n) option remember: `if`(n<2, 1,
      (2*n-1)*b(n-1) -(n-1)*(n-2)*b(n-2))
    end:
a:= n-> add(b(k)*Stirling2(n,k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 22 2018

Range[0, 20]!CoefficientList[Series[E^(1/(2 - E^x) - 1), {x, 0, 20}], x] (* Robert G. Wilson v, Jul 13 2004 *)
Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; a[0] = 1; a[n_] := a[n] = (n-1)! Sum[a[n-k] Fubini[k, 1]/((n-k)! (k-1)!), {k, 1, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 31 2016 *)
Table[Sum[BellY[n, k, PolyLog[-Range[n], 1/2]/2], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)
With[{nn=20},CoefficientList[Series[Exp[1/(2-Exp[x])-1],{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Aug 26 2022 *)

a(n):= sum(sum(stirling2(n,k)*k!*binomial(k-1,m-1), k,m,n)/m!, m,1,n) /* Vladimir Kruchinin, Aug 10 2010 */

E.g.f.: exp(f(x)-1) where f(x) = 1/(2-exp(x)) = e.g.f. for A000670.
STIRLINGi transform of A000262.
a(n) = (n-1)! * Sum_k=1^n a(n-k)*b(k)/((n-k)!*(k-1)!); a(n) = a(n) + C(n-1, k-1)*a(n-k)*b(k) (where b(n) = A000670(n)). - Thomas Wieder, Dec 31 2002
a(n) = (Sum_{j=1..n} m(j))*(n!*Product_{j=1..n} B(j)^m(j))/(Product_{j=1..n} (m(j))!*(j!)^m(j)), where the sum is over all (m(1),m(2),...,m(n)) such that Sum_{j=1..n} (j*m(j)) = n. - Thomas Wieder, May 18 2003
a(n) is asymptotic to exp(1/(4*log(2))-3/4) /(2*sqrt(Pi*sqrt(2*log(2)))) *n!*exp(-log(log(2))*n)*exp(sqrt(2*n /log(2))) /n^(3/4). Calculated using the Maple package "algolib", using the command "equivalent(exp(1/(2-exp(x))-1), x, n);". - Thomas Wieder, Nov 12 2002
a(n) = Sum_{k=0..n} A079641(n,k)*A000110(k). - Vladeta Jovovic, Sep 25 2006
a(n) = sum(sum(stirling2(n,k)*k!*C(k-1,m-1), k=m..n)/m!, m=1..n). - Vladimir Kruchinin, Aug 10 2010

A035317 Pascal-like triangle associated with A000670.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 4, 2, 1, 4, 7, 6, 3, 1, 5, 11, 13, 9, 3, 1, 6, 16, 24, 22, 12, 4, 1, 7, 22, 40, 46, 34, 16, 4, 1, 8, 29, 62, 86, 80, 50, 20, 5, 1, 9, 37, 91, 148, 166, 130, 70, 25, 5, 1, 10, 46, 128, 239, 314, 296, 200, 95, 30, 6, 1, 11, 56, 174, 367, 553, 610, 496, 295, 125

Offset: 0

N. J. A. Sloane

From Johannes W. Meijer, Jul 20 2011: (Start)
The triangle sums, see A180662 for their definitions, link this "Races with Ties" triangle with several sequences, see the crossrefs. Observe that the Kn4 sums lead to the golden rectangle numbers A001654 and that the Fi1 and Fi2 sums lead to the Jacobsthal sequence A001045.
The series expansion of G(x, y) = 1/((y*x-1)*(y*x+1)*((y+1)*x-1)) as function of x leads to this sequence, see the second Maple program. (End)
T(2n,k) = the number of hatted frog arrangements with k frogs on the 2xn grid. See the linked paper "Frogs, hats and common subsequences". - Chris Cox, Apr 12 2024

			Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  4,   2;
  1,  4,  7,   6,   3;
  1,  5, 11,  13,   9,   3;
  1,  6, 16,  24,  22,  12,   4;
  1,  7, 22,  40,  46,  34,  16,   4;
  1,  8, 29,  62,  86,  80,  50,  20,  5;
  1,  9, 37,  91, 148, 166, 130,  70, 25,  5;
  1, 10, 46, 128, 239, 314, 296, 200, 95, 30, 6;
  ...

Vincenzo Librandi, Rows n = 0..100, flattened
Joseph Briggs, Alex Parker, Coy Schwieder, and Chris Wells, Frogs, hats and common subsequences, arXiv preprint arXiv:2404.07285 [math.CO], 2024. See p. 28.
A. Hlavác, M. Marvan, Nonlocal conservation laws of the constant astigmatism equation, arXiv preprint arXiv:1602.06861 [nlin.SI], 2016.
E. Mendelson, Races with Ties, Math. Mag. 55 (1982), 170-175.
Index entries for triangles and arrays related to Pascal's triangle

Row sums are A000975, diagonal sums are A080239.
Central terms are A014300.
Similar to the triangles A059259, A080242, A108561, A112555.
Cf. A059260.
Triangle sums (see the comments): A000975 (Row1), A059841 (Row2), A080239 (Kn11), A052952 (Kn21), A129696 (Kn22), A001906 (Kn3), A001654 (Kn4), A001045 (Fi1, Fi2), A023435 (Ca2), Gi2 (A193146), A190525 (Ze2), A193147 (Ze3), A181532 (Ze4). - Johannes W. Meijer, Jul 20 2011
Cf. A181971.

a035317 n k = a035317_tabl !! n !! k
a035317_row n = a035317_tabl !! n
a035317_tabl = map snd $ iterate f (0, [1]) where
   f (i, row) = (1 - i, zipWith (+) ([0] ++ row) (row ++ [i]))
-- Reinhard Zumkeller, Jul 09 2012

A035317 := proc(n,k): add((-1)^(i+k) * binomial(i+n-k+1, i), i=0..k) end: seq(seq(A035317(n,k), k=0..n), n=0..10); # Johannes W. Meijer, Jul 20 2011
A035317 := proc(n,k): coeff(coeftayl(1/((y*x-1)*(y*x+1)*((y+1)*x-1)), x=0, n), y, k) end: seq(seq(A035317(n,k), k=0..n), n=0..10); # Johannes W. Meijer, Jul 20 2011

t[n_, k_] := (-1)^k*(((-1)^k*(n+2)!*Hypergeometric2F1[1, n+3, k+2, -1])/((k+1)!*(n-k+1)!) + 2^(k-n-2)); Flatten[ Table[ t[n, k], {n, 0, 11}, {k, 0, n}]] (* Jean-François Alcover, Dec 14 2011, after Johannes W. Meijer *)

{T(n,k)=if(n==k,(n+2)\2,if(k==0,1,if(n>k,T(n-1,k-1)+T(n-1,k))))}
for(n=0,12,for(k=0,n,print1(T(n,k),","));print("")) \\ Paul D. Hanna, Jul 18 2012

def A035317_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return -prec(n-1,k-1)-sum(prec(n,k+i-1) for i in (2..n-k+1))
    return [(-1)^k*prec(n+2, k) for k in (1..n)]
for n in (1..11): print(A035317_row(n)) # Peter Luschny, Mar 16 2016

T(n,k) = Sum_{j=0..floor(n/2)} binomial(n-2j, k-2j). - Paul Barry, Feb 11 2003
From Johannes W. Meijer, Jul 20 2011: (Start)
T(n, k) = Sum_{i=0..k}((-1)^(i+k) * binomial(i+n-k+1,i)). (Mendelson)
T(n, k) = T(n-1, k-1) + T(n-1, k) with T(n, 0) = 1 and T(n, n) = floor(n/2) + 1. (Mendelson)
Sum_{k = 0..n}((-1)^k * (n-k+1)^n * T(n, k)) = A000670(n). (Mendelson)
T(n, n-k) = A128176(n, k); T(n+k, n-k) = A158909(n, k); T(2*n-k, k) = A092879(n, k). (End)
T(2*n+1,n) = A014301(n+1); T(2*n+1,n+1) = A026641(n+1). - Reinhard Zumkeller, Jul 19 2012

More terms from James Sellers

A089677 Exponential convolution of A000670(n), with A000670(0)=0, with the sequence of all ones alternating in sign.

Original entry on oeis.org

0, 1, 1, 7, 37, 271, 2341, 23647, 272917, 3543631, 51123781, 811316287, 14045783797, 263429174191, 5320671485221, 115141595488927, 2657827340990677, 65185383514567951, 1692767331628422661, 46400793659664205567, 1338843898122192101557

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Jan 03 2004

Stirling transform of A005212(n)=[1,0,6,0,120,0,5040,...] is a(n)=[1,1,7,37,271,...]. - Michael Somos, Mar 04 2004

Occurs also as first column of a matrix-inversion occurring in a sum-of-like-powers problem. Consider the problem for any fixed natural number m>2 of finding solutions to sum(k=1,n,k^m) = (k+1)^m. Erdos conjectured that there are no solutions for n,m>2. Let D be the matrix of differences of D[m,n] := sum(k=1,n,k^m) - (k+1)^m. Then the generating functions for the rows of this matrix D constitute a set of polynomials in n (for varying n along columns) and the m-th polynomial defining the m-th row. Let GF_D be the matrix of the coefficients of this set of polynomials. Then the present sequence is the (unsigned) second column of GF_D^-1. - Gottfried Helms, Apr 01 2007

			From _Gus Wiseman_, Jan 06 2021: (Start)
a(n) is the number of ordered set partitions of {1..n} into an odd number of blocks. The a(1) = 1 through a(3) = 7 ordered set partitions are:
  {{1}}  {{1,2}}  {{1,2,3}}
                  {{1},{2},{3}}
                  {{1},{3},{2}}
                  {{2},{1},{3}}
                  {{2},{3},{1}}
                  {{3},{1},{2}}
                  {{3},{2},{1}}
(End)

Vincenzo Librandi, Table of n, a(n) for n = 0..200
J.-C. Aval, V. Féray, J.-C. Novelli, J.-Y. Thibon, Quasi-symmetric functions as polynomial functions on Young diagrams, arXiv preprint arXiv:1312.2727, 2013
Gottfried Helms, Discussion of a problem concerning summing of like powers

Ordered set partitions are counted by A000670.
The case of (unordered) set partitions is A024429.
The complement (even-length ordered set partitions) is counted by A052841.
A058695 counts partitions of odd numbers, ranked by A300063.
A101707 counts partitions of odd positive rank.
A160786 counts odd-length partitions of odd numbers, ranked by A300272.
A340102 counts odd-length factorizations into odd factors.
A340692 counts partitions of odd rank.
Other cases of odd length:
- A027193 counts partitions of odd length.
- A067659 counts strict partitions of odd length.
- A166444 counts compositions of odd length.
- A174726 counts ordered factorizations of odd length.
- A332304 counts strict compositions of odd length.
- A339890 counts factorizations of odd length.
Cf. A000700, A026424, A027187, A028260, A078408, A174725, A236914, A340101.

h := n -> add(combinat:-eulerian1(n,k)*2^k,k=0..n):
a := n -> (h(n)-(-1)^n)/2: seq(a(n),n=0..20); # Peter Luschny, Jul 09 2015

Table[Sum[Binomial[n, k](-1)^(n-k)Sum[i! StirlingS2[k, i], {i, 1, k}], {k, 0, n}], {n, 0, 20}]

a(n)=if(n<0,0,n!*polcoeff(subst(y/(1-y^2),y,exp(x+x*O(x^n))-1),n))

{a(n)=polcoeff(sum(m=0,n,(2*m+1)!*x^(2*m+1)/prod(k=1,2*m+1,1-k*x+x*O(x^n))),n)} /* Paul D. Hanna, Jul 20 2011 */

def A089677_list(len):  # with a(0)=1
    e, r = [1], [1]
    for i in (1..len-1):
        for k in range(i-1, -1, -1): e[k] = (e[k]*i)//(i-k)
        r.append(-sum(e[j]*(-1)^(i-j) for j in (0..i-1)))
        e.append(sum(e))
    return r
A089677_list(21) # Peter Luschny, Jul 09 2015

E.g.f.: (exp(x)-1)/(exp(x)*(2-exp(x))).
O.g.f.: Sum_{n>=0} (2*n+1)! * x^(2*n+1) / Product_{k=1..2*n+1} (1-k*x). - Paul D. Hanna, Jul 20 2011
a(n)=Sum(Binomial(n, k)(-1)^(n-k)Sum(i! Stirling2(k, i), i=1, ..k), k=0, .., n).
a(n) = (A000670(n)-(-1)^n)/2. - Vladeta Jovovic, Jan 17 2005
a(n) ~ n! / (4*(log(2))^(n+1)). - Vaclav Kotesovec, Feb 25 2014
a(n) = Sum_{k=0..floor(n/2)} (2*k+1)!*Stirling2(n, 2*k+1). - Peter Luschny, Sep 20 2015

A217389 Partial sums of the ordered Bell numbers (number of preferential arrangements) A000670.

Original entry on oeis.org

1, 2, 5, 18, 93, 634, 5317, 52610, 598445, 7685706, 109933269, 1732565842, 29824133437, 556682481818, 11198025452261, 241481216430114, 5557135898411469, 135927902927547370, 3521462566184392693, 96323049885512803826, 2774010846129897006941, 83898835844633970888762

Offset: 0

Emanuele Munarini, Oct 02 2012

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000670, A006957, A005649, A217388, A217391, A217392.

See A239914 for another version.

A000670:=func;
[&+[A000670(k): k in [0..n]]: n in [0..19]]; // Bruno Berselli, Oct 03 2012

b:= proc(n, k) option remember;
     `if`(n=0, k!, k*b(n-1, k)+b(n-1, k+1))
    end:
a:= proc(n) option remember; `if`(n<0, 0, a(n-1)+b(n, 0)) end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 20 2025

t[n_] := Sum[StirlingS2[n, k]k!, {k, 0, n}]; Table[Sum[t[k], {k, 0, n}], {n, 0, 100}]
(* second program: *)
Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; Table[Fubini[n, 1], {n, 0, 20}] // Accumulate (* Jean-François Alcover, Mar 31 2016 *)

t(n):=sum(stirling2(n,k)*k!,k,0,n);
makelist(sum(t(k),k,0,n),n,0,40);

for(n=0,30, print1(sum(k=0,n, sum(j=0,k, j!*stirling(k,j,2))), ", ")) \\ G. C. Greubel, Feb 07 2018

a(n) = Sum_{k=0..n} t(k), where t = A000670 (ordered Bell numbers).
G.f. = A(x)/(1-x), where A(x) = g.f. for A000670 (see that entry). - N. J. A. Sloane, Apr 12 2014
a(n) ~ n! / (2* (log(2))^(n+1)). - Vaclav Kotesovec, Nov 08 2014

A208744 Triangle relating to ordered Bell numbers, A000670.

Original entry on oeis.org

1, 1, 2, 1, 3, 9, 1, 4, 18, 52, 1, 5, 30, 130, 375, 1, 6, 45, 260, 1125, 3246, 1, 7, 63, 455, 2625, 11361, 32781, 1, 8, 84, 728, 5250, 30296, 131124, 378344, 1, 9, 108, 1092, 9450, 68166, 393372, 1702548, 4912515, 1, 10, 135, 1560, 15750, 136332, 983430, 5675160, 24562575, 70872610

Offset: 1

Gary W. Adamson, Mar 05 2012

Row sums = A000670 starting (1, 3, 13, 75,...).
Right border = A052882 starting (1, 2, 9, 52, 375,...).
A000670 is the eigensequence of triangle A074909, deleting the first "1".
Triangle A074909 is the "beheaded" Pascal's triangle: (1; 1,2; 1,3,3;...).

			Row 4 (nonzero terms) = (1, 4, 18, 52) = termwise product of (1, 4, 6, 4) and (1, 1, 3, 13).
First few rows of the triangle:
1;
1, 2;
1, 3, 9;
1, 4, 18, 52;
1, 5, 30, 130, 375;
1, 6, 45, 260, 1125, 3246;
1, 7, 63, 455, 2625, 11361, 32781;
1, 8, 84, 728, 5250, 30296, 131124, 378344;
...

Cf. A000670, A052882, A154921.

Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i + k + r)*(i + r)^(n - r)/(i!*(k - i - r)!), {i, 0, k - r}], {k, r, n}]; Fubini[0, 1] = 1;
a[n_, k_] := Binomial[n, k] Fubini[k, 1];
Table[a[n, k], {n, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Mar 30 2016 *)

As infinite lower triangular matrices, A074909 * A000670 as the main diagonal and the rest zeros.

E.g.f. (exp(x) - 1)/(2 - exp(x*t)) = x + (1 + 2*t)*x^2/2! + (1 + 3*t + 9*t^2)*x^3/3! + .... Cf. A154921. - Peter Bala, Aug 31 2016

a(36) corrected by Jean-François Alcover, Mar 30 2016

A217388 Alternating sums of the ordered Bell numbers (number of preferential arrangements) A000670.

Original entry on oeis.org

1, 0, 3, 10, 65, 476, 4207, 43086, 502749, 6584512, 95663051, 1526969522, 26564598073, 500293750308, 10141049220135, 220142141757718, 5095512540223637, 125275254488912264, 3260259408767933059, 89541327910560478074, 2588146468333823725041

Offset: 0

Emanuele Munarini, Oct 02 2012

nonn

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Mathematics Stack Exchange, Simple closed form for signed partial sums of Fubini numbers, Aug 8 2025.

Cf. A000670, A006957, A005649, A217389, A217391, A217392.

List([0..30],n->Sum([0..n],k->(-1)^(n-k)*Sum([0..k], j-> Factorial(j)*Stirling2(k,j)))); # Muniru A Asiru, Feb 07 2018

A000670:=func;
[&+[(-1)^(n-k)*A000670(k): k in [0..n]]: n in [0..20]]; // Bruno Berselli, Oct 03 2012

with(combinat):
seq(sum((-1)^(n-k)*sum(factorial(j)*stirling2(k,j), j=0..k), k=0..n), n=0..30); # Muniru A Asiru, Feb 07 2018

t[n_] := Sum[StirlingS2[n, k]k!, {k, 0, n}]; Table[Sum[(-1)^(n - k)t[k], {k, 0, n}], {n, 0, 100}]
(* second program: *)
Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1; a[n_] := Sum[(-1)^(n-k) Fubini[k, 1], {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 31 2016 *)

t(n):=sum(stirling2(n,k)*k!,k,0,n);
makelist(sum((-1)^(n-k)*t(k),k,0,n),n,0,40);

for(n=0,30, print1(sum(k=0,n, (-1)^(n-k)*sum(j=0,k, j!*stirling(k,j,2))), ", ")) \\ G. C. Greubel, Feb 07 2018

a(n) = sum(k=0, n, k!*stirling(n+2,k+2,2)*(2^(k+1)-1)*(-1)^(n-k)) \\ Mikhail Kurkov, Aug 08 2025

a(n) = sum((-1)^(n-k)*t(k), k=0..n), where t = A000670 (ordered Bell numbers).
E.g.f.: 1/(2-exp(x))-exp(-x)*log(1/(2-exp(x))). [Typo corrected by Vaclav Kotesovec, Oct 08 2013]
G.f.: 1/(1+x)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(2*k+2)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 20 2013
a(n) ~ n! /(2*(log(2))^(n+1)). - Vaclav Kotesovec, Oct 08 2013
a(n) = Sum_{k=0..n} k!*Stirling2(n+2,k+2)*(2^(k+1)-1)*(-1)^(n-k). - Mikhail Kurkov, Aug 08 2025

A073146 Triangle of numbers {a(n,k), n >= 0, 0 <= k <= n} defined by a(0,0)=1, a(n,0)=A000670(n), a(n,n)=A000629(n), a(n,k) = a(n,k-1) + a(n-1,k-1); a(n+1,0) = Sum_{k=0..n} a(n,k).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 13, 16, 20, 26, 75, 88, 104, 124, 150, 541, 616, 704, 808, 932, 1082, 4683, 5224, 5840, 6544, 7352, 8284, 9366, 47293, 51976, 57200, 63040, 69584, 76936, 85220, 94586, 545835, 593128, 645104, 702304, 765344, 834928, 911864

Offset: 0

Paul D. Hanna, Jul 18 2002

Related to preferential arrangements of n elements (A000670) and necklaces of sets of labeled beads (A000629).

Row sums are 1, 3, 13, 75, 541, ... (A000670 starting from A000670(1), the second "1"). - Gary W. Adamson, May 31 2005

			Triangle begins:
    1;
    1,   2;
    3,   4,   6;
   13,  16,  20,  26;
   75,  88, 104, 124, 150;
  541, 616, 704, 808, 932, 1082;
  ...

D. Dumont, Matrices d'Euler-Seidel, Sem. Loth. Comb. B05c (1981) 59-78.

Cf. A000670, A000629, A011971.

Main diagonal is in A098696.

Fubini[n_, r_] := Sum[k!*Sum[(-1)^(i+k+r)*(i+r)^(n-r)/(i!*(k-i-r)!), {i, 0, k-r}], {k, r, n}]; Fubini[0, 1] = 1;
a[n_, k_] := Sum[Binomial[k, i-n+k] Fubini[i, 1], {i, n-k, n}];
Table[a[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 30 2016, after Vladeta Jovovic *)

From Vladeta Jovovic, Oct 15 2006: (Start)
Double-exponential generating function: Sum_{n, k} a(n-k, k) x^n/n! y^k/k! = exp(y)/(2-exp(x+y)).
a(n,k) = Sum_{i=n-k..n} binomial(k,i-n+k)*A000670(i). (End)

A095993 Inverse Euler transform of the ordered Bell numbers A000670.

Original entry on oeis.org

1, 1, 2, 10, 59, 446, 3965, 41098, 484090, 6390488, 93419519, 1498268466, 26159936547, 494036061550, 10035451706821, 218207845446062, 5057251219268460, 124462048466812950, 3241773988588098756, 89093816361187396674, 2576652694087142999421

Offset: 0

Mike Zabrocki, Jul 18 2004

nonn

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

Cf. A000670, A085686, A095989.

read transforms; A000670 := proc(n) option remember; local k; if n <=1 then 1 else add(binomial(n,k)*A000670(n-k),k=1..n); fi; end; [seq(A000670(i),i=1..30)]; EULERi(%);
# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(A000670):
seq(a(n), n = 0..22); # Peter Luschny, Nov 21 2022

max = 25; b[0] = 1; b[n_] := b[n] = Sum[Binomial[n, k]*b[n-k], {k, 1, n}]; bb = Array[b, max]; s = {}; For[i=1, i <= max, i++, AppendTo[s, i*bb[[i]] - Sum[s[[d]]*bb[[i-d]], {d, i-1}]]]; a[0] = 1; a[n_] := Sum[If[Divisible[ n, d], MoebiusMu[n/d], 0]*s[[d]], {d, 1, n}]/n; Table[a[n], {n, 0, max}] (* Jean-François Alcover, Feb 25 2017 *)

Product(1/(1-q^n)^(a(n)), n >=1) = sum(A000670(k)*q^k, k>=0).

a(n) ~ n! / (2 * log(2)^(n+1)). - Vaclav Kotesovec, Oct 09 2019

a(0)=1 inserted by Alois P. Heinz, Feb 20 2017

A122101 T(n,k) = Sum_{i=0..k} (-1)^(k-i)binomial(k,i)A000670(n-k+i).

Original entry on oeis.org

1, 1, 0, 3, 2, 2, 13, 10, 8, 6, 75, 62, 52, 44, 38, 541, 466, 404, 352, 308, 270, 4683, 4142, 3676, 3272, 2920, 2612, 2342, 47293, 42610, 38468, 34792, 31520, 28600, 25988, 23646, 545835, 498542, 455932, 417464, 382672, 351152, 322552, 296564, 272918

Offset: 0

Vladeta Jovovic, Oct 18 2006

			Triangle begins as:
     1;
     1,    0;
     3,    2,    2;
    13,   10,    8,    6;
    75,   62,   52,   44,   38;
   541,  466,  404,  352,  308,  270;
  4683, 4142, 3676, 3272, 2920, 2612, 2342;
  ...

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Columns k=0-1 give: A000670, A232472.
Row sums give A089677(n+1).
Main diagonal gives A052841.
T(2n,n) gives A340837.
Cf. A005649, A069321, A073146.

A000670:= function(n)
     return Sum([0..n], i-> Factorial(i)*Stirling2(n,i) ); end;
T:= function(n,k)
    return Sum([0..k], j-> (-1)^(k-j)*Binomial(k, j)*A000670(n-k+j) ); end;
Flat(List([0..10], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Oct 02 2019

A000670:= func< n | &+[Factorial(k)*StirlingSecond(n,k): k in [0..n]] >;
[(&+[(-1)^(k-j)*Binomial(k,j)*A000670(n-k+j): j in [0..k]]): k in [0..n], n in [0..10]]; // G. C. Greubel, Oct 02 2019

T:= (n, k)-> k!*(n-k)!*coeff(series(coeff(series(exp(-y)/
        (2-exp(x+y)), y, k+1), y, k), x, n-k+1), x, n-k):
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Oct 02 2019
# second Maple program:
b:= proc(n) option remember; `if`(n<2, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
T:= (n, k)-> add(binomial(k, j)*(-1)^j*b(n-j), j=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);  # Alois P. Heinz, Oct 02 2019

A000670[n_]:= If[n==0,1,Sum[k! StirlingS2[n, k], {k, n}]]; T[n_, k_]:= Sum[(-1)^(k-j)*Binomial[k, j]*A000670[n-k+j], {j,0,k}]; Table[T[n, k], {n,0,10}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 02 2019 *)

A000670(n) = sum(k=0,n, k!*stirling(n,k,2));
T(n,k) = sum(j=0,k, (-1)^(k-j)*binomial(k, j)*A000670(n-k+j));
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Oct 02 2019

def A000670(n): return sum(factorial(k)*stirling_number2(n,k) for k in (0..n))
def T(n,k): return sum((-1)^(k-j)*binomial(k, j)*A000670(n-k+j) for j in (0..k))
[[T(n,k) for k in (0..n)] for n in (0..10)]

Doubly-exponential generating function: Sum_{n, k} a(n-k,k) x^n/n! y^k/k! = exp(-y)/(2-exp(x+y)).

cp's OEIS Frontend

A060223 Number of orbits of length n under the map whose periodic points are counted by A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A075729 Number of different hierarchical orderings that can be formed from n labeled elements: these are divided into groups and the elements in each group are then arranged in a "preferential arrangement" or "weak order" as in A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A035317 Pascal-like triangle associated with A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A089677 Exponential convolution of A000670(n), with A000670(0)=0, with the sequence of all ones alternating in sign.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A217389 Partial sums of the ordered Bell numbers (number of preferential arrangements) A000670.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Formula

A208744 Triangle relating to ordered Bell numbers, A000670.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A122101 T(n,k) = Sum_{i=0..k} (-1)^(k-i)binomial(k,i)A000670(n-k+i).