A124303 -id:A124303 - cp's OEIS frontend

A007581 a(n) = (2^n+1)*(2^n+2)/6.

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

Simon Plouffe and N. J. A. Sloane

Number of palindromic structures using a maximum of four different symbols. - Marks R. Nester
Dimension of the universal embedding of the symplectic dual polar space DSp(2n,2) (conjectured by A. Brouwer, proved by P. Li). - J. Taylor (jt_cpp(AT)yahoo.com), Apr 02 2004.
Apart from initial term, same as A124303. - Valery A. Liskovets, Nov 16 2006
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
a(n) is also the number of distinct solutions (avoiding permutations) to the equation: XOR(A,B,C)=0 where A,B,C are n-bit binary numbers. - Ramasamy Chandramouli, Jan 11 2009
The rank of the fundamental group of the Z_p^n - cobordism category in dimension 1+1 for the case p=2 (see paper below). The expression for any prime p is (p^(2n-1)+p^(n+1)-p^(n-1)+p^2-p-1)/(p^2-1). - Carlos Segovia Gonzalez, Dec 05 2012
The number of isomorphic classes of regular four coverings of a graph with respect to the identity automorphism (S. Hong and J. H. Kwak). - Carlos Segovia Gonzalez, Aug 01 2013
The density of a language with four letters (N. Moreira and R. Reis). - Carlos Segovia Gonzalez, Aug 01 2013

P. Li, On the Brouwer Conjecture for Dual Polar Spaces of Symplectic Type over GF(2). Preprint.
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]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Barnes, Jeffrey M.; Benkart, Georgia; Halverson, Tom McKay centralizer algebras. Proc. Lond. Math. Soc. (3) 112, No. 2, 375-414 (2016).
Georgia Benkart and Tom Halverson, McKay Centralizer Algebras, hal-02173744 [math.CO], 2020.
A. Blokhuis and A. E. Brouwer, The universal embedding dimension of the binary symplectic dual polar space, Discr. Math., 264 (2003), 3-11.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Bruno Cisneros, Carlos Segovia, An approximation for the number of subgroups, arXiv:1805.04633 [math.GT], 2018.
B. N. Cooperstein and E. E. Shult, A note on embedding and generating dual polar spaces. Adv. Geom. 1 (2001), 37-48.
Yuanan Diao, Michael Finney, and Dawn Ray, The number of oriented rational links with a given deficiency number, arXiv:2007.02819 [math.GT], 2020. See p. 16.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 183. Book's website
S. Hong and J. H. Kwak, Regular fourfold covering with respect to the identity automorphism, J. Graph Theory, 17 (1993), 621-627.
Masashi Kosuda and Manabu Oura, Centralizer algebras of the primitive unitary reflection group of order 96, arXiv:1505.00318 [math.RT], 2015.
George S. Lueker, Improved Bounds on the Average Length of Longest Common Subsequences (Jul 22, 2005) (Fig.1).
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.
C. Segovia, Unexpected relations of cobordism categories with another [sic] subjects in mathematics, 2013.
C. Segovia, The classifying space of the 1+1 dimensional G-cobordism category, arXiv:1211.2144 [math.AT], 2012-2019.
C. Segovia, Numerical computations in cobordism categories, arXiv:1307.2850 [math.AT], 2013.
C. Segovia and M. Winklmeier, Combinatorial Computations in Cobordism Categories, arXiv preprint arXiv:1409.2067 [math.CO], 2014-2015.
C. Segovia and M. Winklmeier, On the density of certain languages with p^2 letters, Electronic Journal of Combinatorics 22(3) (2015), #P3.16.
Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Cf. A056272, A056273, A007051, A000392, A056450, A028401, A060919.

A row of the array in A278984.

List([0..30],n->(2^n+1)*(2^n+2)/6); # Muniru A Asiru, Aug 09 2018

[(2^n+1)*(2^n+2)/6: n in [0..25]]; // Vincenzo Librandi, Aug 09 2018

A007581:=n->(2^n+1)*(2^n+2)/6; seq(A007581(n), n=0..50); # Wesley Ivan Hurt, Nov 25 2013

Table[(3*2^(n-1)+2^(2n-1)+1)/3,{n,0,30}] (* or *) LinearRecurrence[ {7,-14,8},{1,2,5},31] (* Harvey P. Dale, Jul 24 2011 *)
CoefficientList[Series[(1 - 5 x + 5 x^2) / ((1 - x) (1 - 2 x) (1 - 4 x)), {x, 0, 33}], x] (* Vincenzo Librandi, Aug 09 2018 *)

