A293181 -id:A293181 - cp's OEIS frontend

A304972 Triangle read by rows of achiral color patterns (set partitions) for a row or loop of length n. T(n,k) is the number using exactly k colors (sets).

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 10, 9, 3, 1, 1, 7, 19, 16, 12, 3, 1, 1, 15, 38, 53, 34, 18, 4, 1, 1, 15, 65, 90, 95, 46, 22, 4, 1, 1, 31, 130, 265, 261, 195, 80, 30, 5, 1, 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1, 1, 63, 422, 1221, 1700, 1696, 1016, 515, 155, 45, 6, 1, 1, 63, 665, 2002

Offset: 1

Robert A. Russell, May 22 2018

Two color patterns are equivalent if we permute the colors. Achiral color patterns must be equivalent if we reverse the order of the pattern.

			Triangle begins:
1;
1,   1;
1,   1,    1;
1,   3,    2,    1;
1,   3,    5,    2,     1;
1,   7,   10,    9,     3,     1;
1,   7,   19,   16,    12,     3,     1;
1,  15,   38,   53,    34,    18,     4,    1;
1,  15,   65,   90,    95,    46,    22,    4,    1;
1,  31,  130,  265,   261,   195,    80,   30,    5,    1;
1,  31,  211,  440,   630,   461,   295,  100,   35,    5,   1;
1,  63,  422, 1221,  1700,  1696,  1016,  515,  155,   45,   6,  1
1,  63,  665, 2002,  3801,  3836,  3156, 1556,  710,  185,  51,  6, 1;
1, 127, 1330, 5369, 10143, 13097, 10508, 6832, 2926, 1120, 266, 63, 7, 1;
For T(4,2)=3, the row patterns are AABB, ABAB, and ABBA.  The loop patterns are AAAB, AABB, and ABAB.
For T(5,3)=5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Ira Gessel, What is the number of achiral color patterns for a row of n colors containing k different colors?, mathoverflow, Jan 30 2018.
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.

Columns 1-6 are A057427, A052551(n-2), A304973, A304974, A304975, A304976.
A305008 has coefficients that determine the function and generating function for each column.
Row sums are A080107.

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]]
Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten
Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],
  OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],
  True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]
Table[Ach[n, k], {n, 1, 15}, {k, 1, n}] // Flatten

