A126116 -id:A126116 - cp's OEIS frontend

A035607 Table a(d,m) of number of points of L1 norm m in cubic lattice Z^d, read by antidiagonals (d >= 1, m >= 0).

1, 1, 2, 1, 4, 2, 1, 6, 8, 2, 1, 8, 18, 12, 2, 1, 10, 32, 38, 16, 2, 1, 12, 50, 88, 66, 20, 2, 1, 14, 72, 170, 192, 102, 24, 2, 1, 16, 98, 292, 450, 360, 146, 28, 2, 1, 18, 128, 462, 912, 1002, 608, 198, 32, 2, 1, 20, 162, 688, 1666, 2364, 1970, 952, 258, 36, 2, 1, 22, 200, 978, 2816

Offset: 0

N. J. A. Sloane

Table also gives coordination sequences of same lattices.
Rows sums are given by A001333. Rising and falling diagonals are the tribonacci numbers A000213, A001590. - Paul Barry, Feb 13 2003
a(d,m) also gives the number of ways to choose m squares from a 2 X (d-1) grid so that no two squares in the selection are (horizontally or vertically) adjacent. - Jacob A. Siehler, May 13 2006
Mirror image of triangle A113413. - Philippe Deléham, Oct 15 2006
The Ca1 sums lead to A126116 and the Ca2 sums lead to A070550, see A180662 for the definitions of these triangle sums. - Johannes W. Meijer, Aug 05 2011
A035607 is jointly generated with the Delannoy triangle A008288 as an array of coefficients of polynomials v(n,x):  initially, u(1,x) = v(1,x) = 1; for n > 1, u(n,x) = x*u(n-1,x) + v(n-1) and v(n,x) = 2*x*u(n-1,x) + v(n-1,x).  See the Mathematica section. - Clark Kimberling, Mar 05 2012
Also, the polynomial v(n,x) above is x + (x + 1)*f(n-1,x), where f(0,x) = 1. - Clark Kimberling, Oct 24 2014
Rows also give the coefficients of the independence polynomial of the n-ladder graph. - Eric W. Weisstein, Dec 29 2017
Considering both sequences as square arrays (offset by one row), the rows of A035607 are the first differences of the rows of A008288, and the rows of A008288 are the partial sums of the rows of A035607. - Shel Kaphan, Feb 23 2023
Considering only points with nonnegative coordinates, the number of points at L1 distance = m in d dimensions is the same as the number of ways of putting m indistinguishable balls into d distinguishable urns, binomial(m+d-1, d-1). This is one facet of the cross-polytope. Allowing for + and - coordinates, there are binomial(d,i)*2^i facets containing points with up to i nonzero coordinates. Eliminating double counting of points with any coordinates = 0, there are Sum_{i=1..d} (-1)^(d-i)*binomial(m+i-1,i-1)*binomial(d,i)*2^i points at distance m in d dimensions. One may avoid the alternating sum by using binomial(m-1,i-1) to count only the points per facet with exactly i nonzero coordinates, avoiding any double counting, but the result is the same. - Shel Kaphan, Mar 04 2023

			From _Clark Kimberling_, Oct 24 2014: (Start)
As a triangle of coefficients in polynomials v(n,x) in Comments, the first 6 rows are
  1
  1   2
  1   4   2
  1   6   8   2
  1   8  18  12   2
  1  10  32  38  16   2
  ... (End)
From _Shel Kaphan_, Mar 04 2023: (Start)
For d=3, m=4:
There are binomial(3,1)*2^1 = 6 facets (vertices) of binomial(4+1-1,1-1) = 1 point with <= one nonzero coordinate.
There are binomial(3,2)*2^2 = 12 facets (edges) of binomial(4+2-1,2-1) = 5 points with <= two nonzero coordinates.
There are binomial(3,3)*2^3 = 8 facets (faces) of binomial(4+3-1,3-1) = 15 points with <= three nonzero coordinates.
a(3,4) = 8*15 - 12*5 + 6*1 = 120 - 60 + 6 = 66. (End)

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
J. H. Conway and N. J. A. Sloane, Low-Dimensional Lattices VII: Coordination Sequences, Proc. Royal Soc. London, A453 (1997), 2369-2389 (pdf).
M. Janjic and B. Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 13 2013
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 392.
R. J. Mathar, Bivariate Generating Functions for Non-attacking Wazirs on Rectangular Boards (2024), Table 2.
Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
Joan Serra-Sagrista, Enumeration of lattice points in l_1 norm, Inf. Proc. Lett. 76 (1-2) (2000) 39-44.
J. Siehler, Adjacency-free selections from a 2xN grid (Mathematica notebook) [broken link]
Jacob A. Siehler, Selections Without Adjacency on a Rectangular Grid, arXiv:1409.3869 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Ladder Graph