a(n)=(3*2^(n-1)+2^(2*n-1)+1)/3; \\ Charles R Greathouse IV, Jun 24 2011

a(n)=if(n==0,1,(2<<(2*n--))\/3+2^n); \\ Charles R Greathouse IV, Jun 24 2011

a(n) = (3*2^(n-1) + 2^(2*n-1) + 1)/3.
a(n) = Sum_{k=1..4} Stirling2(n, k). - Winston Yang (winston(AT)cs.wisc.edu), Aug 23 2000
Binomial transform of 3^n/6 + 1/2 + 0^n/3, i.e., of A007051 with an extra leading 1. a(n) = binomial(2^n+2, 2^n-1)/2^n. - Paul Barry, Jul 19 2003
a(n) = C(2+2^n, 3)/2^n = a(n-1) + 2^(n-1) + 4^(n-3/2) = A092055(n)/A000079(n). - Henry Bottomley, Feb 19 2004
Second binomial transform of A001045(n-1) + 0^n/2. G.f.: (1-5*x+5*x^2)/((1-x)*(1-2*x)*(1-4*x)). - Paul Barry, Apr 28 2004
a(n) is the top entry of the vector M^n*[1,1,1,1,0,0,0,...], where M is an infinite bidiagonal matrix with M(r,r)=r, r >= 1, as the main diagonal, M(r,r+1)=1, and the rest zeros. ([1,1,1,...] is a column vector and transposing gives the same in terms of a leftmost column term.) - Gary W. Adamson, Jun 24 2011
a(0)=1, a(1)=2, a(2)=5, a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). - Harvey P. Dale, Jul 24 2011
E.g.f.: (exp(2*x) + 1/3*exp(4*x) + 2/3*exp(x))/2 = G(0)/2; G(k)=1 + (2^k)/(3 - 6/(2 + 4^k - 3*x*(8^k)/(3*x*(2^k) + (k+1)/G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Dec 08 2011

A278984 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.

Original entry on oeis.org

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

Offset: 1

Joerg Arndt and N. J. A. Sloane, Dec 05 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.
Let X be the random variable that assigns to each permutation of {1,2,...,b} (with uniform distribution) its number of fixed points (as in A008290).  Then T(b,n) is the n-th moment about 0 of X, i.e., the expected value of X^n. - Geoffrey Critzer, Jun 23 2020

			The array begins:
1,.1,..1,...1,...1,...1,...1,....1..; b=1, A000012
1,.2,..4,...8,..16,..32,..64,..128..; b=2, A000079
1,.2,..5,..14,..41,.122,.365,.1094..; b=3, A007051 (A278985)
1,.2,..5,..15,..51,.187,.715,.2795..; b=4, A007581
1,.2,..5,..15,..52,.202,.855,.3845..; b=5, A056272
1,.2,..5,..15,..52,.203,.876,.4111..; b=6, A056273
...
The rows tend to A000110.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"
Pengyu Liu and Jingzhou Na, Word Motifs and a Generalized Hamming Distance, Contemp. Math. (2025) Vol. 6, Issue 1, 1255-1264. See p. 1257.

Rows 1 through 16 of the array are: A000012, A000079, A007051 (or A124302), A007581 (or A124303), A056272, A056273, A099262, A099263, A164863, A164864, A203641-A203646.
The limit of the rows is A000110, the Bell numbers.
See A278985 for the words arising in row b=3.
Cf. A203647, A137855 (essentially same table).

with(combinat);
f1:=proc(L,b) local t1;i;
t1:=add(stirling2(L,i),i=1..b);
end:
Q1:=b->[seq(f1(L,b), L=1..20)]; # the rows of the array are Q1(1), Q1(2), Q1(3), ...

T[b_, n_] := Sum[StirlingS2[n, j], {j, 1, b}]; Table[T[b-n+1, n], {b, 1, 12}, {n, b, 1, -1}] // Flatten (* Jean-François Alcover, Feb 18 2017 *)

The number of words of length n over an alphabet of size b that are in standard order is Sum_{j = 1..b} Stirling2(n,j).

A056323 Number of reversible string structures with n beads using a maximum of four different colors.

Original entry on oeis.org

1, 1, 2, 4, 11, 31, 107, 379, 1451, 5611, 22187, 87979, 350891, 1400491, 5597867, 22379179, 89500331, 357952171, 1431743147, 5726775979, 22906841771, 91626580651, 366505274027, 1466017950379, 5864067607211

Offset: 0

Marks R. Nester

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure. Thus aabc, cbaa and bbac are all considered to be identical.
Number of set partitions of an unoriented row of n elements with four or fewer nonempty subsets. - Robert A. Russell, Oct 28 2018
There are nonrecursive formulas, generating functions, and computer programs for A124303 and A305750, which can be used in conjunction with the formula. - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 4-paths with n+6 vertices. (A 4-path with order n at least 6 can be constructed from a 5-clique by iteratively adding a new 4-leaf (vertex of degree 4) adjacent to an existing 4-clique containing an existing 4-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			For a(4)=11, the 7 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, ABBC, and ABCD. The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-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]

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.
Index entries for linear recurrences with constant coefficients, signature (5,0,-20,16).

Cf. A032121.
Column 4 of A320750.
Cf. A124303 (oriented), A320934 (chiral), A305750 (achiral).
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

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 *)
k=4; Table[Sum[StirlingS2[n,j]+Ach[n,j],{j,0,k}]/2,{n,0,40}] (* Robert A. Russell, Oct 28 2018 *)
LinearRecurrence[{5, 0, -20, 16}, {1, 1, 2, 4, 11}, 40] (* Robert A. Russell, Oct 28 2018 *)

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
For n > 0, a(n) = (16 + (-2)^n + 15*2^n + 4^n)/48. - Colin Barker, Nov 24 2012
G.f.: (1 - 4x - 3x^2 + 14x^3 - 5x^4) / ((1-x)*(1-4x)*(1-4x^2)). - Colin Barker, Nov 24 2012 [Adapted to offset 0 by Robert A. Russell, Nov 09 2018]
From Robert A. Russell, Oct 28 2018: (Start)
a(n) = (A124303(n) + A305750(n)) / 2.
a(n) = A124303(n) - A320934(n) = A320934(n) + A305750(n).
a(n) = Sum_{j=0..k} (S2(n,j) + Ach(n,j)) / 2, where k=4 is the maximum number of colors, 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)).
a(n) = A000007(n) + A057427(n) + A056326(n) + A056327(n) + A056328(n). (End)

