A136394 -id:A136394 - cp's OEIS frontend

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

1, 1, 1, 1, 1, 4, 1, 11, 3, 1, 26, 25, 1, 57, 130, 15, 1, 120, 546, 210, 1, 247, 2037, 1750, 105, 1, 502, 7071, 11368, 2205, 1, 1013, 23436, 63805, 26775, 945, 1, 2036, 75328, 325930, 247555, 27720, 1, 4083, 237127, 1561516, 1939630, 460845, 10395, 1, 8178

Offset: 0

Emeric Deutsch, Oct 28 2006

Row sums are the Bell numbers (A000110).
It appears that the triangles in this sequence and A112493 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
Equivalent to Jörgen Backelin's observation, the rows of A112493 may be read off as the diagonals of this entry. - Tom Copeland, Sep 24 2022

			T(4,2) = 3 because we have 12|34, 13|24 and 14|23 (if we take {1,2,3,4} as our 4-set).
Triangle starts:
  1;
  1;
  1,    1;
  1,    4;
  1,   11,     3;
  1,   26,    25;
  1,   57,   130,    15;
  1,  120,   546,   210;
  1,  247,  2037,  1750,   105;
  1,  502,  7071, 11368,  2205;
  1, 1013, 23436, 63805, 26775, 945;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Per Alexandersson and Olivia Nabawanda, Peaks are preserved under run-sorting, arXiv:2104.04220 [math.CO], 2021.
Fufa Beyene and Roberto Mantaci, Merging-Free Partitions and Run-Sorted Permutations, arXiv:2101.07081 [math.CO], 2021.
Tom Copeland, Appell-Bell polynomials: Linking the associated Bell polynomials and the associated reduced inverse refined Eulerian polynomials, 2022.
Tom Copeland, The reduced inverse refined Eulerian polynomials and associated arrays, 2022.
Robin Houston, Adam P. Goucher, and Nathaniel Johnston, A New Formula for the Determinant and Bounds on Its Tensor and Waring Ranks, arXiv:2301.06586 [math.CO], 2023.
O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run Distribution Over Flattened Partitions, arXiv:2007.03821 [math.CO], 2020.

Columns k=0-10 give: A000012, A000295, A112495, A112496, A112497, A290034, A290035, A290036, A290037, A290038, A290039.

Cf. A000110, A001147, A048993, A124323, A124325, A136394, A112493.

G:=exp(t*exp(z)-t+(1-t)*z): Gser:=simplify(series(G,z=0,36)): for n from 0 to 33 do P[n]:=sort(n!*coeff(Gser,z,n)) od: for n from 0 to 13 do seq(coeff(P[n],t,k),k=0..floor(n/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      `if`(i>1, x, 1)*binomial(n-1, i-1)*b(n-i), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Mar 08 2015, Jul 15 2017

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] :=  b[n, i] = Expand[If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1]*If[i>1, x^j, 1], {j, 0, n/i}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, n]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 22 2015, after Alois P. Heinz *)

E.g.f.: G(t,z) = exp(t*exp(z) - t + (1-t)*z).
T(n,1) = A000295(n) (the Eulerian numbers).
Sum_{k=0..floor(n/2)} k*T(n,k) = A124325(n).
T(2n,n) = A001147(n). - Alois P. Heinz, Apr 06 2018

A006231 a(n) = Sum_{k=2..n} n(n-1)...(n-k+1)/k.

Original entry on oeis.org

0, 1, 5, 20, 84, 409, 2365, 16064, 125664, 1112073, 10976173, 119481284, 1421542628, 18348340113, 255323504917, 3809950976992, 60683990530208, 1027542662934897, 18430998766219317, 349096664728623316, 6962409983976703316, 145841989688186383337

Offset: 1

R. K. Guy