Ach(n)={my(M=matrix(n,n,i,k,i>=k)); for(i=3, n, for(k=2, n, M[i,k]=k*M[i-2,k] + M[i-2,k-1] + if(k>2, M[i-2,k-2]))); M}
{ my(A=Ach(10)); for(n=1, #A, print(A[n,1..n])) } \\ Andrew Howroyd, Sep 18 2019

T(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [n<2 & n==k & n>=0].
T(2m-1,k) = A140735(m,k).
T(2m,k) = A293181(m,k).
T(n,k) = [k==0 & n==0] + [k==1 & n>0]
  + [k>1 & n==1 mod 2] * Sum_{i=0..(n-1)/2} (C((n-1)/2, i) * T(n-1-2i, k-1))
  + [k>1 & n==0 mod 2] * Sum_{i=0..(n-2)/2} (C((n-2)/2, i) * (T(n-2-2i, k-1)
  + 2^i * T(n-2-2i, k-2))) where C(n,k) is a binomial coefficient.

A002872 Number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles.

Original entry on oeis.org

1, 2, 7, 31, 164, 999, 6841, 51790, 428131, 3827967, 36738144, 376118747, 4086419601, 46910207114, 566845074703, 7186474088735, 95318816501420, 1319330556537631, 19013488408858761, 284724852032757686, 4422344774431494155, 71125541977466879231

Offset: 0

N. J. A. Sloane, Simon Plouffe

Previous name was: Sorting numbers.
a(n) = number of symmetric partitions of the set {-n,...,-1,1,...,n}. A partition of {-n,...,-1,1,...,n} into nonempty subsets X_1,...,X_k is 'symmetric' if for each i, -X_i=X_j for some j. a(n) = S_B(n,1)+...+S_B(n,n) where S_B(n,k) is as in A085483. a(n) is the n-th Bell number of 'type B'. - James East, Aug 18 2003
Column 2 of A162663. - Franklin T. Adams-Watters, Jul 09 2009
a(n) is equal to the sum of all expressions of the form p(1^n)[st(lambda)] for partitions lambda of order less than or equal to n, where p(1^n)[st(lambda)] denotes the coefficient of the irreducible character basis element indexed by the partition lambda in the expansion of the power sum basis element indexed by the partition (1^n). - John M. Campbell, Sep 16 2017
Number of achiral color patterns in a row or loop of length 2n. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 24 2018
Stirling transform of A005425 per Knuth reference. - Robert A. Russell, Apr 28 2018

			For a(2)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD.  The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 24 2018

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765). - Robert A. Russell, Apr 28 2018
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..513 (first 101 terms from T. D. Noe)
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 12, 18, 29.
T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.
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 and S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, arXiv:1010.1683 [hep-th], 2010, (E.2).
J. Pasukonis and S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, J. High En. Phys. 2011 (2) (2011), (E.2).
OEIS Wiki, Sorting numbers
R. Orellana and M. Zabrocki, Symmetric group characters as symmetric functions, arXiv preprint arXiv:1605.06672 [math.CO], 2016-2017.
J. Quaintance, Letter representations of rectangular m x n x p proper arrays, arXiv:math/0412244 [math.CO], 2004-2006.
Index entries for sequences related to sorting

Cf. A002873, A002874, A080107, A085483.
u[n,j] is A162663.
Row sums of A293181.
Column k=2 of A306024.
Cf. A005425.

a:= proc(n) option remember; `if`(n=0, 1, add((1+
      2^(j-1))*binomial(n-1, j-1)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 29 2015

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,2],{n,0,12}] (* Wouter Meeussen, Dec 06 2008 *)
mx = 16; p = 2; 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 *)
Aeven[m_, k_] := Aeven[m, k] = If[m>0, k Aeven[m-1, k] + Aeven[m-1, k-1]
  + Aeven[m-1, k-2], Boole[m==0 && k==0]]
Table[Sum[Aeven[m, k], {k, 0, 2m}], {m, 0, 30}] (* Robert A. Russell, Apr 24 2018 *)
x[n_] := x[n] = If[n<2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[n, k] x[k], {k, 0, n}], {n, 0, 20}] (* Robert A. Russell, Apr 28 2018, from Knuth reference *)
Table[Sum[Binomial[n,k] * 2^k * BellB[k, 1/2] * BellB[n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 29 2022 *)

E.g.f.: e^( (e^(2x) - 3)/2 + e^x ).
a(n) = A080107(2n) for all n. - Jörgen Backelin, Jan 13 2016
From Robert A. Russell, Apr 24 2018: (Start)
Aeven(n,k) = [n>0]*(k*Aeven(n-1,k)+Aeven(n-1,k-1)+Aeven(n-1,k-2))
  + [n==0]*[k==0]
a(n) = Sum_{k=0..2n} Aeven(n,k). (End)
a(n) = Sum_{k=0..n} Stirling2(n, k)*A005425(k). (from Knuth reference) - Robert A. Russell, Apr 28 2018
a(n) ~ exp(exp(2*r)/2 + exp(r) - 3/2 - n) * (n/r)^(n + 1/2) / sqrt((1 + 2*r)*exp(2*r) + (1 + r)*exp(r)), where r = LambertW(2*n)/2 - 1/(1 + 2/LambertW(2*n) + n^(1/2) * (1 + LambertW(2*n)) * (2/LambertW(2*n))^(3/2)). - Vaclav Kotesovec, Jul 03 2022
a(n) ~ (2*n/LambertW(2*n))^n * exp(n/LambertW(2*n) + (2*n/LambertW(2*n))^(1/2) - n - 7/4) / sqrt(1 + LambertW(2*n)). - Vaclav Kotesovec, Jul 10 2022

Edited by Franklin T. Adams-Watters, Jul 09 2009

A152176 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations and reflections.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 14, 11, 3, 1, 1, 8, 31, 33, 16, 3, 1, 1, 17, 82, 137, 85, 27, 4, 1, 1, 22, 202, 478, 434, 171, 37, 4, 1, 1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1, 1, 62, 1401, 6845, 11530, 8389, 3056, 590, 70, 5, 1, 1, 121, 3838, 26148

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of bracelet structures of length n using exactly k different colored beads. Turning over will not create a new bracelet. Permuting the colors of the beads will not change the structure. - Andrew Howroyd, Apr 06 2017
The number of achiral structures (A) is given in A140735 (odd n) and A293181 (even n).  The number of achiral structures plus twice the number of chiral pairs (A+2C) is given in A152175.  These can be used to determine A+C by taking half their average, as is done in the Mathematica program. - Robert A. Russell, Feb 24 2018
T(n,k)=pi_k(C_n) which is the number of non-equivalent partitions of the cycle on n vertices, with exactly 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

			Triangle begins:
  1;
  1,  1;
  1,  1,   1;
  1,  3,   2,    1;
  1,  3,   5,    2,    1;
  1,  7,  14,   11,    3,    1;
  1,  8,  31,   33,   16,    3,   1;
  1, 17,  82,  137,   85,   27,   4,  1;
  1, 22, 202,  478,  434,  171,  37,  4, 1;
  1, 43, 538, 1851, 2271, 1249, 338, 54, 5, 1;
  ...

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles
Marko Riedel, Bracelets with swappable colors classified by the distribution of colors, Power Group Enumeration algorithm
Marko Riedel, Maple code for the number of bracelets with some number of swappable colors by Power Group Enumeration
Mohammad Hadi Shekarriz, GAP Program

Columns 2-6 are A056357, A056358, A056359, A056360, A056361.
Row sums are A084708.
Partial row sums include A000011, A056353, A056354, A056355, A056356.
Cf. A081720, A273891, A008277 (set partitions), A284949 (up to reflection), A152175 (up to rotation).

Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
  1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
  True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
Ach[n_, k_] := Ach[n, k] = Switch[k, 0, If[0==n, 1, 0], 1, If[n>0, 1, 0],
  (* else *) _, If[OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1],
  {i, 0, (n-1)/2}], Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]] (* achiral loops of length n, k colors *)