Other versions: A113413, A119800, A122542, A266213.
Cf. A008288, which has g.f. 1/(1-x-x*y-x^2*y).
Cf. A078057 (row sums), A050146 (central terms).
Cf. A050146.

a035607 n k = a035607_tabl !! n !! k
a035607_row n = a035607_tabl !! n
a035607_tabl = map fst $ iterate
   (\(us, vs) -> (vs, zipWith (+) ([0] ++ us ++ [0]) $
                      zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [1, 2])
-- Reinhard Zumkeller, Jul 20 2013

A035607 := proc(d,m) local j: add(binomial(floor((d-1+j)/2),d-m-1)*binomial(d-m-1, floor((d-1-j)/2)),j=0..d-1) end: seq(seq(A035607(d,m),m=0..d-1),d=1..11); # d=dimension, m=norm # Johannes W. Meijer, Aug 05 2011

u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];
v[n_, x_] := 2 x*u[n - 1, x] + v[n - 1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]    (* A008288 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]    (* A035607 *)
(* Clark Kimberling, Mar 09 2012 *)
Reverse /@ CoefficientList[CoefficientList[Series[(1 + x)/(1 - x - x y - x^2 y), {x, 0, 10}], x], y] // Flatten (* Eric W. Weisstein, Dec 29 2017 *)

T(n, k) = if (k==0, 1, sum(i=0, k-1, binomial(n-k,i+1)*binomial(k-1,i)*2^(i+1)));
tabl(nn) = for (n=1, nn, for (k=0, n-1, print1(T(n, k), ", ")); print); \\ as a triangle; Michel Marcus, Feb 27 2018

def A035607_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1))
    return [prec(n, n-k) for k in (0..n-1)]
for n in (1..10): print(A035607_row(n)) # Peter Luschny, Mar 16 2016

From Johannes W. Meijer, Aug 05 2011: (Start)
f(d,m) = Sum_{j=0..d-1} binomial(floor((d-1+j)/2), d-m-1)*binomial(d-m-1, floor((d-1-j)/2)), d >= 1 and 0 <= m <= d-1.
f(d,m) = f(d-1,m-1) + f(d-1,m) + f(d-2,m-1) (d >= 3 and 1 <= m <= d-1) with f(d,0) = 1 (d >= 1) and f(d,d-1) = 2 (d>=2). (End)
From Roger Cuculière, Apr 10 2006: (Start)
The generating function G(x,y) of this double sequence is the sum of a(n,p)*x^n*y^p, n=1..oo, p=0..oo, which is G(x,y) = x*(1+y)/(1-x-y-x*y).
The horizontal generating function H_n(y), which generates the rows of the table: (1, 2, 2, 2, 2, ...), (1, 4, 8, 12, 16, ...), (1, 6, 18, 38, 66, ...), is the sum of a(n,p)*y^p, p=0..oo, for each fixed n. This is H_n(y) = ((1+y)^n)/((1-y)^n).
The vertical generating function V_p(x), which generates the columns of the table: (1, 1, 1, 1, 1, ...), (2, 4, 6, 8, 10, ...), (2, 8, 18, 32, 50, ...), is the sum of a(n,p)*x^n, n=1..oo, for each fixed p. This is V_p(x) = 2*((1+x)^(p-1))/((1-x)^(p+1)) for p >= 1 and V_0(x) = x/(1-x). (End)
G.f.: (1+x)/(1-x-x*y-x^2*y). - Vladeta Jovovic, Apr 02 2002 (But see previous lines!)
T(2*n,n) = A050146(n+1). - Reinhard Zumkeller, Jul 20 2013
Seen as a triangle read by rows: T(n,0) = 1, for n > 1: T(n,n-1) = 2, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-2,k-1), 0 < k < n. - Reinhard Zumkeller, Jul 20 2013
Seen as a triangle T(n,k) with 0 <= k < n read by rows: T(n,0)=1 for n > 0 and T(n,k) = Sum_{i=0..k-1} binomial(n-k,i+1)*binomial(k-1,i)*2^(i+1) for k > 0. - Werner Schulte, Feb 22 2018
With p >= 1 and q >= 0, as a square array a(p,q) = T(p+q-1,q) = 2*p*Hypergeometric2F1[1-p, 1-q, 2, 2] for q >= 1. Consequently, a(p,q) = a(q,p)*p/q. - Shel Kaphan, Feb 14 2023
For n >= 1, T(2*n,n) = A002003(n), T(3*n,2*n) = A103885(n) and T(4*n,3*n) = A333715(n). - Peter Bala, Jun 15 2023