a(n) is also the number of permutations in the symmetric group S_n that are pure cycles, see example. - Avi Peretz (njk(AT)netvision.net.il), Mar 24 2001
Also the number of elementary circuits in a complete directed graph with n nodes [D. B. Johnson, 1975]. - N. J. A. Sloane, Mar 24 2014
If one takes 1,2,3,4, ..., n and starts creating parenthetic products of k-tuples and adding, one gets a(n+1). For 1,2,3,4 one gets (1)+(2)+(3)+(4) = 10; (1*2)+(2*3)+(3*4) = 20; (1*2*3)+(2*3*4) = 30; (1*2*3*4) = 24; and 10+20+30+24 = 84 = a(5). - J. M. Bergot, Apr 24 2014
Let P_n be the set of probability distributions over orderings of n objects that can be obtained by drawing n real numbers from independent probability distributions and sorting. Then a(n) is conjectured to be the dimension of P_n, as a semi-algebraic subset of R^(n!). - Jamie Tucker-Foltz, Jul 29 2024

			a(3) = 5 because the cycles in S_3 are (12), (13), (23), (123), (132).
a(4) = 20 because there are 24 permutations of {1,2,3,4} but we don't count (12)(34), (13)(24), (14)(23) or the identity permutation. - _Geoffrey Critzer_, Nov 03 2012

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from T. D. Noe)
Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, Jamie Tucker-Foltz, Models of Random Spanning Trees, arXiv:2407.20226 [math.CO], 2023.
R. K. Guy, Letter to N. J. A. Sloane, 1977
Donald B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput. 4 (1975), 77-84. MR0398155 (53 #2010).
Jamie Tucker-Foltz, Code to compute dimension of P_n on GitHub.

Cf. A059760, A000295.

Column k=1 of A136394.

a006231 n = numerator $
   sum $ tail $ zipWith (%) (scanl1 (*) [n,(n-1)..1]) [1..n]
-- Reinhard Zumkeller, Dec 27 2011

A006231 := proc(n)
    n*( hypergeom([1,1,1-n],[2],-1)-1) ;
    simplify(%) ;
end proc: # R. J. Mathar, Aug 06 2013

a[n_] = n*(HypergeometricPFQ[{1,1,1-n}, {2}, -1] - 1); Table[a[n], {n, 1, 20}] (* Jean-François Alcover,  Mar 29 2011 *)
Table[Sum[Times@@Range[n-k+1,n]/k,{k,2,n}],{n,20}] (* Harvey P. Dale, Sep 23 2011 *)

a(n) = n--; sum(ip=1, n, sum(j=1, n-ip+1, prod(k=j, j+ip-1, k))); \\ Michel Marcus, May 07 2014 after comment by J. M. Bergot

a(n+1) - a(n) = A000522(n) - 1.
a(n) = n*( 3F1(1,1,1-n; 2;-1) -1). - Jean-François Alcover,  Mar 29 2011
E.g.f.: exp(x)*(log(1/(1-x))-x). - Geoffrey Critzer, Sep 12 2012
G.f.: (Q(0) - 1)/(1-x)^2, where Q(k)= 1 + (2*k + 1)*x/( 1 - x - 2*x*(1-x)*(k+1)/(2*x*(k+1) + (1-x)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 09 2013
Conjecture: a(n) + (-n-2)*a(n-1) + (3*n-2)*a(n-2) + 3*(-n+2)*a(n-3) + (n-3)*a(n-4) = 0. - R. J. Mathar, Aug 06 2013

More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2

Offset: 0

Antti Karttunen, Apr 18 2000

nonn

Among the first n! entries k appears A136394(n,k) times. - Tilman Piesk, Apr 06 2012

Tilman Piesk, Table of n, a(n) for n = 0..5039
Tilman Piesk, Table for A198380 (a[n] is the number of addends in parentheses on the right of this table)
Tilman Piesk, Permutations and partitions in the OEIS (Wikiversity)
Index entries for sequences related to factorial base representation

Cf. A195663, A195664, A055089 (ordered finite permutations).
Cf. A198380 (cycle type of the n-th finite permutation).
Cf. A136394, A055089, A055090, A055093, A055091, A060128, A290095.

with(group); seq(nops(convert(PermRevLexUnrank(j),'disjcyc')),j=0..)];
# Procedure PermRevLexUnrank given in A055089.

a(n) = A055093(n) - A055091(n).

a(n) = A056170(A290095(n)) = A060128(A060126(n)). - Antti Karttunen, Dec 30 2017

Name changed by Tilman Piesk, Apr 06 2012

A289950 Number of permutations of [n] having exactly two nontrivial cycles.

Original entry on oeis.org

3, 35, 295, 2359, 19670, 177078, 1738326, 18607446, 216400569, 2721632121, 36842898989, 534442231933, 8273657327788, 136186274940140, 2375469940958988, 43774887758841996, 849887136894382191, 17340752094929572431, 370979946172969657107, 8304215235537338992931

Offset: 4

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

			a(4) = 3: (12)(34), (13)(24), (14)(23).

Alois P. Heinz, Table of n, a(n) for n = 4..450
Wikipedia, Permutation

Column k=2 of A136394.

S:= series((log(1-x)+x)^2/2*exp(x), x, 31):
seq(coeff(S,x,j)*j!,j=4..30); # Robert Israel, Mar 22 2018

Drop [Range[0, 30]! CoefficientList[Series[(Log[1 - x] + x)^2 / 2 Exp[x], {x, 0, 30}], x], 4] (* Vincenzo Librandi, Jul 22 2017 *)

x='x+O('x^99); Vec(serlaplace((log(1-x)+x)^2/2*exp(x))) \\ Altug Alkan, Mar 22 2018

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

-(n+1)*(n+2)*(n+3)*(n+4)*a(n)+(5+3*n)*(n+4)*(n+3)*(n+2)*a(n+1)-(n+4)*(n+3)*(3*n^2+15*n+16)*a(n+2)+(n+4)*(n^3+12*n^2+38*n+32)*a(n+3)-(2*n^3+18*n^2+48*n+35)*a(n+4)+(n+3)*(n+1)*a(n+5)=0. - Robert Israel, Mar 22 2018

A289951 Number of permutations of [n] having exactly three nontrivial cycles.

Original entry on oeis.org

15, 315, 4480, 56672, 703430, 8941790, 118685336, 1658897240, 24494859389, 382301179169, 6302039460704, 109568927676192, 2005758201911884, 38588518087076860, 778794884783432176, 16458419973887378416, 363578176719852275467, 8381709371219530604071

Offset: 6

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 6..450
Wikipedia, Permutation

Column k=3 of A136394.

Drop [Range[0, 30]! CoefficientList[Series[(-Log[1 - x] - x)^3 / 3! Exp[x], {x, 0, 30}], x], 6] (* Vincenzo Librandi, Jul 22 2017 *)

E.g.f.: (-log(1-x)-x)^3/3!*exp(x).

A289952 Number of permutations of [n] having exactly four nontrivial cycles.

Original entry on oeis.org

105, 3465, 74025, 1346345, 23079595, 391180075, 6719395683, 118538975555, 2163255564470, 40995539853814, 808279043604630, 16591622809290774, 354584560193653306, 7886213669622441146, 182405117548079061482, 4383906242299647034026, 109380730176142312738279

Offset: 8

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 8..450
Wikipedia, Permutation

Column k=4 of A136394.

Drop[Range[0, 30]! CoefficientList[Series[(Log[1 - x] + x)^4 / 4! Exp[x], {x, 0, 30}], x], 8] (* Vincenzo Librandi, Jul 23 2017 *)

E.g.f.: (log(1-x)+x)^4/4!*exp(x).

A289953 Number of permutations of [n] having exactly five nontrivial cycles.

Original entry on oeis.org

945, 45045, 1344420, 33093060, 745860115, 16201119935, 348820952480, 7567361882080, 167057902281270, 3775807346835342, 87699348621850680, 2098002630307972920, 51760647309783259386, 1317835530989933266850, 34632875559239201852608, 939407586052413176727424

Offset: 10

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 10..450
Wikipedia, Permutation

Column k=5 of A136394.

Drop[Range[0, 30]! CoefficientList[Series[(-Log[1 - x] - x)^5 / 5! Exp[x], {x, 0, 30}], x], 10] (* Vincenzo Librandi, Jul 23 2017 *)

E.g.f.: (-log(1-x)-x)^5/5!*exp(x).

A289954 Number of permutations of [n] having exactly six nontrivial cycles.

Original entry on oeis.org

10395, 675675, 26801775, 855870015, 24479795340, 661680519500, 17424049022380, 455359195951660, 11950227130952110, 317363732767667950, 8572733672197564870, 236346930206430701350, 6665648338618807806268, 192596934884274256728700, 5706700987506640526104700

Offset: 12

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 12..450
Wikipedia, Permutation

Column k=6 of A136394.

Drop[Range[0, 30]! CoefficientList[Series[(Log[1 - x] + x)^6 / 6! Exp[x], {x, 0, 30}], x], 12] (* Vincenzo Librandi, Jul 24 2017 *)

x = 'x + O('x^30); Vec(serlaplace((log(1-x)+x)^6/6!*exp(x))) \\ Michel Marcus, Jul 24 2017

