cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 33 results. Next

A100510 Bisection of A005425.

Original entry on oeis.org

2, 14, 142, 1850, 29186, 538078, 11317646, 266906858, 6965034370, 199037675054, 6176578272782, 206703355298074, 7416522514174082, 283886725100730110, 11542917975992870926, 496687811705758019018, 22543169666612417313026
Offset: 0

Views

Author

N. J. A. Sloane, Nov 24 2004

Keywords

Crossrefs

Programs

  • Magma
    [n le 2 select 2*(6*n-5) else (4*n-1)*Self(n-1) - 2*(n-2)*(2*n-3)*Self(n-2): n in [1..40]]; // G. C. Greubel, Apr 01 2023
    
  • Mathematica
    Table[(-I/Sqrt[2])^(2*n+1)*HermiteH[2*n+1, I*Sqrt[2]], {n,0,40}] (* G. C. Greubel, Apr 01 2023 *)
  • SageMath
    [(-i/sqrt(2))^(2*n+1)*hermite(2*n+1, i*sqrt(2)) for n in range(41)] # G. C. Greubel, Apr 01 2023

Formula

a(n) = (-i/sqrt(2))^(2*n+1)*hermite(2*n+1, i*sqrt(2)). - G. C. Greubel, Apr 01 2023

Extensions

More terms from Hugo Pfoertner, Nov 25 2004

A000085 Number of self-inverse permutations on n letters, also known as involutions; number of standard Young tableaux with n cells.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, 618884638912, 3257843882624, 17492190577600, 95680443760576, 532985208200576, 3020676745975552
Offset: 0

Views

Author

Keywords

Comments

a(n) is also the number of n X n symmetric permutation matrices.
a(n) is also the number of matchings (Hosoya index) in the complete graph K(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
a(n) is also the number of independent vertex sets and vertex covers in the n-triangular graph. - Eric W. Weisstein, May 22 2017
Equivalently, this is the number of graphs on n labeled nodes with degrees at most 1. - Don Knuth, Mar 31 2008
a(n) is also the sum of the degrees of the irreducible representations of the symmetric group S_n. - Avi Peretz (njk(AT)netvision.net.il), Apr 01 2001
a(n) is the number of partitions of a set of n distinguishable elements into sets of size 1 and 2. - Karol A. Penson, Apr 22 2003
Number of tableaux on the edges of the star graph of order n, S_n (sometimes T_n). - Roberto E. Martinez II, Jan 09 2002
The Hankel transform of this sequence is A000178 (superfactorials). Sequence is also binomial transform of the sequence 1, 0, 1, 0, 3, 0, 15, 0, 105, 0, 945, ... (A001147 with interpolated zeros). - Philippe Deléham, Jun 10 2005
Row sums of the exponential Riordan array (e^(x^2/2),x). - Paul Barry, Jan 12 2006
a(n) is the number of nonnegative lattice paths of upsteps U = (1,1) and downsteps D = (1,-1) that start at the origin and end on the vertical line x = n in which each downstep (if any) is marked with an integer between 1 and the height of its initial vertex above the x-axis. For example, with the required integer immediately preceding each downstep, a(3) = 4 counts UUU, UU1D, UU2D, U1DU. - David Callan, Mar 07 2006
Equals row sums of triangle A152736 starting with offset 1. - Gary W. Adamson, Dec 12 2008
Proof of the recurrence relation a(n) = a(n-1) + (n-1)*a(n-2): number of involutions of [n] containing n as a fixed point is a(n-1); number of involutions of [n] containing n in some cycle (j, n), where 1 <= j <= n-1, is (n-1) times the number of involutions of [n] containing the cycle (n-1 n) = (n-1)*a(n-2). - Emeric Deutsch, Jun 08 2009
Number of ballot sequences (or lattice permutations) of length n. A ballot sequence B is a string such that, for all prefixes P of B, h(i) >= h(j) for i < j, where h(x) is the number of times x appears in P. For example, the ballot sequences of length 4 are 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1231, and 1234. The string 1221 does not appear in the list because in the 3-prefix 122 there are two 2's but only one 1. (Cf. p. 176 of Bruce E. Sagan: "The Symmetric Group"). - Joerg Arndt, Jun 28 2009
Number of standard Young tableaux of size n; the ballot sequences are obtained as a length-n vector v where v_k is the (number of the) row in which the number r occurs in the tableaux. - Joerg Arndt, Jul 29 2012
Number of factorial numbers of length n-1 with no adjacent nonzero digits. For example the 10 such numbers (in rising factorial radix) of length 3 are 000, 001, 002, 003, 010, 020, 100, 101, 102, and 103. - Joerg Arndt, Nov 11 2012
Also called restricted Stirling numbers of the second kind (see Mezo). - N. J. A. Sloane, Nov 27 2013
a(n) is the number of permutations of [n] that avoid the consecutive patterns 123 and 132. Proof. Write a self-inverse permutation in standard cycle form: smallest entry in each cycle in first position, first entries decreasing. For example, (6,7)(3,4)(2)(1,5) is in standard cycle form. Then erase parentheses. This is a bijection to the permutations that avoid consecutive 123 and 132 patterns. - David Callan, Aug 27 2014
Getu (1991) says these numbers are also known as "telephone numbers". - N. J. A. Sloane, Nov 23 2015
a(n) is the number of elements x in the symmetric group S_n such that x^2 = e where e is the identity. - Jianing Song, Aug 22 2018 [Edited on Jul 24 2025]
a(n) is the number of congruence orbits of upper-triangular n X n matrices on skew-symmetric matrices, or the number of Borel orbits in largest sect of the type DIII symmetric space SO_{2n}(C)/GL_n(C). Involutions can also be thought of as fixed-point-free partial involutions. See [Bingham and Ugurlu] link. - Aram Bingham, Feb 08 2020
From Thomas Anton, Apr 20 2020: (Start)
Apparently a(n) = b*c where b is odd iff a(n+b) (when a(n) is defined) is divisible by b.
Apparently a(n) = 2^(f(n mod 4)+floor(n/4))*q where f:{0,1,2,3}->{0,1,2} is given by f(0),f(1)=0, f(2)=1 and f(3)=2 and q is odd. (End)
From Iosif Pinelis, Mar 12 2021: (Start)
a(n) is the n-th initial moment of the normal distribution with mean 1 and variance 1. This follows because the moment generating function of that distribution is the e.g.f. of the sequence of the a(n)'s.
The recurrence a(n) = a(n-1) + (n-1)*a(n-2) also follows, by writing E(Z+1)^n=EZ(Z+1)^(n-1)+E(Z+1)^(n-1), where Z is a standard normal random variable, and then taking the first of the latter two integrals by parts. (End)

Examples

			Sequence starts 1, 1, 2, 4, 10, ... because possibilities are {}, {A}, {AB, BA}, {ABC, ACB, BAC, CBA}, {ABCD, ABDC, ACBD, ADCB, BACD, BADC, CBAD, CDAB, DBCA, DCBA}. - _Henry Bottomley_, Jan 16 2001
G.f. = 1 + x + 2*x^2 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 764*x^9 + ...
From _Gus Wiseman_, Jan 08 2021: (Start)
The a(4) = 10 standard Young tableaux:
  1 2 3 4
.
  1 2   1 3   1 2 3   1 2 4   1 3 4
  3 4   2 4   4       3       2
.
  1 2   1 3   1 4
  3     2     2
  4     4     3
.
  1
  2
  3
  4
The a(0) = 1 through a(4) = 10 set partitions into singletons or pairs:
  {}  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{3,4}}
             {{1},{2}}  {{1,2},{3}}    {{1,3},{2,4}}
                        {{1,3},{2}}    {{1,4},{2,3}}
                        {{1},{2},{3}}  {{1},{2},{3,4}}
                                       {{1},{2,3},{4}}
                                       {{1,2},{3},{4}}
                                       {{1},{2,4},{3}}
                                       {{1,3},{2},{4}}
                                       {{1,4},{2},{3}}
                                       {{1},{2},{3},{4}}