More terms from David W. Wilson

Maple program corrected and information added by Johannes W. Meijer, Aug 05 2011

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

Original entry on oeis.org

1, 2, 2, 3, 6, 10, 15, 24, 40, 65, 104, 168, 273, 442, 714, 1155, 1870, 3026, 4895, 7920, 12816, 20737, 33552, 54288, 87841, 142130, 229970, 372099, 602070, 974170, 1576239, 2550408, 4126648, 6677057, 10803704, 17480760, 28284465, 45765226

Offset: 0

Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002

Shares some properties with Fibonacci sequence.
The sum of any two alternating terms (terms separated by one other term) produces a Fibonacci number (e.g., 2+6=8, 3+10=13, 24+65=89). The product of any two consecutive or alternating Fibonacci terms produces a term from this sequence (e.g., 5*8 = 40, 13*5 = 65, 21*8 = 168).
In Penney's game (see A171861), the number of ways that HTH beats HHH on flip 3,4,5,... - Ed Pegg Jr, Dec 02 2010
The Ca2 sums (see A180662 for the definition of these sums) of triangle A035607 equal the terms of this sequence. - Johannes W. Meijer, Aug 05 2011

			G.f.: 1 + 2*x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 15*x^6 + 24*x^7 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
David Applegate, Marc LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq., Vol. 14 (2011), Article # 11.9.8.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Bisections: A001654, A059929.

Cf. A049853, A290565.

a070550 n = a070550_list !! n
a070550_list = 1 : 2 : 2 : 3 :
   zipWith (+) a070550_list
               (zipWith (+) (tail a070550_list) (drop 3 a070550_list))
-- Reinhard Zumkeller, Aug 06 2011

with(combinat): A070550 := proc(n): fibonacci(floor(n/2)+1) * fibonacci(ceil(n/2)+2) end: seq(A070550(n),n=0..37); # Johannes W. Meijer, Aug 05 2011

LinearRecurrence[{1, 0, 1, 1}, {1, 2, 2, 3}, 40] (* Jean-François Alcover, Jan 27 2018 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,a+b+d}; NestList[nxt,{1,2,2,3},40][[;;,1]] (* Harvey P. Dale, Jul 16 2024 *)

A070550(n) = fibonacci(n\2+1)*fibonacci((n+5)\2) \\ M. F. Hasler, Aug 06 2011

x='x+O('x^100); Vec((1+x)/(1-x-x^3-x^4)) \\ Altug Alkan, Dec 24 2015

a(n) = F(floor(n/2)+1)*F(ceiling(n/2)+2), with F(n) = A000045(n). - Ralf Stephan, Apr 14 2004
G.f.: (1+x)/(1-x-x^3-x^4) = (1+x)/((1+x^2)*(1-x-x^2))
a(n) = A126116(n+4) - F(n+3). - Johannes W. Meijer, Aug 05 2011
a(n) = (1+3*i)/10*(-i)^n + (1-3*i)/10*(i)^n + (2+sqrt(5))/5*((1+sqrt(5))/2)^n + (2-sqrt(5))/5*((1-sqrt(5))/2)^n, where i = sqrt(-1). - Sergei N. Gladkovskii, Jul 16 2013
a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014
Sum_{n>=1} 1/a(n) = A290565. - Amiram Eldar, Feb 17 2021

A206282 a(n) = ( a(n-1) * a(n-3) + a(n-2) ) / a(n-4), a(1) = a(2) = 1, a(3) = -1, a(4) = -4.

Original entry on oeis.org