E.g.f.: (log(1-x)+x)^6/6!*exp(x).

A289955 Number of permutations of [n] having exactly seven nontrivial cycles.

Original entry on oeis.org

135135, 11486475, 583783200, 23434451040, 828052325100, 27221423409180, 859752405431920, 26617555964919920, 818486200464162230, 25221598500336187950, 783666055857936771520, 24658659357394687609600, 788174700361283653718300, 25647112073453527447490700

Offset: 14

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 14..450
Wikipedia, Permutation

Column k=7 of A136394.

Drop[CoefficientList[Series[(-Log[1 - x] - x)^7/7!*Exp[x] , {x, 0, 50}], x] * Table[k !, {k, 0, 50}] , 14] (* Indranil Ghosh, Jul 16 2017 *)

x = 'x + O('x^30); Vec(serlaplace((-log(1-x)-x)^7/7!*exp(x))) \\ Michel Marcus, Jul 16 2017

E.g.f.: (-log(1-x)-x)^7/7!*exp(x).

A289956 Number of permutations of [n] having exactly eight nontrivial cycles.

Original entry on oeis.org

2027025, 218243025, 13818229425, 680438103345, 29079209884725, 1141483113695925, 42556765607801445, 1539279211706361125, 54789078082648965055, 1938102614993339970175, 68612592434209034386175, 2443274471026078967051775, 87839862102761225799417075

