OFFSET
1,3
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.
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.
MAPLE
seq(2^(binomial(n, n-3)), n=1..10); # Zerinvary Lajos, Jun 16 2007 [modified by Georg Fischer, Nov 09 2023]
MATHEMATICA
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Dec 10 2006
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
STATUS
approved