a(0)=1 prepended by Robert A. Russell, Nov 09 2018

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

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678569, 4213530, 27641927, 190829797, 1381367941, 10448276360, 82285618467, 672294831619, 5676711562593, 49344452550230, 439841775811967, 4005444732928641, 37136385907400125, 349459367068932740

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"
Dmytro S. Inosov and Emil Vlasák, Cryptarithmically unique terms in integer sequences, arXiv:2410.21427 [math.NT], 2024. See pp. 3-4, 16-18.
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.
Pierpaolo Natalini, Paolo Emilio Ricci, New Bell-Sheffer Polynomial Sets, Axioms 2018, 7(4), 71.
Eric Weisstein's World of Mathematics, Set Partition
Wikipedia, Partition of a set
Index entries for linear recurrences with constant coefficients, signature (46,-906,9996,-67809,291774,-790964,1290824,-1136160,403200).

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

A row of the array in A278984.

# First program:
a:= n-> ceil(2119/11520*2^n +103/1680*3^n +53/3456*4^n +11/3600*5^n +6^n/1920 +7^n/15120 +8^n/80640 +10^n/3628800): seq(a(n), n=0..25);
# second program:
a:= n-> add(Stirling2(n, k), k=0..10): seq(a(n), n=0..25);

Table[Sum[StirlingS2[n,k],{k,0,10}],{n,0,30}] (* Harvey P. Dale, Nov 22 2023 *)

a(n) = Sum_{k=0..10} Stirling2 (n,k).
a(n) = ceiling(2119/11520*2^n +103/1680*3^n +53/3456*4^n +11/3600*5^n +6^n/1920 +7^n/15120 +8^n/80640 +10^n/3628800).
G.f.: (148329*x^9 -613453*x^8 +855652*x^7 -596229*x^6 +240065*x^5 -59410*x^4 +9177*x^3 -862*x^2 +45*x-1) / ((10*x-1) *(8*x-1) *(7*x-1) *(6*x-1) *(5*x-1) *(4*x-1) *(3*x-1) *(2*x-1) *(x-1)).
a(n) <= A000110(n) with equality only for n <= 10.

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.

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Original entry on oeis.org

1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, 348889, 1768483, 9220655, 49286863, 269346822, 1501400222, 8519796094, 49133373040, 287544553912, 1705548000296, 10241669069576, 62201517142632, 381749896129920, 2365758616886432, 14793705539872672

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