Offset: 16

Alois P. Heinz, Jul 16 2017

nonn

A nontrivial cycle has size > 1.

Alois P. Heinz, Table of n, a(n) for n = 16..450
Wikipedia, Permutation

Column k=8 of A136394.

Drop[CoefficientList[Series[(Log[1 - x] + x)^8/8!*Exp[x] , {x, 0, 50}], x] * Table[k !, {k, 0, 50}] , 16] (* Indranil Ghosh, Jul 16 2017 *)

x = 'x + O('x^30); Vec(serlaplace((-log(1-x)-x)^8/8!*exp(x))) \\ Michel Marcus, Jul 16 2017

E.g.f.: (log(1-x)+x)^8/8!*exp(x).

cp's OEIS Frontend

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006231 a(n) = Sum_{k=2..n} n(n-1)...(n-k+1)/k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A055090 Number of cycles (excluding fixed points) of the n-th finite permutation in reversed colexicographic ordering (A055089).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

Extensions

A289950 Number of permutations of [n] having exactly two nontrivial cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A289951 Number of permutations of [n] having exactly three nontrivial cycles.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A289952 Number of permutations of [n] having exactly four nontrivial cycles.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A289953 Number of permutations of [n] having exactly five nontrivial cycles.

Views

Author

Keywords

Comments

Links

Crossrefs