A036077 -id:A036077 - cp's OEIS frontend

A162663 Table by antidiagonals, T(n,k) is the number of partitions of {1..(nk)} that are invariant under a permutation consisting of n k-cycles.

1, 1, 1, 1, 2, 2, 1, 2, 7, 5, 1, 3, 8, 31, 15, 1, 2, 16, 42, 164, 52, 1, 4, 10, 111, 268, 999, 203, 1, 2, 28, 70, 931, 1994, 6841, 877, 1, 4, 12, 258, 602, 9066, 16852, 51790, 4140, 1, 3, 31, 106, 2892, 6078, 99925, 158778, 428131, 21147, 1, 4, 22, 329, 1144, 37778, 70402, 1224579, 1644732, 3827967, 115975

Offset: 0

Franklin T. Adams-Watters, Jul 09 2009

The upper left corner of the array is T(0,1).
Without loss of generality, the permutation can be taken to be (1 2 ... k) (k+1 k+2 ... 2k) ... ((n-1)k+1 (n-1)k+2 ... nk).
Note that it is the partition that is invariant, not the individual parts. Thus for n=k=2 with permutation (1 2)(3 4), the partition 1,3|2,4 is counted; it maps to 2,4|1,3, which is the same partition.

			The table starts:
   1,   1,   1,   1,   1
   1,   2,   2,   3,   2
   2,   7,   8,  16,  10
   5,  31,  42, 111,  70
  15, 164, 268, 931, 602

Alois P. Heinz, Antidiagonals n = 0..140, flattened (first 20 antidiagonals from Franklin T. Adams-Watters)
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers

Columns: A000110, A002872, A002874, A141003, A036075, A141004, A036077, A141005, A141006, A141007, A036081, A141008, A141009, A141010, A141011.
Rows: A000012, A000005, A162664, A162665.
Cf. A084423, A036040, A036073, A080575.
Main diagonal gives A293850.

with(numtheory):
A:= proc(n, k) option remember; `if`(n=0, 1, add(binomial(n-1, j-1)
       *add(d^(j-1), d=divisors(k))*A(n-j, k), j=1..n))
    end:
seq(seq(A(n, 1+d-n), n=0..d), d=0..12);  # Alois P. Heinz, Oct 29 2015

max = 11; ClearAll[col]; col[k_] := col[k] =  CoefficientList[ Series[ Exp[ Sum[ (Exp[d*x] - 1)/d, {d, Divisors[k]}]], {x, 0, max}], x]*Range[0, max]!; t[n_, k_] := col[k][[n]]; Flatten[ Table[ t[n-k+1, k], {n, 1, max}, {k, n, 1, -1}] ] (* Jean-François Alcover, Aug 08 2012, after e.g.f. *)

amat(n,m)=local(r);r=matrix(n,m,i,j,1);for(k=1,n-1,for(j=1,m,r[k+1,j]=sum (i=1,k,binomial(k-1,i-1)*sumdiv(j,d,r[k-i+1,j]*d^(i-1)))));r
acol(n,k)=local(fn);fn=exp(sumdiv(k,d,(exp(d*x+x*O(x^n))-1)/d));vector(n+ 1,i,polcoeff(fn,i-1)*(i-1)!)

E.g.f. for column k: exp(Sum_{d|k} (exp(d*x) - 1) / d).
Equivalently, column k is the exponential transform of a(n) = Sum_{d|k} d^(n-1); this represents a set of n k-cycles, each repeating the same d elements (parts), but starting in different places.
T(n,k) = Sum_{P a partition of n} SP(P) * Product_( (sigma_{i-1}(k))^(P(i)-1) ), where SP is A036040 or A080575, and P(i) is the number of parts in P of size i.
T(n,k) = Sum_{j=0..n-1} A036073(n,j)*k^(n-1-j). - Andrey Zabolotskiy, Oct 22 2017

Offset set to 0 by Alois P. Heinz, Oct 29 2015

A002874 The number of partitions of {1..3n} that are invariant under a permutation consisting of n 3-cycles.

Original entry on oeis.org

1, 2, 8, 42, 268, 1994, 16852, 158778, 1644732, 18532810, 225256740, 2933174842, 40687193548, 598352302474, 9290859275060, 151779798262202, 2600663778494172, 46609915810749130, 871645673599372868, 16971639450858467002, 343382806080459389676

Offset: 0

N. J. A. Sloane, Simon Plouffe

