A125791 a(n) = 2^(n*(n-1)*(n-2)/6) for n>=1.

1, 1, 2, 16, 1024, 1048576, 34359738368, 72057594037927936, 19342813113834066795298816, 1329227995784915872903807060280344576, 46768052394588893382517914646921056628989841375232

Offset: 1

Author

Paul D. Hanna, Dec 10 2006

Keywords

• nonn

Comments

a(n) is a tetrahedral power of 2; exponents of 2 in a(n) begin: 0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, ..., n*(n-1)*(n-2)/6, ... (cf. A000292).

Table A125790 is related to partitions into powers of 2, with A002577 in column 1 of A125790; further, column k of A125790 equals row sums of matrix power A078121^k, where triangle A078121 shifts left one column under matrix square.

Also number of distinct instances of the one-in-three monotone 3SAT problem for n variables. - Paul Tarau (paul.tarau(AT)gmail.com), Jan 25 2008

Hankel transform of aerated 2-Catalan numbers (A015083). [Paul Barry, Dec 15 2010]

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..28
• Pakawut Jiradilok, Some Combinatorial Formulas Related to Diagonal Ramsey Numbers, arXiv:2404.02714 [math.CO], 2024. See p. 19.

Crossrefs

Cf. A125790, A078121; A002577, A000292.

Programs

Maple

seq(2^(binomial(n, n-3)), n=1..10); # Zerinvary Lajos, Jun 16 2007 [modified by Georg Fischer, Nov 09 2023]

Mathematica

A125791[n_]:=2^Binomial[n,n-3];Array[A125791,15] (* Paolo Xausa, Nov 05 2023 *)

PARI

a(n)=if(n<1,0,2^(n*(n-1)*(n-2)/6))

PARI

/* As determinant of n X n matrix: */
{a(n)=local(q=2,A=Mat(1), B); for(m=1, n, B=matrix(m, m);
for(i=1, m, for(j=1, i, if(j==i||j==1, B[i, j]=1, B[i, j]=(A^q)[i-1, j-1]); )); A=B);
return(matdet(matrix(n,n,r,c,(A^c)[r,1])))}
for(n=1,15,print1(a(n),", "))

Prolog

% This generates all 3SAT problem instances
test:-test(4).
test(Max):-
between(1,Max,N),
nl,
one_in_three_monotone_3sat(N,Pss),
write(N:Pss),nl,
fail
; nl.
% generates all one-in-three monotone 3SAT problems involving N variables
one_in_three_monotone_3sat(N,Pss):-
ints(1,N,Is),
findall(Xs,ksubset(3,Is,Xs),Xss),
subset_of(Xss,Pss).
% subset generator
subset_of([],[]).
subset_of([X|Xs],Zs):-
subset_of(Xs,Ys),
add_element(X,Ys,Zs).
add_element(_,Ys,Ys).
add_element(X,Ys,[X|Ys]).
% subsets of K elements
ksubset(0,_,[]).
ksubset(K,[X|Xs],[X|Rs]):-K>0,K1 is K-1,ksubset(K1,Xs,Rs).
ksubset(K,[_|Xs],Rs):-K>0,ksubset(K,Xs,Rs).
% list of integers in [From..To]
ints(From,To,Is):-findall(I,between(From,To,I),Is).
% Paul Tarau (paul.tarau(AT)gmail.com), Jan 25 2008

Formula

Determinant of n X n upper left corner submatrix of table A125790.

a(n) = 2^(binomial(n,n-3)). - Zerinvary Lajos, Jun 16 2007, modified to reflect the new offset by Paolo Xausa, Nov 06 2023.

Extensions

Name simplified; determinant formula moved out of name into formula section by Paul D. Hanna, Oct 16 2013

Offset changed to 1 by Paolo Xausa, Nov 06 2023