Table[(CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x]
+ Table[Ach[n, k],{k,1,n}])/2, {n, 1, 20}] // Flatten (* Robert A. Russell, Feb 24 2018 *)

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(DihedralPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

\\ Ach is A304972 and R is A152175 as square matrices.
Ach(n)={my(M=matrix(n, n, i, k, i>=k)); for(i=3, n, for(k=2, n, M[i, k]=k*M[i-2, k] + M[i-2, k-1] + if(k>2, M[i-2, k-2]))); M}
R(n)={Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
T(n)={(R(n) + Ach(n))/2}
{ my(A=T(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 7, 18, 13, 3, 1, 1, 9, 43, 50, 20, 3, 1, 1, 19, 126, 221, 136, 36, 4, 1, 1, 29, 339, 866, 773, 296, 52, 4, 1, 1, 55, 946, 3437, 4281, 2303, 596, 78, 5, 1, 1, 93, 2591, 13250, 22430, 16317, 5817, 1080, 105, 5, 1, 1, 179, 7254, 51075, 115100, 110462, 52376, 13299, 1873, 147, 6, 1

Offset: 1

Vladeta Jovovic, Nov 27 2008

Number of n-bead necklace structures using exactly k different colored beads. Turning over the necklace is not allowed. Permuting the colors does not change the structure. - Andrew Howroyd, Apr 06 2017

			Triangle begins with T(1,1):
  1;
  1,   1;
  1,   1,     1;
  1,   3,     2,      1;
  1,   3,     5,      2,      1;
  1,   7,    18,     13,      3,      1;
  1,   9,    43,     50,     20,      3,      1;
  1,  19,   126,    221,    136,     36,      4,      1;
  1,  29,   339,    866,    773,    296,     52,      4,     1;
  1,  55,   946,   3437,   4281,   2303,    596,     78,     5,    1;
  1,  93,  2591,  13250,  22430,  16317,   5817,   1080,   105   , 5,   1;
  1, 179,  7254,  51075, 115100, 110462,  52376,  13299,  1873,  147,   6, 1;
  1, 315, 20125, 194810, 577577, 717024, 439648, 146124, 27654, 3025, 187, 6, 1;
  ...
For T(4,2)=3, the set partitions are AAAB, AABB, and ABAB.
For T(4,3)=2, the set partitions are AABC and ABAC.

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]

Andrew Howroyd, Table of n, a(n) for n = 1..1275
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Tilman Piesk, Partition related number triangles

Columns 2-6 are A056295, A056296, A056297, A056298, A056299.
Row sums are A084423.
Partial row sums include A000013, A002076, A056292, A056293, A056294.
Cf. A075195, A087854, A008277 (set partitions), A284949 (up to reflection), A152176 (up to rotation and reflection).
A(1,n,k) in formula is the Stirling subset number A008277.
A(2,n,k) in formula is A293181; A(3,n,k) in formula is A294201.

(* Using recursion formula from Gilbert and Riordan:*)
Adn[d_, n_] := Adn[d, n] = Which[0==n, 1, 1==n, DivisorSum[d, x^# &],
  1==d, Sum[StirlingS2[n, k] x^k, {k, 0, n}],
  True, Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n - 1], x] x]];
Table[CoefficientList[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &]/(x n), x],
   {n, 1, 10}] // Flatten (* Robert A. Russell, Feb 23 2018 *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#] &], Boole[n==0 && k==0]]
Table[DivisorSum[n,EulerPhi[#]Adnk[#,n/#,k]&]/n,{n,1,12},{k,1,n}] // Flatten (* Robert A. Russell, Oct 16 2018 *)

\\ see A056391 for Polya enumeration functions
T(n,k) = NonequivalentStructsExactly(CyclicPerms(n), k); \\ Andrew Howroyd, Oct 14 2017

R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace(-1 + exp(sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d))), x, x^m))/x))]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Sep 20 2019