(End)
		

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 32, 911.
  • S. Chowla, The asymptotic behavior of solutions of difference equations, in Proceedings of the International Congress of Mathematicians (Cambridge, MA, 1950), Vol. I, 377, Amer. Math. Soc., Providence, RI, 1952.
  • W. Fulton, Young Tableaux, Cambridge, 1997.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 5.1.4, p. 65.
  • L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181.
  • T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, p. 6.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 86.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.10.

Crossrefs

See also A005425 for another version of the switchboard problem.
Equals 2 * A001475(n-1) for n>1.
First column of array A099020.
A069943(n+1)/A069944(n+1) = a(n)/A000142(n) in lowest terms.
Cf. A152736, A128229. - Gary W. Adamson, Dec 12 2008
Diagonal of A182172. - Alois P. Heinz, May 30 2012
Row sums of: A047884, A049403, A096713 (absolute value), A100861, A104556 (absolute value), A111924, A117506 (M_4 numbers), A122848, A238123.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.

Programs

  • Haskell
    a000085 n = a000085_list !! n
      a000085_list = 1 : 1 : zipWith (+)
        (zipWith (*) [1..] a000085_list) (tail a000085_list) -- Reinhard Zumkeller, May 16 2013
    
  • Maple
    A000085 := proc(n) option remember; if n=0 then 1 elif n=1 then 1 else procname(n-1)+(n-1)*procname(n-2); fi; end;
    with(combstruct):ZL3:=[S,{S=Set(Cycle(Z,card<3))}, labeled]:seq(count(ZL3,size=n),n=0..25); # Zerinvary Lajos, Sep 24 2007
    with (combstruct):a:=proc(m) [ZL, {ZL=Set(Cycle(Z, m>=card))}, labeled]; end: A:=a(2):seq(count(A, size=n), n=0..25); # Zerinvary Lajos, Jun 11 2008
  • Mathematica
    <Roger L. Bagula, Oct 06 2006 *)
    With[{nn=30},CoefficientList[Series[Exp[x+x^2/2],{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, May 28 2013 *)
    a[ n_] := Sum[(2 k - 1)!! Binomial[ n, 2 k], {k, 0, n/2}]; (* Michael Somos, Jun 01 2013 *)
    a[ n_] := If[ n < 0, 0, HypergeometricU[ -n/2, 1/2, -1/2] / (-1/2)^(n/2)]; (* Michael Somos, Jun 01 2013 *)
    a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ x + x^2 / 2], {x, 0, n}]]; (* Michael Somos, Jun 01 2013 *)
    Table[(I/Sqrt[2])^n HermiteH[n, -I/Sqrt[2]], {n, 0, 100}] (* Emanuele Munarini, Mar 02 2016 *)
    a[n_] := Sum[StirlingS1[n, k]*2^k*BellB[k, 1/2], {k, 0, n}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 18 2017, after Emanuele Munarini *)
    RecurrenceTable[{a[n] == a[n-1] + (n-1)*a[n-2], a[0] == 1, a[1] == 1}, a, {n, 0, 20}] (* Joan Ludevid, Jun 17 2022 *)
    sds[{}]:={{}};sds[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sds[Complement[set,s]]]/@Cases[Subsets[set,{1,2}],{i,_}]; Table[Length[sds[Range[n]]],{n,0,10}] (* Gus Wiseman, Jan 11 2021 *)
  • Maxima
    B(n,x):=sum(stirling2(n,k)*x^k,k,0,n);
      a(n):=sum(stirling1(n,k)*2^k*B(k,1/2),k,0,n);
      makelist(a(n),n,0,40); /* Emanuele Munarini, May 16 2014 */
    
  • Maxima
    makelist((%i/sqrt(2))^n*hermite(n,-%i/sqrt(2)),n,0,12); /* Emanuele Munarini, Mar 02 2016 */
    
  • PARI
    {a(n) = if( n<0, 0, n! * polcoeff( exp( x + x^2 / 2 + x * O(x^n)), n))}; /* Michael Somos, Nov 15 2002 */
    
  • PARI
    N=66; x='x+O('x^N); egf=exp(x+x^2/2); Vec(serlaplace(egf)) \\ Joerg Arndt, Mar 07 2013
    
  • Python
    from math import factorial
    def A000085(n): return sum(factorial(n)//(factorial(n-(k<<1))*factorial(k)*(1<>1)+1)) # Chai Wah Wu, Aug 31 2023
  • Sage
    A000085 = lambda n: hypergeometric([-n/2,(1-n)/2], [], 2)
    [simplify(A000085(n)) for n in range(28)] # Peter Luschny, Aug 21 2014
    
  • Sage
    def a85(n): return sum(factorial(n) / (factorial(n-2*k) * 2**k * factorial(k)) for k in range(1+n//2))
    for n in range(100): print(n, a85(n)) # Manfred Scheucher, Jan 07 2018
    

Formula

D-finite with recurrence a(0) = a(1) = 1, a(n) = a(n-1) + (n-1)*a(n-2) for n>1.
E.g.f.: exp(x+x^2/2).
a(n) = a(n-1) + A013989(n-2) = A013989(n)/(n+1) = 1+A001189(n).
a(n) = Sum_{k=0..floor(n/2)} n!/((n-2*k)!*2^k*k!).
a(m+n) = Sum_{k>=0} k!*binomial(m, k)*binomial(n, k)*a(m-k)*a(n-k). - Philippe Deléham, Mar 05 2004
For n>1, a(n) = 2*(A000900(n) + A000902(floor(n/2))). - Max Alekseyev, Oct 31 2015
The e.g.f. y(x) satisfies y^2 = y''y' - (y')^2.
a(n) ~ c*(n/e)^(n/2)exp(n^(1/2)) where c=2^(-1/2)exp(-1/4). [Chowla]
a(n) = HermiteH(n, 1/(sqrt(2)*i))/(-sqrt(2)*i)^n, where HermiteH are the Hermite polynomials. - Karol A. Penson, May 16 2002
a(n) = Sum_{k=0..n} A001498((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2. - Paul Barry, Jan 12 2006
For asymptotics see the Robinson paper.
a(n) = Sum_{m=0..n} A099174(n,m). - Roger L. Bagula, Oct 06 2006
O.g.f.: A(x) = 1/(1-x-1*x^2/(1-x-2*x^2/(1-x-3*x^2/(1-... -x-n*x^2/(1- ...))))) (continued fraction). - Paul D. Hanna, Jan 17 2006
From Gary W. Adamson, Dec 29 2008: (Start)
a(n) = (n-1)*a(n-2) + a(n-1); e.g., a(7) = 232 = 6*26 + 76.
Starting with offset 1 = eigensequence of triangle A128229. (End)
a(n) = (1/sqrt(2*Pi))*Integral_{x=-oo..oo} exp(-x^2/2)*(x+1)^n. - Groux Roland, Mar 14 2011
Row sums of |A096713|. a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator sqrt(1+2*x)*d/dx. Cf. A047974 and A080599. - Peter Bala, Dec 07 2011
From Sergei N. Gladkovskii, Dec 03 2011 - Oct 28 2013: (Start)
Continued fractions:
E.g.f.: 1+x*(2+x)/(2*G(0)-x*(2+x)) where G(k)=1+x*(x+2)/(2+2*(k+1)/G(k+1)).
G.f.: 1/(U(0) - x) where U(k) = 1 + x*(k+1) - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 + x*k - x/(1 - x*(k+1)/Q(k+1)).
G.f.: -1/(x*Q(0)) where Q(k) = 1 - 1/x - (k+1)/Q(k+1).
G.f.: T(0)/(1-x) where T(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x)^2/T(k+1)). (End)
a(n) ~ (1/sqrt(2)) * exp(sqrt(n)-n/2-1/4) * n^(n/2) * (1 + 7/(24*sqrt(n))). - Vaclav Kotesovec, Mar 07 2014
a(n) = Sum_{k=0..n} s(n,k)*(-1)^(n-k)*2^k*B(k,1/2), where the s(n,k) are (signless) Stirling numbers of the first kind, and the B(n,x) = Sum_{k=0..n} S(n,k)*x^k are the Stirling polynomials, where the S(n,k) are the Stirling numbers of the second kind. - Emanuele Munarini, May 16 2014
a(n) = hyper2F0([-n/2,(1-n)/2],[],2). - Peter Luschny, Aug 21 2014
0 = a(n)*(+a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(-a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Aug 22 2014
From Peter Bala, Oct 06 2021: (Start)
a(n+k) == a(n) (mod k) for all n >= 0 and all positive odd integers k.
Hence for each odd k, the sequence obtained by taking a(n) modulo k is a periodic sequence and the exact period divides k. For example, taking a(n) modulo 7 gives the purely periodic sequence [1, 1, 2, 4, 3, 5, 6, 1, 1, 2, 4, 3, 5, 6, 1, 1, 2, 4, 3, 5, 6, ...] of period 7. For similar results see A047974 and A115329. (End)

A000178 Superfactorials: product of first n factorials.

Original entry on oeis.org

1, 1, 2, 12, 288, 34560, 24883200, 125411328000, 5056584744960000, 1834933472251084800000, 6658606584104736522240000000, 265790267296391946810949632000000000, 127313963299399416749559771247411200000000000, 792786697595796795607377086400871488552960000000000000
Offset: 0

Views

Author

Keywords

Comments

a(n) is also the Vandermonde determinant of the numbers 1,2,...,(n+1), i.e., the determinant of the (n+1) X (n+1) matrix A with A[i,j] = i^j, 1 <= i <= n+1, 0 <= j <= n. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001
a(n) = (1/n!) * D(n) where D(n) is the determinant of order n in which the (i,j)-th element is i^j. - Amarnath Murthy, Jan 02 2002
Determinant of S_n where S_n is the n X n matrix S_n(i,j) = Sum_{d|i} d^j. - Benoit Cloitre, May 19 2002
Appears to be det(M_n) where M_n is the n X n matrix with m(i,j) = J_j(i) where J_k(n) denote the Jordan function of row k, column n (cf. A059380(m)). - Benoit Cloitre, May 19 2002
a(2n+1) = 1, 12, 34560, 125411328000, ... is the Hankel transform of A000182 (tangent numbers) = 1, 2, 16, 272, 7936, ...; example: det([1, 2, 16, 272; 2, 16, 272, 7936; 16, 272, 7936, 353792; 272, 7936, 353792, 22368256]) = 125411328000. - Philippe Deléham, Mar 07 2004
Determinant of the (n+1) X (n+1) matrix whose i-th row consists of terms 1 to n+1 of the Lucas sequence U(i,Q), for any Q. When Q=0, the Vandermonde matrix is obtained. - T. D. Noe, Aug 21 2004
Determinant of the (n+1) X (n+1) matrix A whose elements are A(i,j) = B(i+j) for 0 <= i,j <= n, where B(k) is the k-th Bell number, A000110(k) [I. Mezo, JIS 14 (2011) # 11.1.1]. - T. D. Noe, Dec 04 2004
The Hankel transform of the sequence A090365 is A000178(n+1); example: det([1,1,3; 1,3,11; 3,11,47]) = 12. - Philippe Deléham, Mar 02 2005
Theorem 1.3, page 2, of Polynomial points, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.6, provides an example of an Abelian quotient group of order (n-1) superfactorial, for each positive integer n. The quotient is obtained from sequences of polynomial values. - E. F. Cornelius, Jr. (efcornelius(AT)comcast.net), Apr 09 2007
Starting with offset 1 this is a 'Matryoshka doll' sequence with alpha=1, the multiplicative counterpart to the additive A000292. seq(mul(mul(i,i=alpha..k), k=alpha..n),n=alpha..12). - Peter Luschny, Jul 14 2009
For n>0, a(n) is also the determinant of S_n where S_n is the n X n matrix, indexed from 1, S_n(i,j)=sigma_i(j), where sigma_k(n) is the generalized divisor sigma function: A000203 is sigma_1(n). - Enrique Pérez Herrero, Jun 21 2010
a(n) is the multiplicative Wiener index of the (n+1)-vertex path. Example: a(4)=288 because in the path on 5 vertices there are 3 distances equal to 2, 2 distances equal to 3, and 1 distance equal to 4 (2*2*2*3*3*4=288). See p. 115 of the Gutman et al. reference. - Emeric Deutsch, Sep 21 2011
a(n-1) = Product_{j=1..n-1} j! = V(n) = Product_{1 <= i < j <= n} (j - i) (a Vandermondian V(n), see the Ahmed Fares May 06 2001 comment above), n >= 1, is in fact the determinant of any n X n matrix M(n) with entries M(n;i,j) = p(j-1,x = i), 1 <= i, j <= n, where p(m,x), m >= 0, are monic polynomials of exact degree m with p(0,x) = 1. This is a special x[i] = i choice in a general theorem given in Vein-Dale, p. 59 (written for the transposed matrix M(n;j,x_i) = p(i-1,x_j) = P_i(x_j) in Vein-Dale, and there a_{k,k} = 1, for k=1..n). See the Aug 26 2013 comment under A049310, where p(n,x) = S(n,x) (Chebyshev S). - Wolfdieter Lang, Aug 27 2013
a(n) is the number of monotonic magmas on n elements labeled 1..n with a symmetric multiplication table. I.e., Product(i,j) >= max(i,j); Product(i,j) = Product(j,i). - Chad Brewbaker, Nov 03 2013
The product of the pairwise differences of n+1 integers is a multiple of a(n) [and this does not hold for any k > a(n)]. - Charles R Greathouse IV, Aug 15 2014
a(n) is the determinant of the (n+1) X (n+1) matrix M with M(i,j) = (n+j-1)!/(n+j-i)!, 1 <= i <= n+1, 1 <= j <= n+1. - Stoyan Apostolov, Aug 26 2014
All terms are in A064807 and all terms after a(2) are in A005101. - Ivan N. Ianakiev, Sep 02 2016
Empirical: a(n-1) is the determinant of order n in which the (i,j)-th entry is the (j-1)-th derivative of x^(x+i-1) evaluated at x=1. - John M. Campbell, Dec 13 2016
Empirical: If f(x) is a smooth, real-valued function on an open neighborhood of 0 such that f(0)=1, then a(n) is the determinant of order n+1 in which the (i,j)-th entry is the (j-1)-th derivative of f(x)/((1-x)^(i-1)) evaluated at x=0. - John M. Campbell, Dec 27 2016
Also the automorphism group order of the n-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017
Is the zigzag Hankel transform of A000182. That is, a(2*n+1) is the Hankel transform of A000182 and a(2*n+2) is the Hankel transform of A000182(n+1). - Michael Somos, Mar 11 2020
Except for n = 0, 1, superfactorial a(n) is never a square (proof in link Mabry and Cormick, FFF 4 p. 349); however, when k belongs to A349079 (see for further information), there exists m, 1 <= m <= k such that a(k) / m! is a square. - Bernard Schott, Nov 29 2021

Examples

			a(3) = (1/6)* | 1 1 1 | 2 4 8 | 3 9 27 |
a(7) = n! * a(n-1) = 7! * 24883200 = 125411328000.
a(12) = 1! * 2! * 3! * 4! * 5! * 6! * 7! * 8! * 9! * 10! * 11! * 12!
= 1^12 * 2^11 * 3^10 * 4^9 * 5^8 * 6^7 * 7^6 * 8^5 * 9^4 * 10^3 * 11^2 * 12^1
= 2^56 * 3^26 * 5^11 * 7^6 * 11^2.
G.f. = 1 + x + 2*x^2 + 12*x^3 + 288*x^4 + 34560*x^5 + 24883200*x^6 + ...
		

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 545.
  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 135-145.
  • A. Fletcher, J. C. P. Miller, L. Rosenhead and L. J. Comrie, An Index of Mathematical Tables. Vols. 1 and 2, 2nd ed., Blackwell, Oxford and Addison-Wesley, Reading, MA, 1962, Vol. 1, p. 50.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 231.
  • H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 53.
  • 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).
  • R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer, 1999.

Crossrefs

Programs

  • Magma
    [&*[Factorial(k): k in [0..n]]: n in [0..20]]; // Bruno Berselli, Mar 11 2015
    
  • Maple
    A000178 := proc(n)
        mul(i!,i=1..n) ;
    end proc:
    seq(A000178(n),n=0..10) ; # R. J. Mathar, Oct 30 2015
  • Mathematica
    a[0] := 1; a[1] := 1; a[n_] := n!*a[n - 1]; Table[a[n], {n, 1, 12}] (* Stefan Steinerberger, Mar 10 2006 *)
    Table[BarnesG[n], {n, 2, 14}] (* Zerinvary Lajos, Jul 16 2009 *)
    FoldList[Times,1,Range[20]!] (* Harvey P. Dale, Mar 25 2011 *)
    RecurrenceTable[{a[n] == n! a[n - 1], a[0] == 1}, a, {n, 0, 12}] (* Ray Chandler, Jul 30 2015 *)
    BarnesG[Range[2, 20]] (* Eric W. Weisstein, Jul 14 2017 *)
  • Maxima
    A000178(n):=prod(k!,k,0,n)$ makelist(A000178(n),n,0,30); /* Martin Ettl, Oct 23 2012 */
    
  • PARI
    A000178(n)=prod(k=2,n,k!) \\ M. F. Hasler, Sep 02 2007
    
  • PARI
    a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/prod(j=1, k+1, (1+j!*x+x*O(x^n)) )), n) \\ Paul D. Hanna, Oct 02 2013
    
  • PARI
    for(j=1,13, print1(prod(k=1,j,k^(j-k)),", ")) \\ Hugo Pfoertner, Apr 09 2020
    
  • Python
    A000178_list, n, m = [1], 1,1
    for i in range(1,100):
        m *= i
        n *= m
        A000178_list.append(n) # Chai Wah Wu, Aug 21 2015
    
  • Python
    from math import prod
    def A000178(n): return prod(i**(n-i+1) for i in range(2,n+1)) # Chai Wah Wu, Nov 26 2023
  • Ruby
    def mono_choices(a,b,n)
        n - [a,b].max
    end
    def comm_mono_choices(n)
        accum =1
        0.upto(n-1) do |i|
            i.upto(n-1) do |j|
                accum = accum * mono_choices(i,j,n)
            end
        end
        accum
    end
    1.upto(12) do |k|
        puts comm_mono_choices(k)
    end # Chad Brewbaker, Nov 03 2013
    

Formula

a(0) = 1, a(n) = n!*a(n-1). - Lee Hae-hwang, May 13 2003, corrected by Ilya Gutkovskiy, Jul 30 2016
a(0) = 1, a(n) = 1^n * 2^(n-1) * 3^(n-2) * ... * n = Product_{r=1..n} r^(n-r+1). - Amarnath Murthy, Dec 12 2003 [Formula corrected by Derek Orr, Jul 27 2014]
a(n) = sqrt(A055209(n)). - Philippe Deléham, Mar 07 2004
a(n) = Product_{i=1..n} Product_{j=0..i-1} (i-j). - Paul Barry, Aug 02 2008
log a(n) = 0.5*n^2*log n - 0.75*n^2 + O(n*log n). - Charles R Greathouse IV, Jan 13 2012
Asymptotic: a(n) ~ exp(zeta'(-1) - 3/4 - (3/4)*n^2 - (3/2)*n)*(2*Pi)^(1/2 + (1/2)*n)*(n+1)^((1/2)*n^2 + n + 5/12). For example, a(100) is approx. 0.270317...*10^6941. (See A213080.) - Peter Luschny, Jun 23 2012
G.f.: 1 + x/(U(0) - x) where U(k) = 1 + x*(k+1)! - x*(k+2)!/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2012
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - 1/(1 + 1/((k+1)!*x*G(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Jun 14 2013
G.f.: 1 = Sum_{n>=0} a(n)*x^n / Product_{k=1..n+1} (1 + k!*x). - Paul D. Hanna, Oct 02 2013
A203227(n+1)/a(n) -> e, as n -> oo. - Daniel Suteu, Jul 30 2016
From Ilya Gutkovskiy, Jul 30 2016: (Start)
a(n) = G(n+2), where G(n) is the Barnes G-function.
a(n) ~ exp(1/12 - n*(3*n+4)/4)*n^(n*(n+2)/2 + 5/12)*(2*Pi)^((n+1)/2)/A, where A is the Glaisher-Kinkelin constant (A074962).
Sum_{n>=0} (-1)^n/a(n) = A137986. (End)
0 = a(n)*a(n+2)^3 + a(n+1)^2*a(n+2)^2 - a(n+1)^3*a(n+3) for all n in Z (if a(-1)=1). - Michael Somos, Mar 11 2020
Sum_{n>=0} 1/a(n) = A287013 = 1/A137987. - Amiram Eldar, Nov 19 2020
a(n) = Wronskian(1, x, x^2, ..., x^n). - Mohammed Yaseen, Aug 01 2023
From Andrea Pinos, Apr 04 2024: (Start)
a(n) = e^(Sum_{k=1..n} (Integral_{x=1..k+1} Psi(x) dx)).
a(n) = e^(Integral_{x=1..n+1} (log(sqrt(2*Pi)) - (x-1/2) + x*Psi(x)) dx).
a(n) = e^(Integral_{x=1..n+1} (log(sqrt(2*Pi)) - (x-1/2) + (n+1)*Psi(x) - log(Gamma(x))) dx).
Psi(x) is the digamma function. (End)

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

Views

Author

Keywords

Comments

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

Examples

			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
		

References

  • 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).

Crossrefs

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

Programs

  • Maple
    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
  • Mathematica
    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 *)

Formula

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

Extensions

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

A099174 Triangle read by rows: coefficients of modified Hermite polynomials.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 3, 0, 1, 3, 0, 6, 0, 1, 0, 15, 0, 10, 0, 1, 15, 0, 45, 0, 15, 0, 1, 0, 105, 0, 105, 0, 21, 0, 1, 105, 0, 420, 0, 210, 0, 28, 0, 1, 0, 945, 0, 1260, 0, 378, 0, 36, 0, 1, 945, 0, 4725, 0, 3150, 0, 630, 0, 45, 0, 1, 0, 10395, 0, 17325, 0, 6930, 0, 990, 0, 55, 0, 1
Offset: 0

Views

Author

Ralf Stephan, on a suggestion of Karol A. Penson, Oct 13 2004

Keywords

Comments

Absolute values of A066325.
T(n,k) is the number of involutions of {1,2,...,n}, having k fixed points (0 <= k <= n). Example: T(4,2)=6 because we have 1243,1432,1324,4231,3214 and 2134. - Emeric Deutsch, Oct 14 2006
Riordan array [exp(x^2/2),x]. - Paul Barry, Nov 06 2008
Same as triangle of Bessel numbers of second kind, B(n,k) (see Cheon et al., 2013). - N. J. A. Sloane, Sep 03 2013
The modified Hermite polynomial h(n,x) (as in the Formula section) is the numerator of the rational function given by f(n,x) = x + (n-2)/f(n-1,x), where f(x,0) = 1. - Clark Kimberling, Oct 20 2014
Second lower diagonal T(n,n-2) equals positive triangular numbers A000217 \ {0}. - M. F. Hasler, Oct 23 2014
From James East, Aug 17 2015: (Start)
T(n,k) is the number of R-classes (equivalently, L-classes) in the D-class consisting of all rank k elements of the Brauer monoid of degree n.
For n < k with n == k (mod 2), T(n,k) is the rank (minimal size of a generating set) and idempotent rank (minimal size of an idempotent generating set) of the ideal consisting of all rank <= k elements of the Brauer monoid. (End)
This array provides the coefficients of a Laplace-dual sequence H(n,x) of the Dirac delta function, delta(x), and its derivatives, formed by taking the inverse Laplace transform of these modified Hermite polynomials. H(n,x) = h(n,D) delta(x) with h(n,x) as in the examples and the lowering and raising operators L = -x and R = -x + D = -x + d/dx such that L H(n,x) = n * H(n-1,x) and R H(n,x) = H(n+1,x). The e.g.f. is exp[t H(.,x)] = e^(t^2/2) e^(t D) delta(x) = e^(t^2/2) delta(x+t). - Tom Copeland, Oct 02 2016
Antidiagonals of this entry are rows of A001497. - Tom Copeland, Oct 04 2016
This triangle is the reverse of that in Table 2 on p. 7 of the Artioli et al. paper and Table 6.2 on p. 234 of Licciardi's thesis, with associations to the telephone numbers. - Tom Copeland, Jun 18 2018 and Jul 08 2018
See A344678 for connections to a Heisenberg-Weyl algebra of differential operators, matching and independent edge sets of the regular n-simplices with partially labeled vertices, and telephone switchboard scenarios. - Tom Copeland, Jun 02 2021

Examples

			h(0,x) = 1
h(1,x) = x
h(2,x) = x^2 + 1
h(3,x) = x^3 + 3*x
h(4,x) = x^4 + 6*x^2 + 3
h(5,x) = x^5 + 10*x^3 + 15*x
h(6,x) = x^6 + 15*x^4 + 45*x^2 + 15
From _Paul Barry_, Nov 06 2008: (Start)
Triangle begins
   1,
   0,  1,
   1,  0,  1,
   0,  3,  0,  1,
   3,  0,  6,  0,  1,
   0, 15,  0, 10,  0,  1,
  15,  0, 45,  0, 15,  0,  1
Production array starts
  0, 1,
  1, 0, 1,
  0, 2, 0, 1,
  0, 0, 3, 0, 1,
  0, 0, 0, 4, 0, 1,
  0, 0, 0, 0, 5, 0, 1 (End)
		

Crossrefs

Row sums (polynomial values at x=1) are A000085.
Polynomial values: A005425 (x=2), A202834 (x=3), A202879(x=4).
Cf. A137286.
Cf. A001497.

Programs

  • Maple
    T:=proc(n,k) if n-k mod 2 = 0 then n!/2^((n-k)/2)/((n-k)/2)!/k! else 0 fi end: for n from 0 to 12 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form; Emeric Deutsch, Oct 14 2006
  • Mathematica
    nn=10;a=y x+x^2/2!;Range[0,nn]!CoefficientList[Series[Exp[a],{x,0,nn}],{x,y}]//Grid  (* Geoffrey Critzer, May 08 2012 *)
    H[0, x_] = 1; H[1, x_] := x; H[n_, x_] := H[n, x] = x*H[n-1, x]-(n-1)* H[n-2, x]; Table[CoefficientList[H[n, x], x], {n, 0, 11}] // Flatten // Abs (* Jean-François Alcover, May 23 2016 *)
    T[ n_, k_] := If[ n < 0, 0, Coefficient[HermiteH[n, x I/Sqrt[2]] (Sqrt[1/2]/I)^n, x, k]]; (* Michael Somos, May 10 2019 *)
  • PARI
    T(n,k)=if(k<=n && k==Mod(n,2), n!/k!/(k=(n-k)/2)!>>k) \\ M. F. Hasler, Oct 23 2014
    
  • Python
    import sympy
    from sympy import Poly
    from sympy.abc import x, y
    def H(n, x): return 1 if n==0 else x if n==1 else x*H(n - 1, x) - (n - 1)*H(n - 2, x)
    def a(n): return [abs(cf) for cf in Poly(H(n, x), x).all_coeffs()[::-1]]
    for n in range(21): print(a(n)) # Indranil Ghosh, May 26 2017
    
  • Python
    def Trow(n: int) -> list[int]:
        row: list[int] = [0] * (n + 1); row[n] = 1
        for k in range(n - 2, -1, -2):
            row[k] = (row[k + 2] * (k + 2) * (k + 1)) // (n - k)
        return row  # Peter Luschny, Jan 08 2023
  • Sage
    def A099174_triangle(dim):
        M = matrix(ZZ,dim,dim)
        for n in (0..dim-1): M[n,n] = 1
        for n in (1..dim-1):
            for k in (0..n-1):
                M[n,k] = M[n-1,k-1]+(k+1)*M[n-1,k+1]
        return M
    A099174_triangle(9)  # Peter Luschny, Oct 06 2012
    

Formula

h(k, x) = (-I/sqrt(2))^k * H(k, I*x/sqrt(2)), H(n, x) the Hermite polynomials (A060821, A059343).
T(n,k) = n!/(2^((n-k)/2)*((n-k)/2)!k!) if n-k >= 0 is even; 0 otherwise. - Emeric Deutsch, Oct 14 2006
G.f.: 1/(1-x*y-x^2/(1-x*y-2*x^2/(1-x*y-3*x^2/(1-x*y-4*x^2/(1-... (continued fraction). - Paul Barry, Apr 10 2009
E.g.f.: exp(y*x + x^2/2). - Geoffrey Critzer, May 08 2012
Recurrence: T(0,0)=1, T(0,k)=0 for k>0 and for n >= 1 T(n,k) = T(n-1,k-1) + (k+1)*T(n-1,k+1). - Peter Luschny, Oct 06 2012
T(n+2,n) = A000217(n+1), n >= 0. - M. F. Hasler, Oct 23 2014
The row polynomials P(n,x) = (a. + x)^n, umbrally evaluated with (a.)^n = a_n = aerated A001147, are an Appell sequence with dP(n,x)/dx = n * P(n-1,x). The umbral compositional inverses (cf. A001147) of these polynomials are given by the same polynomials signed, A066325. - Tom Copeland, Nov 15 2014
From Tom Copeland, Dec 13 2015: (Start)
The odd rows are (2x^2)^n x n! L(n,-1/(2x^2),1/2), and the even, (2x^2)^n n! L(n,-1/(2x^2),-1/2) in sequence with n= 0,1,2,... and L(n,x,a) = Sum_{k=0..n} binomial(n+a,k+a) (-x)^k/k!, the associated Laguerre polynomial of order a. The odd rows are related to A130757, and the even to A176230 and A176231. Other versions of this entry are A122848, A049403, A096713 and A104556, and reversed A100861, A144299, A111924. With each non-vanishing diagonal divided by its initial element A001147(n), this array becomes reversed, aerated A034839.
Create four shift and stretch matrices S1,S2,S3, and S4 with all elements zero except S1(2n,n) = 1 for n >= 1, S2(n,2n) = 1 for n >= 0, S3(2n+1,n) = 1 for n >= 1, and S4(n,2n+1) = 1 for n >= 0. Then this entry's lower triangular matrix is T = Id + S1 * (A176230-Id) * S2 + S3 * (unsigned A130757-Id) * S4 with Id the identity matrix. The sandwiched matrices have infinitesimal generators with the nonvanishing subdiagonals A000384(n>0) and A014105(n>0).
As an Appell sequence, the lowering and raising operators are L = D and R = x + dlog(exp(D^2/2))/dD = x + D, where D = d/dx, L h(n,x) = n h(n-1,x), and R h(n,x) = h(n+1,x), so R^n 1 = h(n,x). The fundamental moment sequence has the e.g.f. e^(t^2/2) with coefficients a(n) = aerated A001147, i.e., h(n,x) = (a. + x)^n, as noted above. The raising operator R as a matrix acting on o.g.f.s (formal power series) is the transpose of the production matrix P below, i.e., (1,x,x^2,...)(P^T)^n (1,0,0,...)^T = h(n,x).
For characterization as a Riordan array and associations to combinatorial structures, see the Barry link and the Yang and Qiao reference. For relations to projective modules, see the Sazdanovic link.
(End)
From the Appell formalism, e^(D^2/2) x^n = h_n(x), the n-th row polynomial listed below, and e^(-D^2/2) x^n = u_n(x), the n-th row polynomial of A066325. Then R = e^(D^2/2) * x * e^(-D^2/2) is another representation of the raising operator, implied by the umbral compositional inverse relation h_n(u.(x)) = x^n. - Tom Copeland, Oct 02 2016
h_n(x) = p_n(x-1), where p_n(x) are the polynomials of A111062, related to the telephone numbers A000085. - Tom Copeland, Jun 26 2018
From Tom Copeland, Jun 06 2021: (Start)
In the power basis x^n, the matrix infinitesimal generator M = A132440^2/2, when acting on a row vector for an o.g.f., is the matrix representation for the differential operator D^2/2.
e^{M} gives the coefficients of the Hermite polynomials of this entry.
The only nonvanishing subdiagonal of M, the second subdiagonal (1,3,6,10,...), gives, aside from the initial 0, the triangular numbers A000217, the number of edges of the n-dimensional simplices with (n+1) vertices. The perfect matchings of these simplices are the aerated odd double factorials A001147 noted above, the moments for the Hermite polynomials.
The polynomials are also generated from A036040 with x[1] = x, x[2] = 1, and the other indeterminates equal to zero. (End)

A047970 Antidiagonal sums of nexus numbers (A047969).

Original entry on oeis.org

1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486, 182905, 919146, 4866871, 27068420, 157693007, 959873708, 6091057009, 40213034874, 275699950381, 1959625294310, 14418124498211, 109655727901592, 860946822538675, 6969830450679864, 58114638923638573
Offset: 0

Views

Author

Alford Arnold, Dec 11 1999

Keywords

Comments

From Lara Pudwell, Oct 23 2008: (Start)
A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.
Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.
A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.
For example, if q=5{bar 1}32{bar 4}, then q1=532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)
Number of ordered factorizations over the Gaussian polynomials.
Apparently, also the number of permutations in S_n avoiding {bar 3}{bar 1}542 (i.e., every occurrence of 542 is contained in an occurrence of a 31542). - Lara Pudwell, Apr 25 2008
With offset 1, apparently the number of sequences {b(m)} of length n of positive integers with b(1) = 1 and, for all m > 1, b(m) <= max{b(m-1) + 1, max{b(i) | 1 <= i <= m - 1}}. This sequence begins 1, 2, 5, 14, 43, 144, 523, 2048, 8597, 38486. The term 144 counts the length 6 sequence 1, 2, 3, 1, 1, 3, for instance. Contrast with the families of sequences discussed in Franklin T. Adams-Watters's comment in A005425. - Rick L. Shepherd, Jan 01 2015
a(n-1) for n >= 1 is the number of length-n restricted growth strings (RGS) [s(0), s(1), ..., s(n-1)] with s(0)=0 and s(k) <= the number of fixed points in the prefix, see example. - Joerg Arndt, Mar 08 2015
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) = e(k). [Martinez and Savage, 2.15] - Eric M. Schmidt, Jul 17 2017
a(n) counts all positive-integer m-tuples whose maximum is n-m+2. - Mathew Englander, Feb 28 2021
a(n) counts the cyclic permutations of [n+2] that avoid the vincular pattern 12-3-4, i.e., the pattern 1234 where the 1 and 2 are required to be adjacent. - Rupert Li, Jul 27 2021

Examples

			a(3) = 1 + 5 + 7 + 1 = 14.
From _Paul D. Hanna_, Jul 22 2014:  (Start)
G.f. A(x) = 1 + 2*x + 5*x^2 + 14*x^3 + 43*x^4 + 144*x^5 + 523*x^6 + 2048*x^7 + ...
where we have the series identity:
A(x) = (1-x)*( 1/(1-2*x) + x/(1-3*x) + x^2/(1-4*x) + x^3/(1-5*x) + x^4/(1-6*x) + x^5/(1-7*x) + x^6/(1-8*x) + ...)
is equal to
A(x) = 1/(1-x) + x/((1-x)*(1-2*x)) + x^2/((1-2*x)*(1-3*x)) + x^3/((1-3*x)*(1-4*x)) + x^4/((1-4*x)*(1-5*x)) + x^5/((1-5*x)*(1-6*x)) + x^6/((1-6*x)*(1-7*x)) + ...
and also equals
A(x) = 1/((1-x)*(1+x)) + 2!*x/((1-x)^2*(1+x)*(1+2*x)) + 3!*x^2/((1-x)^3*(1+x)*(1+2*x)*(1+3*x)) + 4!*x^3/((1-x)^4*(1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + ...
(End)
From _Joerg Arndt_, Mar 08 2015: (Start)
There are a(4-1)=14 length-4 RGS as in the comment (dots denote zeros):
01:  [ . . . . ]
02:  [ . . . 1 ]
03:  [ . . 1 . ]
04:  [ . . 1 1 ]
05:  [ . 1 . . ]
06:  [ . 1 . 1 ]
07:  [ . 1 . 2 ]
08:  [ . 1 1 . ]
09:  [ . 1 1 1 ]
10:  [ . 1 1 2 ]
11:  [ . 1 2 . ]
12:  [ . 1 2 1 ]
13:  [ . 1 2 2 ]
14:  [ . 1 2 3 ]
(End)
		

Crossrefs

Antidiagonal sums of A085388 (beginning with the second antidiagonal) and A047969.
Partial sums are in A026898, A003101. First differences A112532.

Programs

  • Maple
    T := proc(n, k) option remember; local j;
        if k=n then 1
      elif k>n then 0
      else (k+1)*T(n-1, k) + add(T(n-1, j), j=k..n)
        fi end:
    A047970 := n -> T(n,0);
    seq(A047970(n), n=0..24); # Peter Luschny, May 14 2014
  • Mathematica
    a[ n_] := SeriesCoefficient[ ((1 - x) Sum[ x^k / (1 - (k + 2) x), {k, 0, n}]), {x, 0, n}]; (* Michael Somos, Jul 09 2014 *)
  • PARI
    /* From o.g.f. (Paul D. Hanna, Jul 20 2014) */
    {a(n)=polcoeff( sum(m=0, n, (m+1)!*x^m/(1-x)^(m+1)/prod(k=1, m+1, 1+k*x +x*O(x^n))), n)}
    for(n=0, 25, print1(a(n), ", "))
    
  • PARI
    /* From o.g.f. (Paul D. Hanna, Jul 22 2014) */
    {a(n)=polcoeff( sum(m=0, n, x^m/((1-m*x)*(1-(m+1)*x +x*O(x^n)))), n)}
    for(n=0, 25, print1(a(n), ", "))
  • Sage
    def A074664():
        T = []; n = 0
        while True:
            T.append(1)
            yield T[0]
            for k in (0..n):
                T[k] = (k+1)*T[k] + add(T[j] for j in (k..n))
            n += 1
    a = A074664()
    [next(a) for n in range(25)] # Peter Luschny, May 13 2014
    

Formula

Formal o.g.f.: (1 - x)*( Sum_{n >= 0} x^n/(1 - (n + 2)*x) ). - Peter Bala, Jul 09 2014
O.g.f.: Sum_{n>=0} (n+1)! * x^n/(1-x)^(n+1) / Product_{k=1..n+1} (1 + k*x). - Paul D. Hanna, Jul 20 2014
O.g.f.: Sum_{n>=0} x^n / ( (1 - n*x) * (1 - (n+1)*x) ). - Paul D. Hanna, Jul 22 2014
From Mathew Englander, Feb 28 2021: (Start)
a(n) = A089246(n+2,0) = A242431(n,0).
a(n) = Sum_{m = 1..n+1} Sum_{i = 0..m-1} binomial(m,i) * (n-m+1)^i.
a(n) = 1 + Sum_{i = 0..n} i * (i+1)^(n-i). (End)
a(n) ~ sqrt(2*Pi*n / (w*(1+w))) * (1 + n/w)^(1 + n - n/w), where w = LambertW(exp(1)*n). - Vaclav Kotesovec, Jun 10 2025

A080107 Number of fixed points of permutation of SetPartitions under {1,2,...,n}->{n,n-1,...,1}. Number of symmetric arrangements of non-attacking rooks on upper half of n X n chessboard.

Original entry on oeis.org

1, 1, 2, 3, 7, 12, 31, 59, 164, 339, 999, 2210, 6841, 16033, 51790, 127643, 428131, 1103372, 3827967, 10269643, 36738144, 102225363, 376118747, 1082190554, 4086419601, 12126858113, 46910207114, 143268057587, 566845074703, 1778283994284, 7186474088735
Offset: 0

Views

Author

Wouter Meeussen, Mar 15 2003

Keywords

Comments

Even-numbered terms a(2k) are A002872: 2,7,31,164,999 ("Sorting numbers"); odd-numbered terms are its binomial transform, A080337. The symmetrical set partitions of {-n,...,-1,0,1,...,n} can be classified by the partition containing 0. Thus we get the sum over k of {n choose k} times the number of symmetrical set partitions of 2n-2k elements. - Don Knuth, Nov 23 2003
Number of partitions of n numbers that are symmetrical and cannot be nested (i.e., include a pattern of the form abab). - Douglas Boffey, May 21 2015
Number of achiral color patterns in a row or loop of length n. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 23 2018
Also the number of self-complementary set partitions of {1, ..., n}. The complement of a set partition pi of {1, ..., n} is defined as n + 1 - pi (elementwise) on page 3 of Callan. For example, the complement of {{1,5},{2},{3,6},{4}} is {{1,4},{2,6},{3},{5}}. - Gus Wiseman, Feb 13 2019

Examples

			Of the set partitions of 4, the following 7 are invariant under 1->4, 2->3, 3->2, 4->1: {{1,2,3,4}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,3},{2,4}}, {{1},{2,3},{4}}, {{1,4},{2},{3}}, {{1},{2},{3},{4}}, so a(4)=7.
For a(4)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD (same as previous example).  The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 23 2018
From _Gus Wiseman_, Feb 13 2019: (Start)
The a(1) = 1 through a(5) = 12 self-complementary set partitions:
  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
         {{1}{2}}  {{13}{2}}    {{12}{34}}      {{1245}{3}}
                   {{1}{2}{3}}  {{13}{24}}      {{135}{24}}
                                {{14}{23}}      {{15}{234}}
                                {{1}{23}{4}}    {{1}{234}{5}}
                                {{14}{2}{3}}    {{12}{3}{45}}
                                {{1}{2}{3}{4}}  {{135}{2}{4}}
                                                {{14}{25}{3}}
                                                {{15}{24}{3}}
                                                {{1}{24}{3}{5}}
                                                {{15}{2}{3}{4}}
                                                {{1}{2}{3}{4}{5}}
(End)
		

References

  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765).

Crossrefs

Programs

  • Mathematica
    < Range[n, 1, -1]]; t= 1 + RankSetPartition /@ t; t= ToCycles[t]; t= Cases[t, {_Integer}]; Length[t], {n, 7}]
    (* second program: *)
    QB[n_, q_] := QB[n, q] = Sum[QB[j, q] QBinomial[n-1, j, q], {j, 0, n-1}] // FunctionExpand // Simplify; QB[0, q_]=1; QB[1, q_]=1; Table[cc = CoefficientList[QB[n, q], q]; cc.Table[(-1)^(k+1), {k, 1, Length[cc]}], {n, 0, 30}] (* Jean-François Alcover, Feb 29 2016, after Paul D. Hanna *)
    (* Ach[n, k] is the number of achiral color patterns for a row or loop of n
      colors containing exactly k different colors *)
    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[Sum[Ach[n, k], {k, 0, n}], {n, 0, 30}] (* Robert A. Russell, Apr 23 2018 *)
    x[n_] := x[n] = If[n < 2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
    Table[Sum[StirlingS2[Ceiling[n/2], k] x[k-Mod[n, 2]], {k, 0, Ceiling[n/2]}],
      {n, 0, 30}] (* Robert A. Russell, Apr 27 2018, after Knuth reference *)

Formula

Knuth gives recurrences and generating functions.
a(n) = Sum_{k=0..t(n)} (-1)^k*A125810(n,k) where A125810 is a triangle of coefficients for a q-analog of the Bell numbers and t(n)=A125811(n)-1. - Paul D. Hanna, Jan 19 2009
From Robert A. Russell, Apr 23 2018: (Start)
a(n) = Sum_{k=0..n} Ach(n,k) where
Ach(n,k) = [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) + [n<2]*[n==k]*[n>=0].
a(n) = 2*A103293(n+1) - A000110(n). (End)
a(n) = [n==0 mod 2]*Sum_{k=0..n/2} Stirling2(n/2, k)*A005425(k) + [n==1 mod 2] * Sum_{k=1..(n+1)/2} Stirling2((n+1)/2, k) * A005425(k-1). (from Knuth reference)
a(n) = 2*A084708(n) - A084423(n). - Robert A. Russell, Apr 27 2018

Extensions

Offset set to 0 by Alois P. Heinz, May 23 2015

A080337 Bisection of A080107.

Original entry on oeis.org

1, 3, 12, 59, 339, 2210, 16033, 127643, 1103372, 10269643, 102225363, 1082190554, 12126858113, 143268057587, 1778283994284, 23120054355195, 314017850216371, 4444972514600178, 65435496909148513, 999907522895563403, 15832873029742458796, 259377550023571768075
Offset: 1

Views

Author

Wouter Meeussen, Mar 18 2003

Keywords

Comments

Number of symmetric positions of non-attacking rooks on upper-diagonal part of 2n X 2n chessboard.
Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=2+max(prefix) for k>=1, see example. - Joerg Arndt, Apr 25 2010
Number of achiral color patterns in a row or loop of length 2n-1. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 24 2018
Stirling transform of A005425(n-1) per Knuth reference. - Robert A. Russell, Apr 28 2018

Examples

			From _Joerg Arndt_, Apr 25 2010: (Start)
For n=0 there is one empty string (term a(0)=0 not included here); for n=1 there is one string [0]; for n=2 there are 3 strings [00], [01], and [02];
for n=3 there are a(3)=12 strings (in lexicographic order):
01: [000],
02: [001],
03: [002],
04: [010],
05: [011],
06: [012],
07: [013],
08: [020],
09: [021],
10: [022],
11: [023],
12: [024].
(End)
For a(3) = 12, both the row and loop patterns are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, ABCBA, ABCBD, ABCDA, and ABCDE. - _Robert A. Russell_, Apr 24 2018
		

References

  • 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

Crossrefs

Row sums of A140735.
Column k=2 of A305962.

Programs

  • Maple
    b:= proc(n, m) option remember; `if`(n=0, 1,
          add(b(n-1, max(m, j)), j=1..m+2))
        end:
    a:= n-> b(n, -1):
    seq(a(n), n=1..25);  # Alois P. Heinz, Jun 15 2018
  • Mathematica
    Table[Sum[ Binomial[n, k] A002872[[k + 1]], {k, 0, n}], {n, 0, 24}]
    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[Sum[Aodd[m, k], {k, 1, 2m-1}], {m, 1, 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-1], {k, 0, n}], {n, 30}] (* Robert A. Russell, Apr 28 2018, after Knuth reference *)
  • PARI
    x='x+O('x^66);
    egf=exp(x+exp(x)+exp(2*x)/2-3/2); /* = 1 +3*x +6*x^2 +59/6*x^3 +113/8*x^4 +... */
    Vec(serlaplace(egf)) /* Joerg Arndt, Apr 29 2011 */

Formula

Binomial transform of A002872 (sorting numbers).
E.g.f.: exp(x+exp(x)+exp(2*x)/2-3/2) = exp(x+sum(j=1,2, (exp(j*x)-1)/j ) ). - Joerg Arndt, Apr 29 2011
From Robert A. Russell, Apr 24 2018: (Start)
Aodd[n,k] = [n>1]*(k*Aodd[n-1,k]+Aodd[n-1,k-1]+Aodd[n-1,k-2])+[n==1]*[k==1]
a(n) = Sum_{k=1..2n-1} Aodd[n,k]. (End)
a(n) = Sum_{k=0..n} Stirling2(n, k)*A005425(k-1). (from Knuth reference) - Robert A. Russell, Apr 28 2018

Extensions

Comment corrected by Wouter Meeussen, Aug 14 2009

A202827 Expansion of e.g.f.: exp(4*x/(1-x)) / sqrt(1-x^2).

Original entry on oeis.org

1, 4, 25, 196, 1849, 20164, 249001, 3422500, 51739249, 851822596, 15155825881, 289527934084, 5906625426025, 128089110981316, 2940882813228649, 71239270847432164, 1815115761586307041, 48511703775281296900, 1356708799439194070809, 39615996090901693902916
Offset: 0

Views

Author

Paul D. Hanna, Dec 25 2011

Keywords

Examples

			E.g.f.: A(x) = 1 + 4*x + 25*x^2/2! + 196*x^3/3! + 1849*x^4/4! +...
where A(x) = 1 + 2^2*x + 5^2*x^2/2! + 14^2*x^3/3! + 43^2*x^4/4! +...+ A005425(n)^2*x^n/n! +...
		

Crossrefs

Programs

  • Magma
    R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!(Laplace( Exp(4*x/(1-x))/Sqrt(1-x^2) ))); // G. C. Greubel, Jun 21 2022
    
  • Mathematica
    With[{nn=20},CoefficientList[Series[Exp[(4x)/(1-x)]/Sqrt[1-x^2], {x,0,nn}], x]Range[0,nn]!] (* Harvey P. Dale, Dec 31 2011 *)
  • PARI
    {a(n)=n!*polcoeff(exp(4*x/(1-x)+x*O(x^n))/sqrt(1-x^2+x*O(x^n)),n)}
    
  • PARI
    {a(n)=sum(k=0,n\2,2^(n-3*k)*n!/((n-2*k)!*k!))^2}
    
  • SageMath
    def A202827_list(prec):
        P. = PowerSeriesRing(QQ, prec)
        return P( exp(4*x/(1-x))/sqrt(1-x^2) ).egf_to_ogf().list()
    A202827_list(40) # G. C. Greubel, Jun 21 2022

Formula

a(n) = A005425(n)^2, where the e.g.f. of A005425 is exp(2*x + x^2/2).
a(n) = ( Sum_{k=0..[n/2]} 2^(n-3*k)*n!/((n-2*k)!*k!) )^2. [From formula by Huajun Huang in A005425]
a(n) ~ n^n*exp(4*sqrt(n)-2-n)/2 * (1+5/(3*sqrt(n))). - Vaclav Kotesovec, May 23 2013
D-finite with recurrence: a(n) = (n+3)*a(n-1) +(n-1)*(n+3)*a(n-2) - (n-1)*(n-2)^2*a(n-3). - Vaclav Kotesovec, May 23 2013

A334548 Array read by antidiagonals: T(n,k) is the number of n X n symmetric binary matrices with no row sum greater than k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 2, 8, 14, 1, 1, 2, 8, 45, 43, 1, 1, 2, 8, 64, 315, 142, 1, 1, 2, 8, 64, 809, 2634, 499, 1, 1, 2, 8, 64, 1024, 13846, 25518, 1850, 1, 1, 2, 8, 64, 1024, 28217, 301262, 280257, 7193, 1, 1, 2, 8, 64, 1024, 32768, 1146419, 8035168, 3434595, 29186, 1
Offset: 0

Views

Author

Andrew Howroyd, May 08 2020

Keywords

Examples

			Array begins:
=============================================================
n\k | 0    1      2       3        4         5         6
----|-------------------------------------------------------
  0 | 1    1      1       1        1         1         1 ...
  1 | 1    2      2       2        2         2         2 ...
  2 | 1    5      8       8        8         8         8 ...
  3 | 1   14     45      64       64        64        64 ...
  4 | 1   43    315     809     1024      1024      1024 ...
  5 | 1  142   2634   13846    28217     32768     32768 ...
  6 | 1  499  25518  301262  1146419   1914733   2097152 ...
  7 | 1 1850 280257 8035168 62951431 178499118 254409765 ...
  ...
		

Crossrefs

Formula

T(n,k) = 2^(n*(n+1)/2) = A006125(n+1) for k >= n.
Showing 1-10 of 33 results. Next