Also the number of 2-regular 3-noncrossing partitions. There is a bijection from 2-regular 3-noncrossing partitions of n to enhanced partition of n-1. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007
It appears that this is the number of sequences of length n, starting with a(1) = 1 and 1 <= a(2) <= 2, with 1 <= a(n) <= max(a(n-1),a(n-2)) + 1 for n > 2. - Franklin T. Adams-Watters, May 27 2008
From Eric M. Schmidt, Jul 17 2017: (Start)
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) <= e(k) and e(i) >= e(k). [Martinez and Savage, 2.16]
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) >= e(k). [Martinez and Savage, 2.16]
(End)
The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - Eric M. Schmidt, Nov 25 2017

			There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.
M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Sherry H. F. Yan, Ascent sequences and 3-nonnesting set partitions, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.

Cf. A124303, A073525, A007317.

Cf. A000110, A000108.

a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n-1) *a(n-2)+ (7*(n-2)^2 +53*(n-2) +88) *a(n-1))/(n+6)/(n+5) fi end: seq(a(n), n=0..20);  # Alois P. Heinz, Sep 05 2008

a[n_] := a[n] = If[n <= 1, 1, If[n==2, 2, (8*(n+1)*(n-1)*a[n-2]+(7*(n-2)^2+53*(n-2)+88)*a[n-1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

D-finite with recurrence: 8*(n+3)*(n+1)*a(n)+(7*n^2+53*n+88)*a(n+1)-(n+8)*(n+7)*a(n+2)=0. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 26 2007
G.f.: -(6*x^4-15*x^3-7*x^2-11*x-1)/(6*x^5)+(224*x^3-60*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3) / (30*x^5*(2*x-1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(1-2*x)^3)/(5*x^3*(2*x-1)^2). - Mark van Hoeij, Oct 24 2011
a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - Vaclav Kotesovec, Aug 16 2013
G.f.: (-6*x^4+15*x^3+7*x^2+11*x+1)/(6*x^5)-(1-8*x)^(4/3)*(1+x)^(2/3)*hypergeom([-2/3, 7/3],[2],-27*x/((1+x)*(-1+8*x)^2))/(6*x^5). - Mark van Hoeij, Jul 26 2021

Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008

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

A305750 Number of achiral color patterns (set partitions) in a row or cycle of length n with 4 or fewer colors (subsets).

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 27, 43, 107, 171, 427, 683, 1707, 2731, 6827, 10923, 27307, 43691, 109227, 174763, 436907, 699051, 1747627, 2796203, 6990507, 11184811, 27962027, 44739243, 111848107, 178956971, 447392427, 715827883, 1789569707, 2863311531, 7158278827

Offset: 0

Robert A. Russell, Jun 09 2018

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABCD are equivalent, as are AABCD and BBCDA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a cycle are equivalent, so for cycles AABBCD = BBCDAA = CDAABB.

			For a(4) = 7, the achiral row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD. The cycle patterns are AAAA, AAAB, AABB, ABAB, AABC, ABAC, and ABCD.

Muniru A Asiru, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Fourth column of A305749.
Cf. A124303 (oriented), A056323 (unoriented), A320934 (chiral), for rows.
Cf. A056292 (oriented), A056354 (unoriented), A320744 (chiral), for cycles.

a:=[1,2,3];; for n in [4..40] do a[n]:=a[n-1]+4*a[n-2]-4*a[n-3]; od; Concatenation([1],a); # Muniru A Asiru, Oct 28 2018

seq(coeff(series((1-3*x^2+x^3)/((1-x)*(1-4*x^2)),x,n+1), x, n), n = 0 .. 40); # Muniru A Asiru, Oct 28 2018

Table[If[EvenQ[n], StirlingS2[(n+8)/2, 4] - 8 StirlingS2[(n+6)/2, 4] + 22 StirlingS2[(n+4)/2, 4] - 23 StirlingS2[(n+2)/2, 4] + 6 StirlingS2[n/2, 4], StirlingS2[(n+7)/2, 4] - 7 StirlingS2[(n+5)/2, 4] + 16 StirlingS2[(n+3)/2, 4] - 12 StirlingS2[(n+1)/2, 4]], {n, 0, 40}]
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 *)
k=4; Table[Sum[Ach[n, j], {j, 0, k}], {n, 0, 40}]
(* or *)
CoefficientList[Series[(1-3x^2+x^3)/((1-x)(1-4x^2)), {x,0,40}], x]
(* or *)
Join[{1},LinearRecurrence[{1,4,-4},{1,2,3},40]]
(* or *)
Join[{1},Table[If[EvenQ[n], (4+5 4^(n/2))/12, (2+4^((n+1)/2))/6], {n,40}]]

a(n) = Sum_{j=0..4} Ach(n,j), where Ach(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [0<=n<2 & n==k].
G.f.: (1 - 3x^2 + x^3) / ((1-x) * (1-4x^2)).
a(2m) = S2(m+4,4) - 8*S2(m+3,4) + 22*S2(m+2,4) - 23*S2(m+1,4) + 6*S2(m,4);
a(2m-1) = S2(m+3,4) - 7*S2(m+2,4) + 16*S2(m+1,4) - 12*S2(m,4), where S2(n,k) is the Stirling subset number A008277.
For m>0, a(2m) = (4 + 5*4^m) / 12.
a(2m-1) = (2 + 4^m) / 6.
a(n) = 2*A056323(n) - A124303(n) = A124303(n) - 2*A320934(n) = A056323(n) - A320934(n).
a(n) = 2*A056354(n) - A056292(n) = A056292(n) - 2*A320744(n) = A056354(n) - A320744(n).
a(n) = A057427(n) + A052551(n-2) + A304973(n) + A304974(n).
a(n) = a(n-1) + 4*a(n-2) - 4*a(n-3). - Muniru A Asiru, Oct 28 2018

A056478 Number of primitive (aperiodic) palindromic structures using a maximum of four different symbols.

Original entry on oeis.org

1, 1, 0, 1, 1, 4, 3, 14, 13, 49, 46, 186, 181, 714, 700, 2789, 2780, 11050, 10997, 43946, 43895, 175259, 175088, 700074, 699875, 2798246, 2797536, 11188856, 11188191, 44747434, 44744591, 178973354, 178970560, 715860463, 715849600, 2863377048, 2863365834

Offset: 0

Marks R. Nester

nonn

Permuting the symbols will not change the structure.

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 = 0..500

Cf. A007581, A124303, A056460, A284826.

a(n) = Sum_{d|n} mu(d)*A124303(ceiling(n/(2*d))) for n > 0.

a(n) = Sum_{k=1..4} A284826(n, k) for n > 0. - Andrew Howroyd, Oct 02 2019

a(0)=1 prepended and terms a(32) and beyond from Andrew Howroyd, Oct 02 2019

A320934 Number of chiral pairs of color patterns (set partitions) for a row of length n using 4 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 1, 4, 20, 80, 336, 1344, 5440, 21760, 87296, 349184, 1397760, 5591040, 22368256, 89473024, 357908480, 1431633920, 5726601216, 22906404864, 91625881600, 366503526400, 1466015154176, 5864060616704, 23456246661120, 93824986644480, 375299963355136, 1501199853420544, 6004799480791040

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.
There are nonrecursive formulas, generating functions, and computer programs for A124303 and A305750, which can be used in conjunction with the first formula.

			For a(4)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB.

Index entries for linear recurrences with constant coefficients, signature (4,4,-16).

Column 4 of A320751.

Cf. A124303 (oriented), A056323 (unoriented), A305750 (achiral).

Table[(4^n - 4^Floor[n/2+1])/48, {n, 40}] (* or *)
LinearRecurrence[{4, 4, -16}, {0, 0, 1}, 40] (* or *)
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 *)
k=4; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,40}]
CoefficientList[Series[x^2/((-1 + 4 x) (-1 + 4 x^2)), {x, 0, 50}], x] (* Stefano Spezia, Oct 29 2018 *)

a(n) = (A124303(n) - A305750(n))/2.
a(n) = A124303(n) - A056323(n).
a(n) = A056323(n) - A305750(n).
a(n) = A122746(n-2) + A320526(n) + A320527(n).
a(n) = Sum_{j=1..k} (S2(n,j) - Ach(n,j)) / 2, where k=4 is the maximum number of colors, 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)).
a(2*m) = (16^m - 4*4^m)/48.
a(2*m-1) = (16^m - 4*4^m)/192.
a(n) = (4^n - 4^floor(n/2+1))/48.
G.f.: x^2/((-1 + 4*x)*(-1 + 4*x^2)). - Stefano Spezia, Oct 29 2018
a(n) = 2^n*(2^n - (-1)^n - 3)/48. - Bruno Berselli, Oct 31 2018

cp's OEIS Frontend

A007581 a(n) = (2^n+1)*(2^n+2)/6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Formula

A278984 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A056323 Number of reversible string structures with n beads using a maximum of four different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author