A004747 Triangle read by rows: the Bell transform of the triple factorial numbers A008544 without column 0.
1, 2, 1, 10, 6, 1, 80, 52, 12, 1, 880, 600, 160, 20, 1, 12320, 8680, 2520, 380, 30, 1, 209440, 151200, 46480, 7840, 770, 42, 1, 4188800, 3082240, 987840, 179760, 20160, 1400, 56, 1, 96342400, 71998080, 23826880, 4583040, 562800, 45360, 2352, 72, 1
Offset: 1
Examples
Triangle begins:
1;
2, 1;
10, 6, 1;
80, 52, 12, 1;
880, 600, 160, 20, 1;
12320, 8680, 2520, 380, 30, 1;
209440, 151200, 46480, 7840, 770, 42, 1;
Tree combinatorics for T(3,2)=6: Consider first the unordered forest of m=2 plane trees with n=3 vertices, namely one vertex with out-degree r=0 (root) and two different trees with two vertices (one root with out-degree r=1 and a leaf with r=0). The 6 increasing labelings come then from the forest with rooted (x) trees x, o-x (1,(3,2)), (2,(3,1)) and (3,(2,1)) and similarly from the second forest x, x-o (1,(2,3)), (2,(1,3)) and (3,(1,2)).
Links
- G. C. Greubel, Rows n = 1..50 of the triangle, flattened
- F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
- P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
- Richell O. Celeste, Roberto B. Corcino, and Ken Joffaniel M. Gonzales. Two Approaches to Normal Order Coefficients, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
- Tom Copeland, A Class of Differential Operators and the Stirling Numbers
- Milan Janjic, Some classes of numbers and derivatives, JIS 12 (2009) #09.8.3.
- Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
- Wolfdieter Lang, Combinatorial Interpretation of Generalized Stirling Numbers, J. Int. Seqs. Vol. 12 (2009) #09.3.3.
- Mathias Pétréolle and Alan D. Sokal, Lattice paths and branched continued fractions. II. Multivariate Lah polynomials and Lah symmetric functions, arXiv:1907.02645 [math.CO], 2019.
- Index entries for sequences related to Bessel functions or polynomials
Crossrefs
Programs
-
Magma
function T(n,k) // T = A004747 if k eq 0 then return 0; elif k eq n then return 1; else return (3*(n-1)-k)*T(n-1,k) + T(n-1,k-1); end if; end function; [T(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Oct 03 2023
-
Maple
T := (n, m) -> 3^n/m!*(1/3*m*GAMMA(n-1/3)*hypergeom([1-1/3*m, 2/3-1/3*m, 1/3-1/3*m], [2/3, 4/3-n], 1)/GAMMA(2/3)-1/6*m*(m-1)*GAMMA(n-2/3)*hypergeom( [1-1/3*m, 2/3-1/3*m, 4/3-1/3*m], [4/3, 5/3-n], 1)/Pi*3^(1/2)*GAMMA(2/3)): for n from 1 to 6 do seq(simplify(T(n,k)),k=1..n) od; # Karol A. Penson, Feb 06 2004 # The function BellMatrix is defined in A264428. # Adds (1,0,0,0, ..) as column 0. BellMatrix(n -> mul(3*k+2, k=(0..n-1)), 9); # Peter Luschny, Jan 29 2016
-
Mathematica
(* First program *) T[1,1]= 1; T[, 0]= 0; T[0, ]= 0; T[n_, m_]:= (3*(n-1)-m)*T[n-1, m]+T[n-1, m-1]; Flatten[Table[T[n, m], {n,12}, {m,n}] ][[1 ;; 45]] (* Jean-François Alcover, Jun 16 2011, after recurrence *) (* Second program *) f[n_, m_]:= m/n Sum[Binomial[k, n-m-k] 3^k (-1)^(n-m-k) Binomial[n+k-1, n-1], {k, 0, n-m}]; Table[n! f[n, m]/(m! 3^(n-m)), {n,12}, {m,n}]//Flatten (* Michael De Vlieger, Dec 23 2015 *) (* Third program *) rows = 12; T[n_, m_]:= BellY[n, m, Table[Product[3k+2, {k, 0, j-1}], {j, 0, rows}]]; Table[T[n, m], {n,rows}, {m,n}]//Flatten (* Jean-François Alcover, Jun 22 2018 *)
-
Sage
# uses [bell_transform from A264428] triplefactorial = lambda n: prod(3*k+2 for k in (0..n-1)) def A004747_row(n): trifact = [triplefactorial(k) for k in (0..n)] return bell_transform(n, trifact) [A004747_row(n) for n in (0..10)] # Peter Luschny, Dec 21 2015
Formula
T(n, m) = n!*A048966(n, m)/(m!*3^(n-m));
T(n+1, m) = (3*n-m)*T(n, m)+ T(n, m-1), for n >= m >= 1, with T(n, m) = 0, for n
E.g.f. of m-th column: ( 1 - (1-3*x)^(1/3) )^m/m!.
Sum_{k=1..n} T(n, k) = A015735(n).
For a formula expressed as special values of hypergeometric functions 3F2 see the Maple program below. - Karol A. Penson, Feb 06 2004
T(n,1) = A008544(n-1). - Peter Luschny, Dec 23 2015
Extensions
New name from Peter Luschny, Dec 21 2015
A112936 INVERT transform (with offset) of triple factorials (A008544), where g.f. satisfies: A(x) = 1 + x*[d/dx x*A(x)^3]/A(x)^3.
1, 1, 3, 15, 111, 1131, 14943, 243915, 4742391, 106912131, 2739347103, 78569371275, 2492748594471, 86650852740531, 3274367635513263, 133625238021647835, 5856377114106629751, 274320168321004350531
Offset: 0
Keywords
Examples
A(x) = 1 + x + 3*x^2 + 15*x^3 + 111*x^4 + 1131*x^5 + 14943*x^6 +... 1/A(x) = 1 - x - 2*x^2 - 10*x^3 - 80*x^4 - 880*x^5 -...-A008544(n)*x^(n+1)-...
Crossrefs
Programs
-
Mathematica
a = ConstantArray[0,20]; a[[1]]=1; Do[a[[n]] = (3*n-2)*a[[n-1]] - Sum[a[[k]]*a[[n-k]],{k,1,n-1}],{n,2,20}]; Flatten[{1,a}] (* Vaclav Kotesovec after Michael Somos, Feb 22 2014 *) CoefficientList[Series[1/(1+(1/3*ExpIntegralE[2/3,-1/(3*x)])/E^(1/(3*x))), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 22 2014 *) -
PARI
{a(n)=local(F=1+x+x*O(x^n));for(i=1,n,F=1+x+3*x^2*deriv(F)/F); return(polcoeff(F,n,x))} -
PARI
{a(n) = my(A); if( n<1, n==0, A = vector(n, k, 1); for(k=2, n, A[k] = (3*k - 2)*A[k-1] - sum(j=1, k-1, A[j] * A[k-j])); A[n])}; /* Michael Somos, Jul 23 2011 */ -
PARI
{a(n) = if( n<1, n==0, polcoeff( 1 / sum(k=0, n, x^k * prod(i=1, k, 3*i - 4), x * O(x^n)), n))}; /* Michael Somos, Oct 17 2016 */ -
PARI
{a(n) = my(A); if( n<0, 0, A = O(x); for(k=0, n, A = (x + sqrt(x^2 + 4*x^5*A')) / 2); polcoeff(A, 3*n + 1))}; /* Michael Somos, Oct 17 2016 */ -
PARI
{a(n) = my(A); if( n<1, n==0, A = x; for(k=1, n, A = truncate(A) + O(x^(3*k + 4)); A += A + x^4*A' - A^2/x); polcoeff(A, 3*n + 1))}; /* Michael Somos, Oct 17 2016 */
Formula
G.f. satisfies: A(x) = 1+x + 3*x^2*[d/dx A(x)]/A(x) (log derivative).
G.f.: A(x) = 1+x +3*x^2/(1-5*x -3*2*2*x^2/(1-11*x -3*3*5*x^2/(1-17*x -3*4*8*x^2/(1-23*x -... -3*n*(3*n-4)*x^2/(1-(6*n-1)*x -...)))) (continued fraction).
G.f.: A(x) = 1/(1-x/(1 -2*x/(1-3*x/(1 -5*x/(1-6*x/(1 -8*x/(1-9*x/(1 -...)))))))) (continued fraction).
a(n) = (3*n - 2) * a(n-1) - Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011
G.f.: Q(0) where Q(k) = 1 - x*(3*k-1)/(1 - x*(3*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 20 2013
G.f.: 2/G(0)+4*x, where G(k)= 1 + 1/(1 - x*(3*k+3)/(x*(3*k+5) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 25 2013
G.f.: 2/G(0), where G(k)= 1 + 1/(1 - x*(3*k-1)/(x*(3*k-1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 06 2013
G.f.: -4/Sum_{n>=0} [Product_{k=0..n} (3*k-4)]*x^n. - Sergei N. Gladkovskii, Jun 06 2013
a(n) ~ n! * 3^(n-1) / (GAMMA(2/3) * n^(4/3)) . - Vaclav Kotesovec, Feb 22 2014
Given g.f. A(x), then y = x * A(x^3) satisfies y^2 = x*y + x^5*y'. - Michael Somos, Oct 17 2016
A112937 Logarithmic derivative of A112936 such that a(n)=(1/3)*A112936(n+1) for n>0, where A112936 equals the INVERT transform (with offset) of triple factorials A008544.
1, 5, 37, 377, 4981, 81305, 1580797, 35637377, 913115701, 26189790425, 830916198157, 28883617580177, 1091455878504421, 44541746007215945, 1952125704702209917, 91440056107001450177, 4558596081095404198741
Offset: 1
Keywords
Examples
log(1+x + 3*x*[x + 5*x^2 + 37*x^3 + 377*x^4 + 4981*x^5 +...]) = x + 5/2*x^2 + 37/3*x^3 + 377/4*x^4 + 4981/5*x^5 + ...
Crossrefs
Programs
-
PARI
{a(n)=local(F=1+x+x*O(x^n));for(i=1,n,F=1+x+3*x^2*deriv(F)/F); return(n*polcoeff(log(F),n,x))}
Formula
G.f.: log(1+x + 3*x*[Sum_{k>=1} a(n)]) = Sum_{k>=1} a(n)/n*x^n.
A136216 Triangle T, read by rows, where T(n,k) = A008544(n-k)*C(n,k) where A008544 equals the triple factorials in column 0.
1, 2, 1, 10, 4, 1, 80, 30, 6, 1, 880, 320, 60, 8, 1, 12320, 4400, 800, 100, 10, 1, 209440, 73920, 13200, 1600, 150, 12, 1, 4188800, 1466080, 258720, 30800, 2800, 210, 14, 1, 96342400, 33510400, 5864320, 689920, 61600, 4480, 280, 16, 1
Offset: 0
Comments
This array is the particular case P(2,3) of the generalized Pascal triangle P(a,b), a lower unit triangular matrix, shown in the comments to A094587. - Peter Bala, Jul 10 2008
The row polynomials form an Appell sequence. - Tom Copeland, Dec 03 2013
Examples
Triangle begins: 1; 2, 1; 10, 4, 1; 80, 30, 6, 1; 880, 320, 60, 8, 1; 12320, 4400, 800, 100, 10, 1; 209440, 73920, 13200, 1600, 150, 12, 1; 4188800, 1466080, 258720, 30800, 2800, 210, 14, 1; ...
Links
- Wikipedia, Appell sequence
- Wikipedia, Sheffer sequence
Programs
-
Mathematica
(* The function RiordanArray is defined in A256893. *) RiordanArray[1/(1 - 3 #)^(2/3)&, #&, 9, True] // Flatten (* Jean-François Alcover, Jul 19 2019 *)
-
PARI
{T(n,k) = binomial(n,k)*if(n-k==0,1, prod(j=0,n-k-1,3*j+2))} for(n=0,10,for(k=0,n,print1(T(n,k),", "));print(""))
Formula
Column k of T = column 0 of V^(k+1) for k>=0 where V = A112333.
Equals the matrix square of triangle A136215.
T(n,k) = (3*n-3*k-1)*T(n-1,k) + T(n-1,k-1). - Peter Bala, Jul 10 2008
Using the formalism of A132382 modified for the triple rather than the double factorial (replace 2 by 3 in basic formulas), the e.g.f. for the row polynomials is exp(x*t)*(1-3x)^(-2/3). - Tom Copeland, Aug 18 2008
From Peter Bala, Aug 28 2013: (Start)
Exponential Riordan array [1/(1 - 3*y)^(2/3), y].
The row polynomials R(n,x) thus form a Sheffer sequence of polynomials with associated delta operator equal to d/dx. Thus d/dx(R(n,x)) = n*R(n-1,x). The Sheffer identity is R(n,x + y) = sum {k = 0..n} binomial(n,k)*y^(n-k)*R(k,x).
Define a polynomial sequence P(n,x) of binomial type by setting P(n,x) = product {k = 0..n-1} (2*x + 3*k) with the convention that P(0,x) = 1. Then this is triangle of connection constants when expressing the basis polynomials P(n,x + 1) in terms of the basis P(n,x). For example, row 3 is (80, 30, 6, 1) so P(3,x + 1) = (2*x + 2)*(2*x + 5)*(2*x + 8) = 80 + 20*(2*x) + 6*(2*x*(2*x + 3)) + (2*x)*(2*x + 3)*(2*x + 6). (End)
A133480 Left 3-step factorial (n,-3)!: a(n) = (-1)^n * A008544(n).
1, -2, 10, -80, 880, -12320, 209440, -4188800, 96342400, -2504902400, 72642169600, -2324549427200, 81359229952000, -3091650738176000, 126757680265216000, -5577337931669504000, 262134882788466688000, -13106744139423334400000, 694657439389436723200000, -38900816605808456499200000
Offset: 0
Comments
To motivate the definition, consider c(t) = column vector(1, t, t^2, t^3, t^4, t^5, ...), T = A094638 and the list of integers.
Starting at 1 and sampling every integer to the right, we obtain (1,2,3,4,5,...) from which factorials may be formed. It's true that
T * c(1) = (1, 1*2, 1*2*3, 1*2*3*4, ...), giving n! for n > 0. Call this sequence the right 1-step factorial (n,+1)!.
Starting at 1 and sampling every integer to the left, we obtain (1,0,-1,-2,-3,-4,-5,...). And,
T * c(-1) = (1, 1*0, 1*0*-1, 1*0*-1*-2, ...) = (1,0,0,0,...). Call this the left 1-step factorial (n,-1)!.
Sampling every other integer to the right, we obtain (1,3,5,7,9,...).
T * c(2) = (1, 1*3, 1*3*5, ...) = (1,3,15,105,945,...), giving A001147 for n > 0, the right 2-step factorial, (n,+2)!.
Sampling every other integer to the left, we obtain (1,-1,-3,-5,-7,...).
T * c(-2) = (1, 1*-1, 1*-1*-3, 1*-1*-3*-5, ...) = (1,-1,3,-15,105,-945,...) = signed A001147, the left 2-step factorial, (n,-2)!.
Sampling every 3 steps to the right, we obtain (1,4,7,10,...).
T * c(3) = (1, 1*4, 1*4*7, ...) = (1,4,28,280,...), giving A007559 for n > 0, the right 3-step factorial, (n,+3)!.
Sampling every 3 steps to the left, we obtain (1,-2,-5,-8,-11,...), giving
T * c(-3) = (1, 1*-2, 1*-2*-5, 1*-2*-5*-8, ...) = (1,-2,10,-80,880,...) = signed A008544 = the left 3-step factorial, (n,-3)!.
The list partition transform A133314 of [1,T * c(t)] gives signed [1,T *c(-t)]. For example:
LPT[1,T*c(1)] = LPT[1,(n,+1)! ] = LPT[A000142] = (1,-1,0,0,0,...) = signed [1,(n,-1)! ]
LPT[1,T*c(2)] = LPT[1,(n,+2)! ] = LPT[A001147] = (1,-1,-1,-3,-15,-105,-945,...) = (1,-A001147) = signed [1,(n,-2)! ]
LPT[1,T*c(3)] = LPT[1,(n,+3)! ] = LPT[A007559] = (1,-1,-2,-10,-80,-880,...) = (1,-A008544) = signed [1,(n,-3)! ]
LPT[1,T*c(-3)] = LPT[1,(n,-3)! ] = signed A007559 = signed [1,(n,+3)! ].
And, e.g.f.[1,T * c(m)] = e.g.f.[1,(n,m)! ] = (1-m*x)^(-1/m).
Also with P(n,t) = Sum_{k=0..n-1} T(n,k+1) * t^k = 1*(1+t)*(1+2t)...(1+(n-1)*t) and P(0,t)=1, exp[P(.,t)*x] = (1-tx)^(-1/t).
T(n,k+1) = (1/k!) (D_t)^k (D_x)^n [ (1-tx)^(-1/t) - 1 ] evaluated at t=x=0.
And, (1-tx)^(-1/t) - 1 is the e.g.f. for plane increasing m-ary trees when t = (m-1), discussed by Bergeron et al. in "Varieties of Increasing Trees" and the book Combinatorial Species and Tree-Like Structures, cited in the OEIS.
The above relations reveal the intimate connections, through T or LPT or sampling, between the right and left step factorials, (n,+m)! and (n,-m)!. The pairs have conjugate interpretations as trees, ignoring signs, which Callan and Lang have noted in several of the OEIS entries above. Also note unsigned (n,-2)! is the diagonal of A001498 and (n,+2)!, the first subdiagonal.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..375
Programs
-
Magma
[Round((-3)^n*Gamma(n+2/3)/Gamma(2/3)): n in [0..20]]; // G. C. Greubel, Mar 31 2019
-
Mathematica
Table[(-3)^n*Pochhammer[2/3, n], {n,0,20}] (* G. C. Greubel, Mar 31 2019 *) -
PARI
vector(20, n, n--; round((-3)^n*gamma(n+2/3)/gamma(2/3))) \\ G. C. Greubel, Mar 31 2019
-
Sage
[(-3)^n*rising_factorial(2/3,n) for n in (0..20)] # G. C. Greubel, Mar 31 2019
Formula
a(n) = b(0)*b(1)...b(n) where b = (1,-2,-5,-8,-11,...) .
a(n) = 3^(n+1)*Sum_{k=1..n+1} stirling1(n+1,k)/3^k. - Vladimir Kruchinin, Jul 02 2011
G.f.: (1/Q(0)-1)/x where Q(k) = 1 + x*(3*k-1)/( 1 + x*(3*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 22 2013
G.f.: G(0)/(2*x) - 1/x, where G(k) = 1 + 1/(1 - x*(3*k-1)/(x*(3*k-1) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 06 2013
From G. C. Greubel, Mar 31 2019: (Start)
G.f.: Hypergeometric2F0(1,2/3; -; -3*x).
E.g.f.: (1+3*x)^(-2/3).
a(n) = (-3)^n*Pochhammer(2/3, n) = (-3)^n*(Gamma(n+2/3)/Gamma(2/3)). (End)
D-finite with recurrence: a(n) +(3*n-1)*a(n-1)=0. - R. J. Mathar, Jan 20 2020
Extensions
Terms a(11) onward added by G. C. Greubel, Mar 31 2019
A368791 a(n) = A008544(n) * Sum_{k=0..n} 1/A008544(k).
1, 3, 16, 129, 1420, 19881, 337978, 6759561, 155469904, 4042217505, 117224307646, 3751177844673, 131291224563556, 4989066533415129, 204551727870020290, 9000276026280892761, 423012973235201959768, 21150648661760097988401, 1120984379073285193385254
Offset: 0
Programs
-
PARI
a008544(n) = prod(k=1, n, 3*k-1); a(n) = a008544(n)*sum(k=0, n, 1/a008544(k));
Formula
a(n) = (3*n-1) * a(n-1) + 1.
A000165 Double factorial of even numbers: (2n)!! = 2^n*n!.
1, 2, 8, 48, 384, 3840, 46080, 645120, 10321920, 185794560, 3715891200, 81749606400, 1961990553600, 51011754393600, 1428329123020800, 42849873690624000, 1371195958099968000, 46620662575398912000, 1678343852714360832000, 63777066403145711616000
Offset: 0
Comments
a(n) is also the size of the automorphism group of the graph (edge graph) of the n-dimensional hypercube and also of the geometric automorphism group of the hypercube (the two groups are isomorphic). This group is an extension of an elementary Abelian group (C_2)^n by S_n. (C_2 is the cyclic group with two elements and S_n is the symmetric group.) - Avi Peretz (njk(AT)netvision.net.il), Feb 21 2001
Then a(n) appears in the power series: sqrt(1+sin(y)) = Sum_{n>=0} (-1)^floor(n/2)*y^(n)/a(n) and sqrt((1+cos(y))/2) = Sum_{n>=0} (-1)^n*y^(2n)/a(2n). - Benoit Cloitre, Feb 02 2002
Number of n X n monomial matrices with entries 0, +-1.
Also number of linear signed orders.
Define a "downgrade" to be the permutation d which places the items of a permutation p in descending order. This note concerns those permutations that are equal to their double-downgrades. The number of permutations of order 2n having this property are equinumerous with those of order 2n+1. a(n) = number of double-downgrading permutations of order 2n and 2n+1. - Eugene McDonnell (eemcd(AT)mac.com), Oct 27 2003
a(n) = (Integral_{x=0..Pi/2} cos(x)^(2*n+1) dx) where the denominators are b(n) = (2*n)!/(n!*2^n). - Al Hakanson (hawkuu(AT)excite.com), Mar 02 2004
1 + (1/2)x - (1/8)x^2 - (1/48)x^3 + (1/384)x^4 + ... = sqrt(1+sin(x)).
a(n)*(-1)^n = coefficient of the leading term of the (n+1)-th derivative of arctan(x), see Hildebrand link. - Reinhard Zumkeller, Jan 14 2006
a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is j for iDavid Callan, Sep 25 2006
a(n) is the number of increasing plane trees with n+1 edges. (In a plane tree, each subtree of the root is an ordered tree but the subtrees of the root may be cyclically rotated.) Increasing means the vertices are labeled 0,1,2,...,n+1 and each child has a greater label than its parent. Cf. A001147 for increasing ordered trees, A000142 for increasing unordered trees and A000111 for increasing 0-1-2 trees. - David Callan, Dec 22 2006
Hamed Hatami and Pooya Hatami prove that this is an upper bound on the cardinality of any minimal dominating set in C_{2n+1}^n, the Cartesian product of n copies of the cycle of size 2n+1, where 2n+1 is a prime. - Jonathan Vos Post, Jan 03 2007
This sequence and (1,-2,0,0,0,0,...) form a reciprocal pair under the list partition transform and associated operations described in A133314. - Tom Copeland, Oct 29 2007
a(n) = number of permutations of the multiset {1,1,2,2,...,n,n,n+1,n+1} such that between the two occurrences of i, there is exactly one entry >i, for i=1,2,...,n. Example: a(2) = 8 counts 121323, 131232, 213123, 231213, 232131, 312132, 321312, 323121. Proof: There is always exactly one entry between the two 1s (when n>=1). Given a permutation p in A(n) (counted by a(n)), record the position i of the first 1, then delete both 1s and subtract 1 from every entry to get a permutation q in A(n-1). The mapping p -> (i,q) is a bijection from A(n) to the Cartesian product [1,2n] X A(n-1). - David Callan, Nov 29 2007
Row sums of A028338. - Paul Barry, Feb 07 2009
a(n) is the number of ways to seat n married couples in a row so that everyone is next to their spouse. Compare A007060. - Geoffrey Critzer, Mar 29 2009
From Gary W. Adamson, Apr 21 2009: (Start)
Equals (-1)^n * (1, 1, 2, 8, 48, ...) dot (1, -3, 5, -7, 9, ...).
Example: a(4) = 384 = (1, 1, 2, 8, 48) dot (1, -3, 5, -7, 9) = (1, -3, 10, -56, 432). (End)
exp(x/2) = Sum_{n>=0} x^n/a(n). - Jaume Oliver Lafont, Sep 07 2009
Assuming n starts at 0, a(n) appears to be the number of Gray codes on n bits. It certainly is the number of Gray codes on n bits isomorphic to the canonical one. Proof: There are 2^n different starting positions for each code. Also, each code has a particular pattern of bit positions that are flipped (for instance, 1 2 1 3 1 2 1 for n=3), and these bit position patterns can be permuted in n! ways. - D. J. Schreffler (ds1404(AT)txstate.edu), Jul 18 2010
E.g.f. of 0,1,2,8,... is x/(1-2x/(2-2x/(3-8x/(4-8x/(5-18x/(6-18x/(7-... (continued fraction). - Paul Barry, Jan 17 2011
Number of increasing 2-colored trees with choice of two colors for each edge. In general, if we replace 2 with k we get the number of increasing k-colored trees. For example, for k=3 we get the triple factorial numbers. - Wenjin Woan, May 31 2011
a(n) = row sums of triangle A193229. - Gary W. Adamson, Jul 18 2011
Also the number of permutations of 2n (or of 2n+1) that are equal to their reverse-complements. (See the Egge reference.) Note that the double-downgrade described in the preceding comment (McDonnell) is equivalent to the reverse-complement. - Justin M. Troyka, Aug 11 2011
The e.g.f. can be used to form a generator, [1/(1-2x)] d/dx, for A000108, so a(n) can be applied to A145271 to generate the Catalan numbers. - Tom Copeland, Oct 01 2011
The e.g.f. of 1/a(n) is BesselI(0,sqrt(2*x)). See Abramowitz-Stegun (reference and link under A008277), p. 375, 9.6.10. - Wolfdieter Lang, Jan 09 2012
a(n) = order of the largest imprimitive group of degree 2n with n systems of imprimitivity (see [Miller], p. 203). - L. Edson Jeffery, Feb 05 2012
Row sums of triangle A208057. - Gary W. Adamson, Feb 22 2012
a(n) is the number of ways to designate a subset of elements in each n-permutation. a(n) = A000142(n) + A001563(n) + A001804(n) + A001805(n) + A001806(n) + A001807(n) + A035038(n) * n!. - Geoffrey Critzer, Nov 08 2012
For n>1, a(n) is the order of the Coxeter groups (also called Weyl groups) of types B_n and C_n. - Tom Edgar, Nov 05 2013
For m>0, k*a(m-1) is the m-th cumulant of the chi-squared probability distribution for k degrees of freedom. - Stanislav Sykora, Jun 27 2014
a(n) with 0 prepended is the binomial transform of A120765. - Vladimir Reshetnikov, Oct 28 2015
Exponential self-convolution of A001147. - Vladimir Reshetnikov, Oct 08 2016
Also the order of the automorphism group of the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017
a(n) is the order of the group O_n(Z) = {A in M_n(Z): A*A^T = I_n}, the group of n X n orthogonal matrices over the integers. - Jianing Song, Mar 29 2021
a(n) is the number of ways to tile a (3n,3n)-benzel or a (3n+1,3n+2)-benzel using left stones and two kinds of bones; see Defant et al., below. - James Propp, Jul 22 2023
a(n) is the number of labeled histories for a labeled topology with the modified lodgepole shape and n+1 cherry nodes. - Noah A Rosenberg, Jan 16 2025
Examples
The following permutations and their reversals are all of the permutations of order 5 having the double-downgrade property: 0 1 2 3 4 0 3 2 1 4 1 0 2 4 3 1 4 2 0 3 G.f. = 1 + 2*x + 8*x^2 + 48*x^3 + 384*x^4 + 3840*x^5 + 46080*x^6 + 645120*x^7 + ...
References
- 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).
Links
- T. D. Noe, Table of n, a(n) for n = 0..100
- Paul Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6.
- Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.
- Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Combinatorial Identities Associated with a Multidimensional Polynomial Sequence, J. Int. Seq., Vol. 21 (2018), Article 18.7.4.
- P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
- CombOS - Combinatorial Object Server, Generate colored permutations
- R. Coquereaux and J.-B. Zuber, Maps, immersions and permutations, arXiv preprint arXiv:1507.03163 [math.CO], 2015.
- Colin Defant, Rupert Li, James Propp, and Benjamin Young, Tilings of Benzels via the Abacus Bijection, arXiv preprint, arXiv:2209.05717 [math.CO], 2022.
- Eric S. Egge, Restricted symmetric permutations, Ann. Combin., 11 (2007), 405-434.
- Peter C. Fishburn, Signed Orders, Choice Probabilities and Linear Polytopes, Journal of Mathematical Psychology, Volume 45, Issue 1, (2001), pp. 53-80.
- Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
- G. Gordon, The answer is 2^n*n! What is the question?, Amer. Math. Monthly, 106 (1999), 636-645.
- Guo-Niu Han, Enumeration of Standard Puzzles
- Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]
- Hamed Hatami and Pooya Hatami, Perfect dominating sets in the Cartesian products of prime cycles, arXiv:math/0701018 [math.CO], 2006-2009.
- Jason D. Hildebrand, Differentiating Arctan(x)
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 136
- E. Lappo and N. A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
- L. C. Larson, The number of essentially different nonattacking rook arrangements, J. Recreat. Math., 7 (No. 3, 1974), circa pages 180-181. [Annotated scan of pages 180 and 181 only]
- E. Lucas, Théorie des nombres (annotated scans of a few selected pages)
- Eugene McDonnell, Magic Squares and Permutations, APL Quote Quad 7.3 (Fall 1976).
- B. E. Meserve, Double Factorials, American Mathematical Monthly, 55 (1948), 425-426.
- G. A. Miller, Groups formed by special matrices, Bull. Amer. Math. Soc. 24 (1918), 203-206.
- R. Ondrejka, Tables of double factorials, Math. Comp., 24 (1970), 231.
- Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
- Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
- R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
- M. Z. Spivey and L. L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
- Eric Weisstein's World of Mathematics, Double Factorial
- Eric Weisstein's World of Mathematics, Graph Automorphism
- Eric Weisstein's World of Mathematics, Ladder Rung Graph
- Index to divisibility sequences
- Index entries for sequences related to factorial numbers
Programs
-
Haskell
a000165 n = product [2, 4 .. 2 * n] -- Reinhard Zumkeller, Mar 28 2015
-
Magma
[2^n*Factorial(n): n in [0..35]]; // Vincenzo Librandi, Apr 22 2011
-
Magma
I:=[2,8]; [1] cat [n le 2 select I[n] else (3*n-1)*Self(n-1)-2*(n-1)^2*Self(n-2): n in [1..35] ]; // Vincenzo Librandi, Feb 19 2015
-
Maple
A000165 := proc(n) option remember; if n <= 1 then 1 else n*A000165(n-2); fi; end; ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 0)}, labelled]: seq(combstruct[count](ZL, size=n), n=0..17); # Zerinvary Lajos, Mar 26 2008 G(x):=(1-2*x)^(-1): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..17); # Zerinvary Lajos, Apr 03 2009 A000165 := proc(n) doublefactorial(2*n) ; end proc; seq(A000165(n),n=0..10) ; # R. J. Mathar, Oct 20 2009
-
Mathematica
Table[(2 n)!!, {n, 30}] (* Vladimir Joseph Stephan Orlovsky, Dec 13 2008 *) (2 Range[0, 30])!! (* Harvey P. Dale, Jan 23 2015 *) RecurrenceTable[{a[n] == 2 n*a[n-1], a[0] == 1}, a, {n,0,30}] (* Ray Chandler, Jul 30 2015 *) -
PARI
a(n)=n!<
Charles R Greathouse IV, Feb 11 2011 -
PARI
{a(n) = prod( k=1, n, 2*k)}; /* Michael Somos, Jan 04 2013 */ -
Python
from math import factorial def A000165(n): return factorial(n)<
Chai Wah Wu, Jan 24 2023 -
SageMath
[2^n*factorial(n) for n in range(31)] # G. C. Greubel, Jul 21 2024
Formula
E.g.f.: 1/(1-2*x).
a(n) = A001044(n)/A000142(n)*A000079(n) = Product_{i=0..n-1} (2*i+2) = 2^n*Pochhammer(1,n). - Daniel Dockery (peritus(AT)gmail.com), Jun 13 2003
D-finite with recurrence a(n) = 2*n * a(n-1), n>0, a(0)=1. - Paul Barry, Aug 26 2004
This is the binomial mean transform of A001907. See Spivey and Steil (2006). - Michael Z. Spivey (mspivey(AT)ups.edu), Feb 26 2006
a(n) = Integral_{x>=0} x^n*exp(-x/2)/2 dx. - Paul Barry, Jan 28 2008
G.f.: 1/(1-2x/(1-2x/(1-4x/(1-4x/(1-6x/(1-6x/(1-.... (continued fraction). - Paul Barry, Feb 07 2009
a(n) = A006882(2*n). - R. J. Mathar, Oct 20 2009
From Gary W. Adamson, Jul 18 2011: (Start)
a(n) = upper left term in M^n, M = a production matrix (twice Pascal's triangle deleting the first "2", with the rest zeros; cf. A028326):
2, 2, 0, 0, 0, 0, ...
2, 4, 2, 0, 0, 0, ...
2, 6, 6, 2, 0, 0, ...
2, 8, 12, 8, 2, 0, ...
2, 10, 20, 20, 10, 2, ...
... (End)
From Sergei N. Gladkovskii, Apr 11 2013, May 01 2013, May 24 2013, Sep 30 2013, Oct 27 2013: (Start)
Continued fractions:
G.f.: 1 + x*(Q(0) - 1)/(x+1) where Q(k) = 1 + (2*k+2)/(1-x/(x+1/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + 2*k*x - 2*x*(k+1)/Q(k+1).
G.f.: G(0)/2 where G(k) = 1 + 1/(1 - x*(2*k+2)/(x*(2*k+2) + 1/G(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 - x*(4*k+2) - 4*x^2*(k+1)^2/Q(k+1).
G.f.: R(0) where R(k) = 1 - x*(2*k+2)/(x*(2*k+2)-1/(1-x*(2*k+2)/(x*(2*k+2) -1/R(k+1)))). (End)
a(n) = (2n-2)*a(n-2) + (2n-1)*a(n-1), n>1. - Ivan N. Ianakiev, Aug 06 2013
From Peter Bala, Feb 18 2015: (Start)
Recurrence equation: a(n) = (3*n - 1)*a(n-1) - 2*(n - 1)^2*a(n-2) with a(1) = 2 and a(2) = 8.
The sequence b(n) = A068102(n) also satisfies this second-order recurrence. This leads to the generalized continued fraction expansion lim_{n -> oo} b(n)/a(n) = log(2) = 1/(2 - 2/(5 - 8/(8 - 18/(11 - ... - 2*(n - 1)^2/((3*n - 1) - ... ))))). (End)
From Amiram Eldar, Jun 25 2020: (Start)
Sum_{n>=0} 1/a(n) = sqrt(e) (A019774).
Sum_{n>=0} (-1)^n/a(n) = 1/sqrt(e) (A092605). (End)
Limit_{n->oo} a(n)^4 / (n * A134372(n)) = Pi. - Daniel Suteu, Apr 09 2022
a(n) = 1/([x^n] hypergeom([1], [1], x/2)). - Peter Luschny, Sep 13 2024
a(n) = Sum_{k=0..n} k!*(n-k)!*binomial(n,k)^2. - Ridouane Oudra, Jul 13 2025
A016789 a(n) = 3*n + 2.
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, 101, 104, 107, 110, 113, 116, 119, 122, 125, 128, 131, 134, 137, 140, 143, 146, 149, 152, 155, 158, 161, 164, 167, 170, 173, 176, 179
Offset: 0
Comments
Except for 1, n such that Sum_{k=1..n} (k mod 3)*binomial(n,k) is a power of 2. - Benoit Cloitre, Oct 17 2002
The sequence 0,0,2,0,0,5,0,0,8,... has a(n) = n*(1 + cos(2*Pi*n/3 + Pi/3) - sqrt(3)*sin(2*Pi*n + Pi/3))/3 and o.g.f. x^2(2+x^3)/(1-x^3)^2. - Paul Barry, Jan 28 2004 [Artur Jasinski, Dec 11 2007, remarks that this should read (3*n + 2)*(1 + cos(2*Pi*(3*n + 2)/3 + Pi/3) - sqrt(3)*sin(2*Pi*(3*n + 2)/3 + Pi/3))/3.]
Except for 2, exponents e such that x^e + x + 1 is reducible. - N. J. A. Sloane, Jul 19 2005
The trajectory of these numbers under iteration of sum of cubes of digits eventually turns out to be 371 or 407 (47 is the first of the second kind). - Avik Roy (avik_3.1416(AT)yahoo.co.in), Jan 19 2009
a(n) is the set of numbers congruent to {2,5,8} mod 9. - Gary Detlefs, Mar 07 2010
It appears that a(n) is the set of all values of y such that y^3 = k*n + 2 for integer k. - Gary Detlefs, Mar 08 2010
These numbers do not occur in A000217 (triangular numbers). - Arkadiusz Wesolowski, Jan 08 2012
A089911(2*a(n)) = 9. - Reinhard Zumkeller, Jul 05 2013
Also indices of even Bell numbers (A000110). - Enrique Pérez Herrero, Sep 10 2013
Central terms of the triangle A108872. - Reinhard Zumkeller, Oct 01 2014
A092942(a(n)) = 1 for n > 0. - Reinhard Zumkeller, Dec 13 2014
a(n-1), n >= 1, is also the complex dimension of the manifold E(S), the set of all second-order irreducible Fuchsian differential equations defined on P^1 = C U {oo}, having singular points at most in S = {a_1, ..., a_n, a_{n+1} = oo}, a subset of P^1. See the Iwasaki et al. reference, Proposition 2.1.3., p. 149. - Wolfdieter Lang, Apr 22 2016
Except for 2, exponents for which 1 + x^(n-1) + x^n is reducible. - Ron Knott, Sep 16 2016
The reciprocal sum of 8 distinct items from this sequence can be made equal to 1, with these terms: 2, 5, 8, 14, 20, 35, 41, 1640. - Jinyuan Wang, Nov 16 2018
There are no positive integers x, y, z such that 1/a(x) = 1/a(y) + 1/a(z). - Jinyuan Wang, Dec 31 2018
As a set of positive integers, it is the set sum S + S where S is the set of numbers in A016777. - Michael Somos, May 27 2019
Prepended with {1}, these are the denominators of the elements of the 3x+1 semigroup, the numerators being A005408 prepended with {2}. See Applegate and Lagarias link for more information. - Paolo Xausa, Nov 20 2021
This is also the maximum number of moves starting with n + 1 dots in the game of Sprouts. - Douglas Boffey, Aug 01 2022 [See the Wikipedia link. - Wolfdieter Lang, Sep 29 2022]
a(n-2) is the maximum sum of the span (or L(2,1)-labeling number) of a graph of order n and its complement. The extremal graphs are stars and their complements. For example, K_{1,2} has span 3, and K_2 has span 2. Thus a(3-1) = 5. - Allan Bickle, Apr 20 2023
Examples
G.f. = 2 + 5*x + 8*x^2 + 11*x^3 + 14*x^4 + 17*x^5 + 20*x^6 + ... - _Michael Somos_, May 27 2019
References
- K. Iwasaki, H. Kimura, S. Shimomura and M. Yoshida, From Gauss to Painlevé, Vieweg, 1991. p. 149.
- Konrad Knopp, Theory and Application of Infinite Series, Dover, p. 269
Links
- G. C. Greubel, Table of n, a(n) for n = 0..10000
- D. Applegate and J. C. Lagarias, The 3x+1 semigroup, Journal of Number Theory, Vol. 177, Issue 1, March 2006, pp. 146-159; see also the arXiv version, arXiv:math/0411140 [math.NT], 2004-2005.
- H. Balakrishnan and N. Deo, Parallel algorithm for radiocoloring a graph, Congr. Numer. 160 (2003), 193-204.
- Allan Bickle, Extremal Decompositions for Nordhaus-Gaddum Theorems, Discrete Math, 346 7 (2023), 113392.
- L. Euler, Observatio de summis divisorum p. 9.
- L. Euler, An observation on the sums of divisors, arXiv:math/0411587 [math.HO], 2004-2009, p. 9.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 937
- L. B. W. Jolley, Summation of Series, Dover, 1961, p. 16
- Tanya Khovanova, Recursive Sequences
- Konrad Knopp, Theorie und Anwendung der unendlichen Reihen, Berlin, J. Springer, 1922. (Original German edition of "Theory and Application of Infinite Series")
- Fabian S. Reid, The Visual Pattern in the Collatz Conjecture and Proof of No Non-Trivial Cycles, arXiv:2105.07955 [math.GM], 2021.
- Luis Manuel Rivera, Integer sequences and k-commuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014-2015.
- Leo Tavares, Illustration: Capped Triangular Frames
- Wikipedia, Sprouts (game)
- Index entries for linear recurrences with constant coefficients, signature (2,-1).
Crossrefs
Programs
-
GAP
List([0..70],n->3*n+2); # Muniru A Asiru, Nov 02 2018
-
Haskell
a016789 = (+ 2) . (* 3) -- Reinhard Zumkeller, Jul 05 2013
-
Magma
[3*n+2: n in [0..80]]; // Vincenzo Librandi, Apr 14 2015
-
Maple
seq(3*n+2, n = 0 .. 50); # Matt C. Anderson, May 18 2017
-
Mathematica
Range[2, 500, 3] (* Vladimir Joseph Stephan Orlovsky, May 26 2011 *) LinearRecurrence[{2,-1},{2,5},70] (* Harvey P. Dale, Aug 11 2021 *)
-
PARI
vector(100,n,3*n-1) \\ Derek Orr, Apr 13 2015
-
Python
for n in range(0,100): print(3*n+2, end=', ') # Stefano Spezia, Nov 21 2018
Formula
G.f.: (2+x)/(1-x)^2.
a(n) = 3 + a(n-1).
a(n) = 1 + A016777(n).
a(n) = A124388(n)/9.
a(n) = A125199(n+1,1). - Reinhard Zumkeller, Nov 24 2006
Sum_{n>=1} (-1)^n/a(n) = (1/3)*(Pi/sqrt(3) - log(2)). - Benoit Cloitre, Apr 05 2002
1/2 - 1/5 + 1/8 - 1/11 + ... = (1/3)*(Pi/sqrt(3) - log 2). [Jolley] - Gary W. Adamson, Dec 16 2006
Sum_{n>=0} 1/(a(2*n)*a(2*n+1)) = (Pi/sqrt(3) - log 2)/9 = 0.12451569... (see A196548). [Jolley p. 48 eq (263)]
a(n) = 2*a(n-1) - a(n-2); a(0)=2, a(1)=5. - Philippe Deléham, Nov 03 2008
a(n) = 6*n - a(n-1) + 1 with a(0)=2. - Vincenzo Librandi, Aug 25 2010
E.g.f.: (2 + 3*x)*exp(x). - G. C. Greubel, Nov 02 2018
a(n) = -A016777(-1-n) for all n in Z. - Michael Somos, May 27 2019
a(n) = A007310(n+1) + (1 - n mod 2). - Walt Rorie-Baety, Sep 13 2021
a(n) = A000096(n+1) - A000217(n-1). See Capped Triangular Frames illustration. - Leo Tavares, Oct 05 2021
A007559 Triple factorial numbers (3*n-2)!!! with leading 1 added.
1, 1, 4, 28, 280, 3640, 58240, 1106560, 24344320, 608608000, 17041024000, 528271744000, 17961239296000, 664565853952000, 26582634158080000, 1143053268797440000, 52580450364682240000, 2576442067869429760000, 133974987529210347520000, 7368624314106569113600000
Offset: 0
Comments
a(n) is the number of increasing quaternary trees on n vertices. (See A001147 for ternary and A000142 for binary trees.) - David Callan, Mar 30 2007
a(n) is the product of the positive integers k <= 3*n that have k modulo 3 = 1. - Peter Luschny, Jun 23 2011
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
Partial products of A016777. - Reinhard Zumkeller, Sep 20 2013
For n > 2, a(n) is a Zumkeller number. - Ivan N. Ianakiev, Jan 28 2020
a(n) is the number of generalized permutations of length n related to the degenerate Eulerian numbers (see arXiv:2007.13205), cf. A336633. - Orli Herscovici, Jul 28 2020
Examples
G.f. = 1 + x + 4*x^2 + 28*x^3 + 280*x^4 + 3640*x^5 + 58240*x^6 + ... a(3) = 28 and a(4) = 280; with top row of M^3 = (28, 117, 108, 27), sum = 280.
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n=0..100
- Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
- P. Codara, O. M. D'Antona and P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers, arXiv preprint arXiv:1308.1700 [cs.DM], 2013.
- S. Goodenough and C. Lavault, On subsets of Riordan subgroups and Heisenberg--Weyl algebra, arXiv preprint arXiv:1404.1894 [cs.DM], 2014.
- S. Goodenough and C. Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16.
- Orli Herscovici, Generalized permutations related to the degenerate Eulerian numbers, arXiv preprint arXiv:2007.13205 [math.CO], 2020.
- Ivan N. Ianakiev, A simple proof that for n > 2, a(n) is a Zumkeller number
- Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
- J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
- M. D. Schmidt, Generalized j-Factorial Functions, Polynomials, and Applications, J. Int. Seq. 13 (2010), 10.6.7, Table 6.3.
Crossrefs
Cf. A107716. - Gary W. Adamson, Oct 22 2009
Cf. A095660. - Gary W. Adamson, Jul 19 2011
a(n) = A286718(n,0), n >= 0.
Row sums of A336633.
Programs
-
GAP
List([0..20], n-> Product([0..n-1], k-> 3*k+1 )); # G. C. Greubel, Aug 20 2019
-
Haskell
a007559 n = a007559_list !! n a007559_list = scanl (*) 1 a016777_list -- Reinhard Zumkeller, Sep 20 2013
-
Magma
b:= func< n | (n lt 2) select n else (3*n-2)*Self(n-1) >; [1] cat [b(n): n in [1..20]]; // G. C. Greubel, Aug 20 2019
-
Maple
A007559 := n -> mul(k, k = select(k-> k mod 3 = 1, [$1 .. 3*n])): seq(A007559(n), n = 0 .. 17); # Peter Luschny, Jun 23 2011 # second Maple program: b:= proc(n) option remember; `if`(n<1, 1, n*b(n-3)) end: a:= n-> b(3*n-2): seq(a(n), n=0..20); # Alois P. Heinz, Dec 18 2024
-
Mathematica
a[ n_] := If[ n < 0, 1 / Product[ k, {k, - 2, 3 n - 1, -3}], Product[ k, {k, 1, 3 n - 2, 3}]]; (* Michael Somos, Oct 14 2011 *) FoldList[Times,1,Range[1,100,3]] (* Harvey P. Dale, Jul 05 2013 *) Range[0, 19]! CoefficientList[Series[((1 - 3 x)^(-1/3)), {x, 0, 19}], x] (* Vincenzo Librandi, Oct 08 2015 *) -
Maxima
a(n):=if n=1 then 1 else (n)!*(sum(m/n*sum(binomial(k,n-m-k)*(-1/3)^(n-m-k)* binomial (k+n-1,n-1),k,1,n-m),m,1,n)+1); /* Vladimir Kruchinin, Aug 09 2010 */
-
PARI
{a(n) = if( n<0, (-1)^n / prod(k=0,-1-n, 3*k + 2), prod(k=0, n-1, 3*k + 1))}; /* Michael Somos, Oct 14 2011 */ -
PARI
my(x='x+O('x^33)); Vec(serlaplace((1-3*x)^(-1/3))) /* Joerg Arndt, Apr 24 2011 */ -
Sage
def A007559(n) : return mul(j for j in range(1,3*n,3)) [A007559(n) for n in (0..17)] # Peter Luschny, May 20 2013
Formula
a(n) = Product_{k=0..n-1} (3*k + 1).
a(n) = (3*n - 2)!!!.
a(n) = A007661(3*n-2).
E.g.f.: (1-3*x)^(-1/3).
a(n) ~ sqrt(2*Pi)/Gamma(1/3)*n^(-1/6)*(3*n/e)^n*(1 - (1/36)/n - ...). - Joe Keane (jgk(AT)jgk.org), Nov 22 2001
a(n) = 3^n*Pochhammer(1/3, n).
a(n) = Sum_{k=0..n} (-3)^(n-k)*A048994(n, k). - Philippe Deléham, Oct 29 2005
a(n) = n!*(1+Sum_{m=1..n} (m/n)*Sum_{k=1..n-m} binomial(k, n-m-k)*(-1/3)^(n-m-k)*binomial(k+n-1, n-1)), n>1. - Vladimir Kruchinin, Aug 09 2010
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = upper left term in M^n, M = a variant of Pascal (1,3) triangle (Cf. A095660); as an infinite square production matrix:
1, 3, 0, 0, 0,...
1, 4, 3, 0, 0,...
1, 5, 7, 3, 0,...
...
a(n+1) = sum of top row terms of M^n. (End)
a(n) = (-2)^n*Sum_{k=0..n} (3/2)^k*s(n+1,n+1-k), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
G.f.: 1/Q(0) where Q(k) = 1 - x*(3*k+1)/( 1 - x*(3*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 21 2013
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(3*k+1)/(x*(3*k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
E.g.f.: E(0)/2, where E(k)= 1 + 1/(1 - x*(3*k+1)/(x*(3*k+1) + (k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
Let D(x) = 1/sqrt(1 - 2*x) be the e.g.f. for the sequence of double factorial numbers A001147. Then the e.g.f. A(x) for the triple factorial numbers satisfies D( Integral_{t=0..x} A(t) dt ) = A(x). Cf. A007696 and A008548. - Peter Bala, Jan 02 2015
O.g.f.: hypergeom([1, 1/3], [], 3*x). - Peter Luschny, Oct 08 2015
a(n) = 3^n * Gamma(n + 1/3)/Gamma(1/3). - Artur Jasinski, Aug 23 2016
a(n) = sigma[3,1]^{(n)}n, n >= 0, with the elementary symmetric function of degree n in the n numbers 1, 4, 7, ..., 1+3*(n-1), with sigma[3,1]^{(n)}_0 := 1. See the first formula. - _Wolfdieter Lang, May 29 2017
a(n) = (-1)^n / A008544(n), 0 = a(n)*(+3*a(n+1) -a(n+2)) +a(n+1)*a(n+1) for all n in Z. - Michael Somos, Sep 30 2018
D-finite with recurrence: a(n) +(-3*n+2)*a(n-1)=0, n>=1. - R. J. Mathar, Feb 14 2020
Sum_{n>=1} 1/a(n) = (e/9)^(1/3) * (Gamma(1/3) - Gamma(1/3, 1/3)). - Amiram Eldar, Jun 29 2020
Extensions
Better description from Wolfdieter Lang
A132393 Triangle of unsigned Stirling numbers of the first kind (see A048994), read by rows, T(n,k) for 0 <= k <= n.
1, 0, 1, 0, 1, 1, 0, 2, 3, 1, 0, 6, 11, 6, 1, 0, 24, 50, 35, 10, 1, 0, 120, 274, 225, 85, 15, 1, 0, 720, 1764, 1624, 735, 175, 21, 1, 0, 5040, 13068, 13132, 6769, 1960, 322, 28, 1, 0, 40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1, 0, 362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1
Offset: 0
Comments
Another name: Triangle of signless Stirling numbers of the first kind.
Triangle T(n,k), 0<=k<=n, read by rows given by [0,1,1,2,2,3,3,4,4,5,5,...] DELTA [1,0,1,0,1,0,1,0,1,...] where DELTA is the operator defined in A084938.
Row sums are the factorial numbers. - Roger L. Bagula, Apr 18 2008
Exponential Riordan array [1/(1-x), log(1/(1-x))]. - Ralf Stephan, Feb 07 2014
Also the Bell transform of the factorial numbers (A000142). For the definition of the Bell transform see A264428 and for cross-references A265606. - Peter Luschny, Dec 31 2015
This is the lower triagonal Sheffer matrix of the associated or Jabotinsky type |S1| = (1, -log(1-x)) (see the W. Lang link under A006232 for the notation and references). This implies the e.g.f.s given below. |S1| is the transition matrix from the monomial basis {x^n} to the rising factorial basis {risefac(x,n)}, n >= 0. - Wolfdieter Lang, Feb 21 2017
T(n, k), for n >= k >= 1, is also the total volume of the n-k dimensional cell (polytope) built from the n-k orthogonal vectors of pairwise different lengths chosen from the set {1, 2, ..., n-1}. See the elementary symmetric function formula for T(n, k) and an example below. - Wolfdieter Lang, May 28 2017
From Wolfdieter Lang, Jul 20 2017: (Start)
The compositional inverse w.r.t. x of y = y(t;x) = x*(1 - t(-log(1-x)/x)) = x + t*log(1-x) is x = x(t;y) = ED(y,t) := Sum_{d>=0} D(d,t)*y^(d+1)/(d+1)!, the e.g.f. of the o.g.f.s D(d,t) = Sum_{m>=0} T(d+m, m)*t^m of the diagonal sequences of the present triangle. See the P. Bala link for a proof (there d = n-1, n >= 1, is the label for the diagonals).
This inversion gives D(d,t) = P(d, t)/(1-t)^(2*d+1), with the numerator polynomials P(d, t) = Sum_{m=0..d} A288874(d, m)*t^m. See an example below. See also the P. Bala formula in A112007. (End)
For n > 0, T(n,k) is the number of permutations of the integers from 1 to n which have k visible digits when viewed from a specific end, in the sense that a higher value hides a lower one in a subsequent position. - Ian Duff, Jul 12 2019
Examples
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 3, 1;
0, 6, 11, 6, 1;
0, 24, 50, 35, 10, 1;
0, 120, 274, 225, 85, 15, 1;
0, 720, 1764, 1624, 735, 175, 21, 1;
0, 5040, 13068, 13132, 6769, 1960, 322, 28, 1;
...
---------------------------------------------------
Production matrix is
0, 1
0, 1, 1
0, 1, 2, 1
0, 1, 3, 3, 1
0, 1, 4, 6, 4, 1
0, 1, 5, 10, 10, 5, 1
0, 1, 6, 15, 20, 15, 6, 1
0, 1, 7, 21, 35, 35, 21, 7, 1
...
From _Wolfdieter Lang_, May 09 2017: (Start)
Three term recurrence: 50 = T(5, 2) = 1*6 + (5-1)*11 = 50.
Recurrence from the Sheffer a-sequence [1, 1/2, 1/6, 0, ...]: 50 = T(5, 2) = (5/2)*(binomial(1, 1)*1*6 + binomial(2, 1)*(1/2)*11 + binomial(3, 1)*(1/6)*6 + 0) = 50. The vanishing z-sequence produces the k=0 column from T(0, 0) = 1. (End)
Elementary symmetric function T(4, 2) = sigma^{(3)}_2 = 1*2 + 1*3 + 2*3 = 11. Here the cells (polytopes) are 3 rectangles with total area 11. - _Wolfdieter Lang_, May 28 2017
O.g.f.s of diagonals: d=2 (third diagonal) [0, 6, 50, ...] has D(2,t) = P(2, t)/(1-t)^5, with P(2, t) = 2 + t, the n = 2 row of A288874. - _Wolfdieter Lang_, Jul 20 2017
Boas-Buck recurrence for column k = 2 and n = 5: T(5, 2) = (5!*2/3)*((3/8)*T(2,2)/2! + (5/12)*T(3,2)/3! + (1/2)*T(4,2)/4!) = (5!*2/3)*(3/16 + (5/12)*3/3! + (1/2)*11/4!) = 50. The beta sequence begins: {1/2, 5/12, 3/8, ...}. - _Wolfdieter Lang_, Aug 11 2017
References
- Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 31, 187, 441, 996.
- R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., Table 259, p. 259.
- Steve Roman, The Umbral Calculus, Dover Publications, New York (1984), pp. 149-150
Links
- Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
- Roland Bacher and P. De La Harpe, Conjugacy growth series of some infinitely generated groups, hal-01285685v2, 2016.
- Eli Bagno and David Garber, Combinatorics of q,r-analogues of Stirling numbers of type B, arXiv:2401.08365 [math.CO], 2024. See page 5.
- Peter Bala, Diagonals of triangles with generating function exp(t*F(x)).
- J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
- Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, Preprint, 2016.
- Jean-Luc Baril and Sergey Kirgizov, Transformation à la Foata for special kinds of descents and excedances, arXiv:2101.01928 [math.CO], 2021.
- Jean-Luc Baril and José L. Ramírez, Some distributions in increasing and flattened permutations, arXiv:2410.15434 [math.CO], 2024. See p. 9.
- Ricky X. F. Chen, A Note on the Generating Function for the Stirling Numbers of the First Kind, Journal of Integer Sequences, 18 (2015), #15.3.8.
- Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See p. 5.
- FindStat - Combinatorial Statistic Finder, The number of saliances of a permutation, The number of cycles in the cycle decomposition of a permutation.
- Bill Gosper, Colored illustrations of triangle of Stirling numbers of first kind read mod 2, 3, 4, 5, 6, 7
- W. Steven Gray and Makhin Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 11-11 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.
- John M. Holte, Carries, Combinatorics and an Amazing Matrix, The American Mathematical Monthly, Vol. 104, No. 2 (Feb., 1997), pp. 138-149.
- Tanya Khovanova and J. B. Lewis, Skyscraper Numbers, J. Int. Seq. 16 (2013) #13.7.2.
- Sergey Kitaev and Philip B. Zhang, Distributions of mesh patterns of short lengths, arXiv:1811.07679 [math.CO], 2018.
- Wolfdieter Lang, On Sums of Powers of Arithmetic Progressions, and Generalized Stirling, Eulerian and Bernoulli numbers, arXiv:1707.04451 [math.NT], 2017.
- Shuzhen Lv and Philip B. Zhang, Joint equidistributions of mesh patterns 123 and 321 with symmetric and antipodal shadings, arXiv:2501.00357 [math.CO], 2024. See p. 11.
- Shuzhen Lv and Philip B. Zhang, Joint equidistributions of mesh patterns 123 and 132 with antipodal shadings, arXiv:2506.23148 [math.CO], 2025. See p. 6.
- Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012. - From _N. J. A. Sloane_, Aug 21 2012
- Mathematics Stack Exchange, Symmetric (under the swapping) recursions for Stirling numbers of both kinds, Aug 10 2025.
- Emanuele Munarini, Shifting Property for Riordan, Sheffer and Connection Constants Matrices, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.2.
- Emanuele Munarini, Combinatorial identities involving the central coefficients of a Sheffer matrix, Applicable Analysis and Discrete Mathematics (2019) Vol. 13, 495-517.
- Fedor Petrov, Recursive algorithm for columns of Stirling numbers of the first kind, answer to question on MathOverflow (2025).
- E. G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024. See p. 2.
- Umesh Shankar, Log-concavity of rows of triangular arrays satisfying a certain super-recurrence, arXiv:2508.12467 [math.CO], 2025. See p. 4.
- Xun-Tuan Su, Deng-Yun Yang, and Wei-Wei Zhang, A note on the generalized factorial, Australasian Journal of Combinatorics, Volume 56 (2013), Pages 133-137.
- Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024. See p. 37.
Crossrefs
Programs
-
Haskell
a132393 n k = a132393_tabl !! n !! k a132393_row n = a132393_tabl !! n a132393_tabl = map (map abs) a048994_tabl -- Reinhard Zumkeller, Nov 06 2013
-
Maple
a132393_row := proc(n) local k; seq(coeff(expand(pochhammer (x,n)),x,k),k=0..n) end: # Peter Luschny, Nov 28 2010
-
Mathematica
p[t_] = 1/(1 - t)^x; Table[ ExpandAll[(n!)SeriesCoefficient[ Series[p[t], {t, 0, 30}], n]], {n, 0, 10}]; a = Table[(n!)* CoefficientList[SeriesCoefficient[ Series[p[t], {t, 0, 30}], n], x], {n, 0, 10}]; Flatten[a] (* Roger L. Bagula, Apr 18 2008 *) Flatten[Table[Abs[StirlingS1[n,i]],{n,0,10},{i,0,n}]] (* Harvey P. Dale, Feb 04 2014 *) -
Maxima
create_list(abs(stirling1(n,k)),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */
-
PARI
column(n,k) = my(v1, v2); v1 = vector(n-1, i, 0); v2 = vector(n, i, 0); v2[1] = 1; for(i=1, n-1, v1[i] = (i+k)*(i+k-1)/2*v2[i]; for(j=1, i-1, v1[j] *= (i-j)*(i+k)/(i-j+2)); v2[i+1] = vecsum(v1)/i); v2 \\ generates n first elements of the k-th column starting from the first nonzero element. - Mikhail Kurkov, Mar 05 2025
Formula
T(n,k) = T(n-1,k-1)+(n-1)*T(n-1,k), n,k>=1; T(n,0)=T(0,k); T(0,0)=1.
Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000142(n), A001147(n), A007559(n), A007696(n), A008548(n), A008542(n), A045754(n), A045755(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8 respectively. - Philippe Deléham, Nov 13 2007
Expand 1/(1-t)^x = Sum_{n>=0}p(x,n)*t^n/n!; then the coefficients of the p(x,n) produce the triangle. - Roger L. Bagula, Apr 18 2008
Sum_{k=0..n} T(n,k)*2^k*x^(n-k) = A000142(n+1), A000165(n), A008544(n), A001813(n), A047055(n), A047657(n), A084947(n), A084948(n), A084949(n) for x = 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively. - Philippe Deléham, Sep 18 2008
a(n) = Sum_{k=0..n} T(n,k)*3^k*x^(n-k) = A001710(n+2), A001147(n+1), A032031(n), A008545(n), A047056(n), A011781(n), A144739(n), A144756(n), A144758(n) for x=1,2,3,4,5,6,7,8,9,respectively. - Philippe Deléham, Sep 20 2008
Sum_{k=0..n} T(n,k)*4^k*x^(n-k) = A001715(n+3), A002866(n+1), A007559(n+1), A047053(n), A008546(n), A049308(n), A144827(n), A144828(n), A144829(n) for x=1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Sep 21 2008
Sum_{k=0..n} x^k*T(n,k) = x*(1+x)*(2+x)*...*(n-1+x), n>=1. - Philippe Deléham, Oct 17 2008
From Wolfdieter Lang, Feb 21 2017: (Start)
E.g.f. k-th column: (-log(1 - x))^k, k >= 0.
E.g.f. triangle (see the Apr 18 2008 Baluga comment): exp(-x*log(1-z)).
From Wolfdieter Lang, May 28 2017: (Start)
The row polynomials R(n, x) = Sum_{k=0..n} T(n, k)*x^k, for n >= 0, are R(n, x) = risefac(x,n-1) := Product_{j=0..n-1} x+j, with the empty product for n=0 put to 1. See the Feb 21 2017 comment above. This implies:
T(n, k) = sigma^{(n-1)}_(n-k), for n >= k >= 1, with the elementary symmetric functions sigma^{(n-1)}_m of degree m in the n-1 symbols 1, 2, ..., n-1, with binomial(n-1, m) terms. See an example below.(End)
Boas-Buck type recurrence for column sequence k: T(n, k) = (n!*k/(n - k)) * Sum_{p=k..n-1} beta(n-1-p)*T(p, k)/p!, for n > k >= 0, with input T(k, k) = 1, and beta(k) = A002208(k+1)/A002209(k+1). See a comment and references in A286718. - Wolfdieter Lang, Aug 11 2017
T(n,k) = Sum_{j=k..n} j^(j-k)*binomial(j-1, k-1)*A354795(n,j) for n > 0. - Mélika Tebni, Mar 02 2023
n-th row polynomial: n!*Sum_{k = 0..2*n} (-1)^k*binomial(-x, k)*binomial(-x, 2*n-k) = n!*Sum_{k = 0..2*n} (-1)^k*binomial(1-x, k)*binomial(-x, 2*n-k). - Peter Bala, Mar 31 2024
From Mikhail Kurkov, Mar 05 2025: (Start)
For a general proof of the formulas below via generating functions, see Mathematics Stack Exchange link.
Recursion for the n-th row (independently of other rows): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} binomial(-k,j)*T(n,k+j-1)*(-1)^j for 1 <= k < n with T(n,n) = 1.
Recursion for the k-th column (independently of other columns): T(n,k) = 1/(n-k)*Sum_{j=2..n-k+1} (j-2)!*binomial(n,j)*T(n-j+1,k) for 1 <= k < n with T(n,n) = 1 (see Fedor Petrov link). (End)
Comments