Original name: Sorting numbers.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 0..484 (first 101 terms from T. D. Noe)
Vaclav Kotesovec, Graph - the asymptotic ratio (10000 terms)
Vaclav Kotesovec, Asymptotics for a certain group of exponential generating functions, arXiv:2207.10568 [math.CO], Jul 13 2022.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
J. Pasukonis, S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, arXiv:1010.1683 [hep-th], 2010, (E.3).
J. Pasukonis, S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, J. High En. Phys. 2011 (2) (2011), (E.3).
OEIS Wiki, Sorting numbers
Index entries for sequences related to sorting

u[n,j] generates for j=1, A000110; j=2, A002872; j=3, this sequence; j=4, A141003; j=5, A036075; j=6, A141004; j=7, A036077. - Wouter Meeussen, Dec 06 2008
Equals column 3 of A162663. - Michel Marcus, Mar 27 2013
Row sums of A294201.

S:= series(exp( (exp(3*x) - 4)/3 + exp(x)), x, 31):
seq(coeff(S,x,j)*j!, j=0..30); # Robert Israel, Oct 30 2015
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add((1+
      3^(j-1))*binomial(n-1, j-1)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 17 2017

u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; Table[u[n,3],{n,0,12}] (* Wouter Meeussen, Dec 06 2008 *)
mx = 16; p = 3; Range[0, mx]! CoefficientList[ Series[ Exp[ (Exp[p*x] - p - 1)/p + Exp[x]], {x, 0, mx}], x] (* Robert G. Wilson v, Dec 12 2012 *)
Table[Sum[Binomial[n,k] * 3^k * BellB[k, 1/3] * BellB[n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 29 2022 *)

E.g.f.: exp( (exp(3*x) - 4)/3 + exp(x) ).
a(n) ~ exp(exp(3*r)/3 + exp(r) - 4/3 - n) * (n/r)^(n + 1/2) / sqrt((1 + 3*r)*exp(3*r) + (1 + r)*exp(r)), where r = LambertW(3*n)/3 - 1/(1 + 3/LambertW(3*n) + n^(2/3) * (1 + LambertW(3*n)) * (3/LambertW(3*n))^(5/3)). - Vaclav Kotesovec, Jul 03 2022
a(n) ~ (3*n/LambertW(3*n))^n * exp(n/LambertW(3*n) + (3*n/LambertW(3*n))^(1/3) - n - 4/3) / sqrt(1 + LambertW(3*n)). - Vaclav Kotesovec, Jul 10 2022

New name from Danny Rorabaugh, Oct 24 2015

A084708 Number of set partitions up to rotations and reflections.

Original entry on oeis.org

1, 2, 3, 7, 12, 37, 93, 354, 1350, 6351, 31950, 179307, 1071265, 6845581, 46162583, 327731950, 2437753740, 18948599220, 153498350745, 1293123243928, 11306475314467, 102425554299516, 959826755336242, 9290811905391501

Offset: 1

Wouter Meeussen, Jul 02 2003

nonn

Combines the symmetry operations of A080107 and A084423.

Equivalently, number of n-bead bracelets using any number of unlabeled (interchangable) colors. - Andrew Howroyd, Sep 25 2017

			SetPartitions[6] is the first to decompose differently from A084423: 4 cycles of length 1, 2 of 2, 9 of 3, 16 of 6, 6 of 12.
a(7) = 1 + A056357(7) + A056358(7) + A056359(7) + A056360(7) + A056361(7) + 1 = 1 + 8 + 31 + 33 + 16 + 3 + 1 = 93.

Michael De Vlieger, Table of n, a(n) for n = 1..577
Colin Adams, Chaim Even-Zohar, Jonah Greenberg, Reuben Kaufman, David Lee, Darin Li, Dustin Ping, Theodore Sandstrom, and Xiwen Wang, Virtual Multicrossings and Petal Diagrams for Virtual Knots and Links, arXiv:2103.08314 [math.GT], 2021.
Tilman Piesk, Partition related number triangles
N. J. A. Sloane, Generating functions [From _Wouter Meeussen_, Dec 06 2008]

Cf. A080107, A084423, A080510, A002872, A002874, A141003, A036075, A141004, A036077, A152176.

<A080107 *); Table[{Length[ # ], First[ # ]}&/@ Split[Sort[Length/@Split[Sort[First[Sort[Flatten[ {#, Map[Sort, (#/. i_Integer:>w+1-i), 2]}& @(NestList[Sort[Sort/@(#/. i_Integer :> Mod[i+1, w, 1])]&, #, w]), 1]]]&/@SetPartitions[w]]]]], {w, 1, 10}]
u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; a[n_]:=1/n*Plus@@(EulerPhi[ # ]u[Quotient[n,# ],# ]&/@Divisors[n]); Table[a[n]/2+If[EvenQ[n],u[n/2,2],Sum[Binomial[n/2-1/2,k] u[k,2], {k,0,n/2-1/2}]]/2,{n,40}] (* Wouter Meeussen, Dec 06 2008 *)

a(n) = (A080107(n)+A084423(n))/2. - Wouter Meeussen and Vladeta Jovovic, Nov 28 2008

a(12) from Vladeta Jovovic, Jul 15 2007

More terms from Vladeta Jovovic's formula given in Mathematica line. - Wouter Meeussen, Dec 06 2008

A036075 The number of partitions of {1..5n} that are invariant under a permutation consisting of n 5-cycles.

Original entry on oeis.org

1, 2, 10, 70, 602, 6078, 70402, 917830, 13253002, 209350350, 3584098770, 66012131222, 1300004931162, 27232369503902, 604103160535330, 14136908333006822, 347827448896896554, 8971450949011952494

Offset: 0

N. J. A. Sloane

nonn

Original name: Sorting numbers.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Vaclav Kotesovec, Asymptotics for a certain group of exponential generating functions, arXiv:2207.10568 [math.CO], Jul 13 2022.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers
Index entries for sequences related to sorting

Cf. A001861, A002872-A002875, A036074.
u[n,j] generates for j=1, A000110 Bell numbers; j=2, A002872; j=3, A002874; j=4, A141003 (Mathar); j=5, this sequence; j=6, A141004 (Mathar); j=7, A036077. - Wouter Meeussen, Dec 06 2008
Column 5 of A162663.

u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; Table[u[n,5],{n,0,12}] (* Wouter Meeussen, Dec 06 2008 *)
mx = 16; p = 5; Range[0, mx]! CoefficientList[ Series[ Exp[ (Exp[p*x] - p - 1)/p + Exp[x]], {x, 0, mx}], x] (* Robert G. Wilson v, Dec 12 2012 *)
Table[Sum[Binomial[n,k] * 5^k * BellB[k, 1/5] * BellB[n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 29 2022 *)

E.g.f.: exp((exp(p*x)-p-1)/p+exp(x)) for p=5.
a(n) ~ exp(exp(p*r)/p + exp(r) - 1 - 1/p - n) * (n/r)^(n + 1/2) / sqrt((1 + p*r)*exp(p*r) + (1 + r)*exp(r)), where r = LambertW(p*n)/p - 1/(1 + p/LambertW(p*n) + n^(1 - 1/p) * (1 + LambertW(p*n)) * (p/LambertW(p*n))^(2 - 1/p)) for p=5. - Vaclav Kotesovec, Jul 03 2022
a(n) ~ (5*n/LambertW(5*n))^n * exp(n/LambertW(5*n) + (5*n/LambertW(5*n))^(1/5) - n - 6/5) / sqrt(1 + LambertW(5*n)). - Vaclav Kotesovec, Jul 10 2022

New name from Danny Rorabaugh, Oct 24 2015

A141004 Expansion of e.g.f. exp(Sum_{d|6} (exp(d*x)-1)/d).

Original entry on oeis.org

1, 4, 28, 258, 2892, 37778, 560124, 9256010, 168182044, 3325057826, 70934634236, 1621828212826, 39517131361884, 1021237022557682, 27877344103738940, 800976143703407210, 24148078430008534428, 761815206361252780098, 25087729474993723079548

Offset: 0

R. J. Mathar, Jul 11 2008

nonn

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

u[n,j] generates for j=1, A000110 Bell numbers; j=2, A002872 "Sorting numbers"; j=3, A002874 "Sorting numbers"; j=4, A141003 (Mathar); j=5, A036075 "Sorting numbers"; j=6, A141004 (Mathar); j=7, A036077 "Sorting numbers". - Wouter Meeussen, Dec 06 2008

Column k=6 of A162663.

u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; Table[u[n,6],{n,0,18}] (* Wouter Meeussen, Dec 06 2008 *)

cp's OEIS Frontend

A162663 Table by antidiagonals, T(n,k) is the number of partitions of {1..(nk)} that are invariant under a permutation consisting of n k-cycles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A002874 The number of partitions of {1..3n} that are invariant under a permutation consisting of n 3-cycles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A084708 Number of set partitions up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A036075 The number of partitions of {1..5n} that are invariant under a permutation consisting of n 5-cycles.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A141004 Expansion of e.g.f. exp(Sum_{d|6} (exp(d*x)-1)/d).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica