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

%I #37 Apr 10 2024 10:40:38

%S 1,1,2,16,1024,1048576,34359738368,72057594037927936,

%T 19342813113834066795298816,1329227995784915872903807060280344576,

%U 46768052394588893382517914646921056628989841375232

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

%C 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).

%C 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.

%C 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

%C Hankel transform of aerated 2-Catalan numbers (A015083). [_Paul Barry_, Dec 15 2010]

%H Michael De Vlieger, <a href="/A125791/b125791.txt">Table of n, a(n) for n = 1..28</a>

%H Pakawut Jiradilok, <a href="https://arxiv.org/abs/2404.02714">Some Combinatorial Formulas Related to Diagonal Ramsey Numbers</a>, arXiv:2404.02714 [math.CO], 2024. See p. 19.

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

%F a(n) = 2^(binomial(n,n-3)). - _Zerinvary Lajos_, Jun 16 2007, modified to reflect the new offset by _Paolo Xausa_, Nov 06 2023.

%p seq(2^(binomial(n, n-3)), n=1..10); # _Zerinvary Lajos_, Jun 16 2007 [modified by _Georg Fischer_, Nov 09 2023]

%t A125791[n_]:=2^Binomial[n,n-3];Array[A125791,15] (* _Paolo Xausa_, Nov 05 2023 *)

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

%o (PARI) /* As determinant of n X n matrix: */

%o {a(n)=local(q=2,A=Mat(1), B); for(m=1, n, B=matrix(m, m);

%o 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);

%o return(matdet(matrix(n,n,r,c,(A^c)[r,1])))}

%o for(n=1,15,print1(a(n),", "))

%o (Prolog) % This generates all 3SAT problem instances

%o test:-test(4).

%o test(Max):-

%o between(1,Max,N),

%o nl,

%o one_in_three_monotone_3sat(N,Pss),

%o write(N:Pss),nl,

%o fail

%o ; nl.

%o % generates all one-in-three monotone 3SAT problems involving N variables

%o one_in_three_monotone_3sat(N,Pss):-

%o ints(1,N,Is),

%o findall(Xs,ksubset(3,Is,Xs),Xss),

%o subset_of(Xss,Pss).

%o % subset generator

%o subset_of([],[]).

%o subset_of([X|Xs],Zs):-

%o subset_of(Xs,Ys),

%o add_element(X,Ys,Zs).

%o add_element(_,Ys,Ys).

%o add_element(X,Ys,[X|Ys]).

%o % subsets of K elements

%o ksubset(0,_,[]).

%o ksubset(K,[X|Xs],[X|Rs]):-K>0,K1 is K-1,ksubset(K1,Xs,Rs).

%o ksubset(K,[_|Xs],Rs):-K>0,ksubset(K,Xs,Rs).

%o % list of integers in [From..To]

%o ints(From,To,Is):-findall(I,between(From,To,I),Is).

%o % Paul Tarau (paul.tarau(AT)gmail.com), Jan 25 2008

%Y Cf. A125790, A078121; A002577, A000292.

%K nonn

%O 1,3

%A _Paul D. Hanna_, Dec 10 2006

%E Name simplified; determinant formula moved out of name into formula section by _Paul D. Hanna_, Oct 16 2013

%E Offset changed to 1 by _Paolo Xausa_, Nov 06 2023