1, 1, -1, -4, -5, 1, 9, 11, -4, -25, -31, 9, 64, 79, -25, -169, -209, 64, 441, 545, -169, -1156, -1429, 441, 3025, 3739, -1156, -7921, -9791, 3025, 20736, 25631, -7921, -54289, -67105, 20736, 142129, 175681, -54289, -372100, -459941, 142129, 974169, 1204139

Offset: 1

Michael Somos, Feb 05 2012

This satisfies the same recurrence as Dana Scott's sequence A048736.

			G.f. = x + x^2 - x^3 - 4*x^4 - 5*x^5 + x^6 + 9*x^7 + 11*x^8 - 4*x^9 - 25*x^10 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 1..5000
Index entries for linear recurrences with constant coefficients, signature (0,0,-2,0,0,2,0,0,1).

Cf. A000045, A048736, A110034, A110035, A126116.

a206282 n = a206282_list !! (n-1)
a206282_list = 1 : 1 : -1 : -4 :
   zipWith div
     (zipWith (+)
       (zipWith (*) (drop 3 a206282_list)
                    (drop 1 a206282_list))
       (drop 2 a206282_list))
     a206282_list
-- Same program as in A048736, see comment.
-- Reinhard Zumkeller, Feb 08 2012

I:=[1,1,-1,-4]; [n le 4 select I[n] else (Self(n-1)*Self(n-3) + Self(n-2))/Self(n-4): n in [1..30]]; // G. C. Greubel, Aug 12 2018

CoefficientList[Series[x*(1+x)*(1-x^2)*(1+x^3)/(1-2*x^2-2*x^4-2*x^6+x^8 ), {x,0,50}], x] (* or *) RecurrenceTable[{a[n] == ( a[n-1]*a[n-3] + a[n-2] )/a[n-4], a[1] == a[2] == 1, a[3] == -1, a[4] == -4}, a, {n,1,50}] (* G. C. Greubel, Aug 12 2018 *)

{a(n) = my(k = n\3); (-1)^k * if( n%3 == 0, fibonacci( k )^2, n%3 == 1, fibonacci( k+2 )^2, fibonacci( k ) * fibonacci( k+3 ) + fibonacci( k+1 ) * fibonacci( k+2 ))};

x='x+O('x^30); Vec(x*(1+x)*(1-x^2)*(1+x^3)/(1-2*x^2-2*x^4 -2*x^6 +x^8 )) \\ G. C. Greubel, Aug 12 2018

G.f.: x * (1 + x - x^2 - 2*x^3 - 3*x^4 - x^5 - x^6 - x^7) / (1 + 2*x^3 - 2*x^6 - x^9).
a(n) = a(-5 - n) = a(n+2) * a(n-2) - a(n+1) * a(n-1) for all n in Z.
a(3*n) = (-1)^n * F(n)^2, a(3*n + 1) = (-1)^n * F(n + 2)^2 where F = Fibonacci A000045.
a(6*n - 4) = - A110034(2*n), a(6*n - 1) = - A110035(2*n), a(3*n + 2) = (-1)^n * A126116(2*n + 3).

A240836 Numbers n such that n^3 = xyz where 2 <= x <= y <= z , n^3+1 = (x-1)(y+1)(z+1).

Original entry on oeis.org

2, 12, 80, 546, 3740, 25632, 175682, 1204140, 8253296, 56568930, 387729212, 2657535552, 18215019650, 124847601996, 855718194320, 5865179758242, 40200540113372, 275538601035360, 1888569667134146, 12944449068903660, 88722573815191472, 608113567637436642

Offset: 1

Naohiro Nomoto, Apr 12 2014

Also, z/y approx = y/x approx = golden ratio.

			546^3 = 338 * 546 * 882, 546^3 + 1 = 337 * 547 * 883.
25632^3 = 15842 * 25632 * 41472, 25632^3 + 1 = 15841 * 25633 * 41473.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (8,-8,1).

Cf. A000045, A079472, A081016, A110035, A126116.

F:=Fibonacci;; List([1..30], n-> 2*F(2*n)*F(2*n-1) ); # G. C. Greubel, Jul 15 2019

F:=Fibonacci; [2*F(2*n)*F(2*n-1): n in [1..30]]; // G. C. Greubel, Jul 15 2019

