A115992 -id:A115992 - cp's OEIS frontend

A116732 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0) = a(1) = a(2) = 0, a(3) = 1.

0, 0, 0, 1, 1, 2, 4, 6, 11, 19, 32, 56, 96, 165, 285, 490, 844, 1454, 2503, 4311, 7424, 12784, 22016, 37913, 65289, 112434, 193620, 333430, 574195, 988811, 1702816, 2932392, 5049824, 8696221, 14975621, 25789274, 44411292, 76479966, 131704911, 226806895

Offset: 0

R. K. Guy, Mar 23 2008

This sequence is an example of a "symmetric" quartic recurrence and has some expected divisibility properties.

a(n-3) counts partially ordered partitions of (n-3) into parts 1,2,3 where only the order of the adjacent 1's and 3's are unimportant (see example). - David Neil McGrath, Jul 25 2015

			Partially ordered partitions of (n-3) into parts 1,2,3 where only the order of adjacent 1's and 3's are unimportant. E.g., a(n-3)=a(6)=19. These are (33),(321),(312),(231),(123),(132),(3111),(2211),(1122),(1221),(2112),(2121),(1212),(21111),(12111),(11211),(11121),(11112),(111111). - _David Neil McGrath_, Jul 25 2015
G.f. = x^3 + x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + 19*x^9 + 32*x^10 + ... - _Michael Somos_, Jul 25 2025

Michael De Vlieger, Table of n, a(n) for n = 0..4239
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

Close to A000786 (& A048239), A115992, A115993. Cf. A116201.

LinearRecurrence[{1, 1, 1, -1}, {0, 0, 0, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 02 2012 *)
CoefficientList[Series[x^3/(1-x-x^2-x^3+x^4),{x,0,40}],x] (* Harvey P. Dale, Mar 25 2018 *)

v=[0,0,0,1];for(i=1,40,v=concat(v,v[#v]+v[#v-1]+v[#v-2]-v[#v-3]));v \\ Derek Orr, Aug 27 2015

{a(n) = if(n<0, -a(2-n), polcoeff(x^3/(1 - x - x^2 - x^3 + x^4 + x*O(x^n)), n))} /* Michael Somos, Jul 25 2025 */

G.f.: x^3/(x^4 - x^3 - x^2 - x + 1).

a(n) = -a(2-n) for all n in Z. - Michael Somos, Jul 25 2025

More terms from Max Alekseyev, Mar 23 2008

Name clarified by Michael Somos, Jul 25 2025

A068940 Maximum number of chess queens that can be placed on a 3-dimensional chessboard of order n so that no two queens attack each other.

Original entry on oeis.org

1, 1, 4, 7, 13, 21, 32, 48, 67, 91, 121, 133, 169

Offset: 1

Al Zimmermann, Mar 08 2002

Attacking Queens Programming Contest, Description of the contest.
Eric Weisstein's World of Mathematics, Independence Number.
Al Zimmermann, Attacking Queens Programming Contest, Final report, 2002.
Attacking Queens Programming Contest Database [broken link]

Cf. A068941, A115992, A375103.

A115993 Size |S| of the largest subset S of {0,1}^n whose measure m(S) is <= 2^n, where m is the additive measure defined on each element x of S by m({x}) = 2^k(x), where k(x) is the number of non-null coordinates of x.

Original entry on oeis.org

1, 1, 2, 4, 6, 11, 19, 32, 52, 89, 158, 262, 426, 725, 1287, 2154, 3498, 5931, 10485, 17940, 28965, 48813, 85775, 150923, 241735, 404082, 704598, 1275594, 2031915, 3363953, 5812312, 10438620, 17194101, 28160524, 48156310, 85702564

Offset: 0

Frederic van der Plancke (fplancke(AT)hotmail.com), Feb 10 2006

This is an upper bound to sequence A115992; I do not know whether the two sequences are equal. The proof goes by projecting a queen (see definition of A115992), i.e. an element q of {0,1,2}^n, to the element p(q) of {0,1}^n obtained by substituting 0 for 2. Let also D(q) = { q' in {0,2}^n | if q_i <> 1 then q'_i = q_i }; then |D(q)| = m(p(q)). Two queens q and q' attack each other if and only if either p(q)=p(q') or D(q) and D(q') meet. Conclusion left to the reader.

			a(4)=6=|S| with S containing (0,0,0,0) (of measure 1), plus the 4 permutations of (1,0,0,0) (each of measure 2), plus (1,1,0,0) (of measure 4). Total measure of S is 1+4*2+4=13, while {0,1}^4 itself has measure 16 and all remaining elements of {0,1} have measure >= 4 so none of them can complete S.

Cf. A115992 (of which this is an easier upper bound).

def q3ub(n):
    sum = 0;
    vlm = 2**n; # 2 to the n-th power
    combi = 1; # combinatorial coefficient (n k)
    for k in range(n+1): # for k := 0 to n
        c = min(combi, vlm);
        sum = sum + c;
        vlm = vlm - c;
        vlm = vlm // 2; # integer division, result is truncated
        combi = (combi * (n-k)) // (k+1) # division is exact
    #end for k
    return sum

cp's OEIS Frontend

A116732 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0) = a(1) = a(2) = 0, a(3) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A068940 Maximum number of chess queens that can be placed on a 3-dimensional chessboard of order n so that no two queens attack each other.

Views

Author

Keywords

Links

Crossrefs

A115993 Size |S| of the largest subset S of {0,1}^n whose measure m(S) is <= 2^n, where m is the additive measure defined on each element x of S by m({x}) = 2^k(x), where k(x) is the number of non-null coordinates of x.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python