T(n,k) = (1/n)*Sum_{d|n} phi(d)*A(d,n/d,k), where A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)). - Robert A. Russell, Oct 16 2018

A056182 First differences of A003063.

Original entry on oeis.org

0, 2, 10, 38, 130, 422, 1330, 4118, 12610, 38342, 116050, 350198, 1054690, 3172262, 9533170, 28632278, 85962370, 258018182, 774316690, 2323474358, 6971471650, 20916512102, 62753730610, 188269580438, 564825518530, 1694510110022, 5083597438930, 15250926534518, 45753048039010

Offset: 0

N. J. A. Sloane, Aug 05 2000

Let V be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xVy if x is a proper subset of y or y is a proper subset of x. Then a(n) = |V|. - Ross La Haye, Dec 22 2006
With regard to the comment by Ross La Haye: For nonempty subsets see a(n+1) in A260217. - If "proper" is omitted see A027649. - For nonempty subsets with "proper" omitted see A091344. - Manfred Boergens, Sep 04 2023
It appears that a(n) is the number of permutations p of 1,..,(n+2) such that max[p(i+1)-p(i)] is 2.  For example, for n=1, the permutations (1,3,2) and (2,1,3) and no others have the desired property, so a(1)=2.  This approach gives values in agreement with all listed terms. [John W. Layman, Nov 09 2011]
In the terdragon curve, a(n-1) is the number of enclosed unit triangles in expansion level n. - Kevin Ryde, Oct 20 2020

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Kevin Ryde, Iterations of the Terdragon Curve, see index "A area".
Index entries for linear recurrences with constant coefficients, signature (5,-6).

3rd column of A056151.  Cf. A028243 (partial sums).
A002783(n) - 1.
a(n) = A293181(n+1,3).
Cf. A001047, A027649, A091344, A217764, A260217.

A056182:=n->2 * (3^n - 2^n); seq(A056182(n), n=0..30); # Wesley Ivan Hurt, Feb 10 2014