with(combinat); A240836:=n->2*fibonacci(2*n)*fibonacci(2*n-1); seq(A240836(n), n=1..30); # Wesley Ivan Hurt, Apr 13 2014

Table[2Fibonacci[2n]Fibonacci[2n-1], {n, 30}] (* Wesley Ivan Hurt, Apr 13 2014 *)

vector(30, n, f=fibonacci; 2*f(2*n)*f(2*n-1)) \\ G. C. Greubel, Jul 15 2019

f=fibonacci; [2*f(2*n)*f(2*n-1) for n in (1..30)] # G. C. Greubel, Jul 15 2019

a(n) = 2*F(2n)*F(2n-1) where F(n) are the Fibonacci numbers (A000045).
G.f.: 2*x*(1-2*x)/((1-x)*(1-7*x+x^2)). - Colin Barker, Apr 13 2014
a(n) = 2 * A081016(n-1). - Wesley Ivan Hurt, Apr 13 2014

More terms from Colin Barker, Apr 13 2014

A307677 a(0) = a(1) = a(2) = a(3) = 1; thereafter a(n) = a(n-1) + a(n-2) + a(n-4).

Original entry on oeis.org

1, 1, 1, 1, 3, 5, 9, 15, 27, 47, 83, 145, 255, 447, 785, 1377, 2417, 4241, 7443, 13061, 22921, 40223, 70587, 123871, 217379, 381473, 669439, 1174783, 2061601, 3617857, 6348897, 11141537, 19552035, 34311429, 60212361, 105665327, 185429723, 325406479, 571048563, 1002120369

Offset: 0

Joseph Damico, Apr 21 2019

A079398, A103609, A003269, A306276, A126116, and A000288 are the other six sequences which have characteristic equations of the form x^4 = ax^3 + bx^2 + cx + 1 in which a, b, and c are equal to either 0 or 1 -- but not all three of them are equal to zero. (Each of those sequences begins with 1,1,1,1.)
A005251 has the same characteristic equation, and each successive term is determined by the same operation, namely, a(n) = a(n-1) + a(n-2) + a(n-4). However, it has different starting values: (0,1,1,1) instead of (1,1,1,1).
The characteristic equation of this sequence is x^4 = x^3 + x^2 + 1. Lim_{n->infinity} a(n+1)/a(n) = 1.754877666...

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,0,1).

Cf. A000288, A003269, A005251, A005314, A079398, A103609, A126116, A306276.

[n le 4 select 1 else Self(n-1) +Self(n-2) +Self(n-4): n in [1..51]]; // G. C. Greubel, Oct 23 2024

LinearRecurrence[{1,1,0,1}, {1,1,1,1}, 51] (* G. C. Greubel, Oct 23 2024 *)

Vec((1 - x^2 - x^3) / ((1 + x)*(1 - 2*x + x^2 - x^3)) + O(x^40)) \\ Colin Barker, Apr 25 2020

@CachedFunction # a = A307677
def a(n): return 1 if n<4 else a(n-1) +a(n-2) +a(n-3)
[a(n) for n in range(51)] # G. C. Greubel, Oct 23 2024

From Colin Barker, Apr 25 2020: (Start)
G.f.: (1 - x^2 - x^3) / ((1 + x)*(1 - 2*x + x^2 - x^3)).
a(n) = a(n-1) + a(n-2) + a(n-4) for n>3. (End)
a(n) = (1/5)*((-1)^n + 2*(2*A005314(n+1) - A005314(n) - 2*A005314(n-1))). - G. C. Greubel, Oct 23 2024

cp's OEIS Frontend

A035607 Table a(d,m) of number of points of L1 norm m in cubic lattice Z^d, read by antidiagonals (d >= 1, m >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

A206282 a(n) = ( a(n-1) * a(n-3) + a(n-2) ) / a(n-4), a(1) = a(2) = 1, a(3) = -1, a(4) = -4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Formula

A240836 Numbers n such that n^3 = x*y*z where 2 <= x <= y <= z , n^3+1 = (x-1)*(y+1)*(z+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A307677 a(0) = a(1) = a(2) = a(3) = 1; thereafter a(n) = a(n-1) + a(n-2) + a(n-4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A240836 Numbers n such that n^3 = xyz where 2 <= x <= y <= z , n^3+1 = (x-1)(y+1)(z+1).