Table[ -((-1 + k)^(1-k+n)*(-1+k)!)+k^(-k+n)*k! /. k -> 3, {n, 3, 36} ]
Table[2 (3^n - 2^n), {n, 0, 30}] (* Wesley Ivan Hurt, Feb 10 2014 *)
CoefficientList[Series[2 x/((2 x - 1) (3 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Feb 12 2014 *)
LinearRecurrence[{5,-6},{0,2},30] (* Harvey P. Dale, Sep 22 2015 *)

a(n) = 2 * (3^n - 2^n).
a(n) = 5*a(n-1)-6*a(n-2). G.f.: 2*x/((2*x-1)*(3*x-1)). [Colin Barker, Dec 10 2012]
a(n) = A217764(n,3). - Ross La Haye, Mar 27 2013
a(n) = sum_{i=1..n} binomial(n, i) * 2^(n - i + 1). - Wesley Ivan Hurt, Feb 10 2014
a(n) = 2 * A001047(n). - Wesley Ivan Hurt, Feb 10 2014
E.g.f.: 2*exp(2*x)*(exp(x) - 1). - Stefano Spezia, May 18 2024

More terms from Wouter Meeussen, Aug 05 2000

A002873 The maximal number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles, and which have the same number of nonempty parts.

Original entry on oeis.org

1, 1, 3, 10, 53, 265, 1700, 13097, 96796, 829080, 8009815, 75604892, 808861988, 9175286549, 106167118057, 1320388106466, 16950041305210, 233232366601078, 3243603207488124, 47776065074368313, 733990397879859192, 11515503147927664816, 189107783918416912912

Offset: 0

N. J. A. Sloane

Previous name was: Sorting numbers (see Motzkin article for details).

Since a(n) by definition is the largest among some positive integers, whose sum is A002872(n), we always have the relation a(n) <= A002872(n); and for n > 0 the inequality is strict, since then that sum consists of more than one term. - Jörgen Backelin, Jan 13 2016

			There are three partitions of {1,2,3,4} into two (nonempty) parts, and which are invariant under the permutation (1,2)(3,4), namely {{1,2}, {3,4}}, {{1,3}, {2,4}}, and {{1,4}, {2,3}}. There are also one such partition with just one part, two with three parts, and one with four parts; but three is the largest of these amounts. Thus, a(2) = 3.
Similarly, there are ten (1,2)(3,4)(5,6) invariant partitions of {1,2,3,4,5,6} into three nonempty parts, and no larger amount into any other given number of parts, whence a(3) = 10.

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..514
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]
OEIS Wiki, Sorting numbers
Index entries for sequences related to sorting

Cf. A000262 (the parent sequence of this family), A002872.

Maximum row values of A293181.

Name changed and example added by Jörgen Backelin, Jan 13 2016
a(7)-a(8) from Sean A. Irvine, Jun 19 2016
a(9)-a(22) from Andrew Howroyd, Oct 01 2017

A140735 Triangle read by rows, X^n * [1,0,0,0,...]; where X = a tridiagonal matrix with (1,2,3,...) in the main diagonal and (1,1,1,...) in the sub and subsubdiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 5, 2, 1, 1, 7, 19, 16, 12, 3, 1, 1, 15, 65, 90, 95, 46, 22, 4, 1, 1, 31, 211, 440, 630, 461, 295, 100, 35, 5, 1, 1, 63, 665, 2002, 3801, 3836, 3156, 1556, 710, 185, 51, 6, 1, 1, 127, 2059, 8736, 21672, 28819, 29729, 19440, 11102, 4116, 1456, 308, 70

Offset: 1

Gary W. Adamson, May 25 2008

T(m,k) is the number of achiral color patterns in a row or loop of length 2m-1 using exactly k different colors. Two color patterns are equivalent if we permute the colors. - Robert A. Russell, Mar 24 2018

			First few rows of the triangle are:
  1;
  1,  1,   1;
  1,  3,   5,    2,    1;
  1,  7,  19,   16,   12,    3,    1;
  1, 15,  65,   90,   95,   46,   22,    4,   1;
  1, 31, 211,  440,  630,  461,  295,  100,  35,   5,  1;
  1, 63, 665, 2002, 3801, 3836, 3156, 1556, 710, 185, 51, 6, 1;
  ...
T(3,3)=5 is the number of achiral color patterns of length five using exactly three colors. These are AABCC, ABACA, ABBBC, ABCAB, and ABCBA for both rows and loops. - _Robert A. Russell_, Mar 24 2018

MathOverflow, What is the number of achiral color patterns for a row of n colors containing k different colors?

Cf. A080337 (row sums), A140733, A140744.

Number of achiral color patterns of length even n in A293181.

(* Ach[n, k] is the number of achiral color patterns for a row or loop of n
  colors containing k different colors *)
Ach[n_, k_] := Ach[n, k] = Which[0==k, Boole[0==n], 1==k, Boole[n>0],
  OddQ[n], Sum[Binomial[(n-1)/2, i] Ach[n-1-2i, k-1], {i, 0, (n-1)/2}],
  True, Sum[Binomial[n/2-1, i] (Ach[n-2-2i, k-1]
  + 2^i Ach[n-2-2i, k-2]), {i, 0, n/2-1}]]
Table[Ach[n, k], {n, 1, 13, 2}, {k, 1, n}] // Flatten
(* Robert A. Russell, Feb 06 2018 *)
Table[MatrixPower[Table[Switch[j-i, 0,i, 1,1, 2,1, _,0],
  {i, 1, 2 n - 1}, {j, 1, 2 n - 1}], n-1][[1]], {n, 1, 10}]
  // Flatten (* Robert A. Russell, Mar 24 2018 *)
Aodd[m_, k_] := Aodd[m, k] = If[m > 1, k Aodd[m-1, k] + Aodd[m-1, k-1]
  + Aodd[m-1, k-2], Boole[m==1 && k==1]]
Table[Aodd[m,k],{m,1,10},{k,1,2m-1}] // Flatten (* Robert A. Russell, Apr 24 2018 *)

G.f.(exponential in x, ordinary in t): exp(x+t*(exp(x)-1)+(1/2)*t^2*(exp(2*x)-1)). - Ira M. Gessel, Jan 30 2018

T(m,k) = [m>1]*(k*T(m-1,k)+T(m-1,k-1)+T(m-1,k-2)) + [m==1]*[k==1] - Robert A. Russell, Apr 24 2018

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Michael Somos, May 03 2012

Row sums of triangle in A123149. - Philippe Deléham, May 04 2012
This is simply the classic sequence A038754 prefixed by a 1. - N. J. A. Sloane, Nov 23 2017
Binomial transform is A057960.
Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, May 30 2014
a(n) is also the number of achiral color patterns in a row or cycle of length n using three or fewer colors. Two color patterns are the same if we permute the colors, so ABCAB=BACBA. For a cycle, we can rotate the colors, so ABCAB=CABAB. A row is achiral if it is the same as some color permutation of its reverse. Thus the reversal of ABCAB is BACBA, which is equivalent to ABCAB when we permute A and B. A cycle is achiral if it is the same as some rotation of some color permutation of its reverse. Thus CABAB reversed is BABAC. We can permute A and B to get ABABC and then rotate to get CABAB, so CABAB is achiral. It is interesting that the number of achiral color patterns is the same for rows and cycles. - Robert A. Russell, Mar 10 2018
Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 0. - Sean A. Irvine, Jun 03 2025

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 18*x^6 + 27*x^7 + 54*x^8 + ...
From _Robert A. Russell_, Mar 10 2018: (Start)
For a(4) = 6, the achiral color patterns for rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA.  Note that for cycles AABB=ABBA and ABBC=ABCA.  The achiral patterns for cycles are AAAA, AAAB, AABB, ABAB, ABAC, and ABBC.  Note that AAAB and ABAC are not achiral rows.
For a(5) = 9, the achiral color patterns (for both rows and cycles) are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, and ABCBA. (End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Sean A. Irvine, Walks on Graphs.
Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A038754 (essentially the same sequence).
Cf. A008277, A052551, A057427, A057960.
Cf. A123149, A140735, A293181, A304973.
Also row sums of triangle in A169623.
Column 3 of A305749.
Cf. A124302 (oriented), A001998 (unoriented), A107767 (chiral), for rows, varying offsets.
Cf. A002076 (oriented), A056353 (unoriented), A320743 (chiral), for cycles.

I:=[1,1,2]; [n le 3 select I[n] else 3*Self(n-2): n in [1..40]]; // Bruno Berselli, Mar 19 2013

Join[{1}, RecurrenceTable[{a[1]==1, a[2]==2, a[n]==3 a[n-2]}, a, {n, 40}]] (* Bruno Berselli, Mar 19 2013 *)
CoefficientList[Series[(1+x-x^2)/(1-3*x^2), {x,0,50}], x] (* G. C. Greubel, Apr 14 2017 *)
Table[If[EvenQ[n], StirlingS2[(n+6)/2,3] - 4 StirlingS2[(n+4)/2,3] + 5 StirlingS2[(n+2)/2,3] - 2 StirlingS2[n/2,3], StirlingS2[(n+5)/2,3] - 3 StirlingS2[(n+3)/2,3] + 2 StirlingS2[(n+1)/2,3]], {n,0,40}] (* Robert A. Russell, Oct 21 2018 *)
Join[{1},Table[If[EvenQ[n], 2 3^((n-2)/2), 3^((n-1)/2)],{n,40}]] (* Robert A. Russell, Oct 28 2018 *)

makelist(if n=0 then 1 else (1+mod(n-1,2))*3^floor((n-1)/2), n, 0, 40); /* Bruno Berselli, Mar 19 2013 */

{a(n) = if( n<1, n==0, n--; (n%2 + 1) * 3^(n \ 2))}

my(x='x+O('x^50)); Vec((1+x-x^2)/(1-3*x^2)) \\ G. C. Greubel, Apr 14 2017

def A182522(n): return (3 -(3-2*sqrt(3))*((n+1)%2))*3^((n-3)/2) + int(n==0)/3
[A182522(n) for n in range(41)] # G. C. Greubel, Jul 17 2023

G.f.: (1 + x - x^2) / (1 - 3*x^2).
Expansion of 1 / (1 - x / (1 - x / (1 + x / (1 + x)))) in powers of x.
a(n+1) = A038754(n).
a(n) = Sum_{k=0..n} A123149(n,k). - Philippe Deléham, May 04 2012
a(n) = (3-(1+(-1)^n)*(3-2*sqrt(3))/2)*sqrt(3)^(n-3) for n>0, a(0)=1. - Bruno Berselli, Mar 19 2013
a(0) = 1, a(1) = 1, a(n) = a(n-1) + a(n-2) if n is odd, and a(n) = a(n-1) + a(n-2) + a(n-3) if n is even. - Jon Perry, Mar 19 2013
For odd n = 2m-1, a(2m-1) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A140735; for even n = 2m, a(2m) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A293181. - Robert A. Russell, Mar 10 2018
From Robert A. Russell, Oct 21 2018: (Start)
a(2m) = S2(m+3,3) - 4*S2(m+2,3) + 5*S2(m+1,3) - 2*S2(m,3).
a(2m-1) = S2(m+2,3) - 3*S2(m+1,3) + 2*S2(m,3), where S2(n,k) is the Stirling subset number A008277.
a(n) = 2*A001998(n-1) - A124302(n) = A124302(n) - 2*A107767(n-1) = A001998(n-1) - A107767(n-1).
a(n) = 2*A056353(n) - A002076(n) = A002076(n) - 2*A320743(n) = A056353(n) - A320743(n).
a(n) = A057427(n) + A052551(n-2) + A304973(n). (End)

Edited by Bruno Berselli, Mar 19 2013

Definition simplified by N. J. A. Sloane, Nov 23 2017

A304973 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 3 colors (sets).

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 10, 19, 38, 65, 130, 211, 422, 665, 1330, 2059, 4118, 6305, 12610, 19171, 38342, 58025, 116050, 175099, 350198, 527345, 1054690, 1586131, 3172262, 4766585, 9533170, 14316139, 28632278, 42981185, 85962370, 129009091, 258018182, 387158345, 774316690, 1161737179, 2323474358

Offset: 0

Robert A. Russell, May 22 2018

Two color patterns are equivalent if we permute the colors. Achiral color patterns must be equivalent if we reverse the order of the pattern.

			For a(5) = 5, the color patterns for both rows and loops are AABCC, ABACA, ABBBC, ABCAB, and ABCBA.

Index entries for linear recurrences with constant coefficients, signature (0, 5, 0, -6).

Third column of A304972.
Third column of A140735 for odd n.
Third column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 3 of A305008.

Table[If[EvenQ[n], 2 StirlingS2[n/2+1, 3] - 2 StirlingS2[n/2, 3], StirlingS2[(n + 3)/2, 3] - StirlingS2[(n + 1)/2, 3]], {n, 0, 30}]
Join[{0}, LinearRecurrence[{0, 5, 0, -6}, {0, 0, 1, 2}, 40]] (* Robert A. Russell, Oct 14 2018 *)

a(n) = [n==0 mod 2] * (2*S2(n/2+1, 3) - 2*S2(n/2, 3)) + [n==1 mod 2] * (S2((n+3)/2, 3) - S2((n+1)/2, 3)) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^3 * (1+2x) / ((1-2x^2) * (1-3x^2)).
a(n) = A304972(n,3).
a(2m-1) = A140735(m,3).
a(2m) = A293181(m,3).

A304974 Number of achiral color patterns (set partitions) for a row or loop of length n using exactly 4 colors (sets).

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 9, 16, 53, 90, 265, 440, 1221, 2002, 5369, 8736, 22933, 37130, 96105, 155080, 397541, 640002, 1629529, 2619056, 6636213, 10653370, 26899145, 43144920, 108659461, 174174002, 437826489, 701478976, 1760871893, 2820264810, 7072185385, 11324105960, 28374834981, 45425564002, 113757620249

Offset: 0

Robert A. Russell, May 22 2018

Two color patterns are equivalent if we permute the colors. Achiral color patterns must be equivalent if we reverse the order of the pattern.

			For a(6) = 9, the row color patterns are AABCDD, ABACDC, ABBCCD, ABCADC, ABCBCD, ABCCBD, ABCCDA, ABCDAB, and ABCBCD.  The loop color patterns are AAABCD, AABBCD, AABCCD, AABCDB, ABABCD, ABACAD, ABACBD, ABACDC, and ABCADC.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,7,-7,-12,12).

Fourth column of A304972.
Fourth column of A140735 for odd n.
Fourth column of A293181 for even n.
Coefficients that determine the first formula and generating function are row 4 of A305008.

I:=[0,0,0,1,2]; [0] cat [n le 5 select I[n] else Self(n-1) +7*Self(n-2) -7*Self(n-3) -12*Self(n-4) +12*Self(n-5): n in [1..40]]; // G. C. Greubel, Oct 17 2018

Table[If[EvenQ[n], StirlingS2[n/2 + 2, 4] - StirlingS2[n/2 + 1, 4] - 2 StirlingS2[n/2, 4], 2 StirlingS2[(n + 3)/2, 4] - 4 StirlingS2[(n + 1)/2, 4]], {n, 0, 40}]
Join[{0}, LinearRecurrence[{1, 7, -7, -12, 12}, {0, 0, 0, 1, 2}, 40]] (* Robert A. Russell, Oct 14 2018 *)

m=40; v=concat([0,0,0,1,2], vector(m-5)); for(n=6, m, v[n] = v[n-1] +7*v[n-2] -7*v[n-3] -12*v[n-4] +12*v[n-5]); concat([0], v) \\ G. C. Greubel, Oct 17 2018

a(n) = [n==0 mod 2] * (S2(n/2+2, 4) - S2(n/2+1, 4) - 2*S2(n/2, 4)) + [n==1 mod 2] * (2*S2((n+3)/2, 4) - 4*S2((n+1)/2, 4)) where S2(n,k) is the Stirling subset number A008277(n,k).
G.f.: x^4 * (1+x)^2 * (1-2x^2) / Product_{k=1..4} (1 - k*x^2).
a(n) = A304972(n,4).
a(2m-1) = A140735(m,4).
a(2m) = A293181(m,4).

cp's OEIS Frontend

A304972 Triangle read by rows of achiral color patterns (set partitions) for a row or loop of length n. T(n,k) is the number using exactly k colors (sets).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A002872 Number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A152176 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations and reflections.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A152175 Triangle read by rows: T(n,k) is the number of k-block partitions of an n-set up to rotations.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A056182 First differences of A003063.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A002873 The maximal number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles, and which have the same number of nonempty parts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A140735 Triangle read by rows, X^n * [1,0,0,0,...]; where X = a tridiagonal matrix with (1,2,3,...) in the main diagonal and (1,1,1,...) in the sub and subsubdiagonals.

Views

Author

Keywords

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.