A000213 -id:A000213 - 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

A122542 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 2, -1, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 2, 4, 1, 0, 2, 8, 6, 1, 0, 2, 12, 18, 8, 1, 0, 2, 16, 38, 32, 10, 1, 0, 2, 20, 66, 88, 50, 12, 1, 0, 2, 24, 102, 192, 170, 72, 14, 1, 0, 2, 28, 146, 360, 450, 292, 98, 16, 1, 0, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1

Offset: 0

Philippe Deléham, Sep 19 2006, May 28 2007

Riordan array (1, x*(1+x)/(1-x)). Rising and falling diagonals are the tribonacci numbers A000213, A001590.

			Triangle begins:
  1;
  0, 1;
  0, 2,  1;
  0, 2,  4,   1;
  0, 2,  8,   6,   1;
  0, 2, 12,  18,   8,    1;
  0, 2, 16,  38,  32,   10,   1;
  0, 2, 20,  66,  88,   50,  12,   1;
  0, 2, 24, 102, 192,  170,  72,  14,   1;
  0, 2, 28, 146, 360,  450, 292,  98,  16,  1;
  0, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1;

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 1.

Other versions: A035607, A113413, A119800, A266213.
Diagonals: A000012, A005843, A001105, A035597 - A035606.
Columns: A000007, A040000, A008575, A005899, A008412-A008416, A008418, A008420, A035706 - A035745.
Sums include: A000007, A001333 (row), A001590 (diagonal), A007483, A057077 (signed row), A078016 (signed diagonal), A086901, A091928, A104934, A122558, A122690.
Cf. A155161, A059283.

a122542 n k = a122542_tabl !! n !! k
a122542_row n = a122542_tabl !! n
a122542_tabl = map fst $ iterate
   (\(us, vs) -> (vs, zipWith (+) ([0] ++ us ++ [0]) $
                      zipWith (+) ([0] ++ vs) (vs ++ [0]))) ([1], [0, 1])
-- Reinhard Zumkeller, Jul 20 2013, Apr 17 2013

function T(n, k) // T = A122542
  if k eq 0 then return 0^n;
  elif k eq n then return 1;
  else return T(n-1,k) + T(n-1,k-1) + T(n-2,k-1);
  end if;
end function;
[T(n, k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 27 2024

CoefficientList[#, y]& /@ CoefficientList[(1-x)/(1 - (1+y)x - y x^2) + O[x]^11, x] // Flatten (* Jean-François Alcover, Sep 09 2018 *)
(* Second program *)
T[n_, k_]:= T[n, k]= If[k==n, 1, If[k==0, 0, T[n-1,k-1] +T[n-1,k] +T[n-2,k- 1] ]]; (* T = A122542 *)
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Oct 27 2024 *)

def A122542_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, k) for k in (0..n)]
for n in (0..10): print(A122542_row(n)) # Peter Luschny, Mar 16 2016

Sum_{k=0..n} x^k*T(n,k) = A000007(n), A001333(n), A104934(n), A122558(n), A122690(n), A091928(n)  for x = 0, 1, 2, 3, 4, 5. - Philippe Deléham, Jan 25 2012
Sum_{k=0..n} 3^(n-k)*T(n,k) = A086901(n).
Sum_{k=0..n} 2^(n-k)*T(n,k) = A007483(n-1), n >= 1. - Philippe Deléham, Oct 08 2006
T(2*n, n) = A123164(n).
T(n, k) = T(n-1,k) + T(n-1,k-1) + T(n-2,k-1), n > 1. - Philippe Deléham, Jan 25 2012
G.f.: (1-x)/(1-(1+y)*x-y*x^2). - Philippe Deléham, Mar 02 2012
From G. C. Greubel, Oct 27 2024: (Start)
Sum_{k=0..n} (-1)^k*T(n, k) = A057077(n).
Sum_{k=0..floor(n/2)} T(n-k, k) = A001590(n+1).
Sum_{k=0..floor(n/2)} (-1)^k*T(n-k, k) = A078016(n). (End)

A166444 a(0) = 0, a(1) = 1 and for n > 1, a(n) = sum of all previous terms.

Original entry on oeis.org

0, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592

Offset: 0

Robert G. Wilson v, Oct 13 2009

Essentially a duplicate of A000079. - N. J. A. Sloane, Oct 15 2009
a(n) is the number of compositions of n into an odd number of parts.
Also 0 together with A011782. - Omar E. Pol, Oct 28 2013
Inverse INVERT transform of A001519. - R. J. Mathar, Dec 08 2022

			G.f. = x + x^2 + 2*x^3 + 4*x^4 + 8*x^5 + 16*x^6 + 32*x^7 + 64*x^8 + 128*x^9 + ...

Indranil Ghosh, Table of n, a(n) for n = 0..3317
Index entries for linear recurrences with constant coefficients, signature (2).

Cf. A000045, A000079, A000213, A000288, A000322, A000383, A001519.
Cf. A011782, A034008, A060455, A123526, A127193, A127194, A127624.
Cf. A131577, A163551.

[n le 1 select n else 2^(n-2): n in [0..40]]; // G. C. Greubel, Jul 27 2024

a:= n-> `if`(n<2, n, 2^(n-2)):
seq(a(n), n=0..40);  # Alois P. Heinz, Jun 02 2021

a[0] = 0; a[1] = 1; a[n_] := a[n] = Plus @@ Array[a, n - 1]; Array[a, 35, 0]

[(2^n +2*int(n==1) -int(n==0))/4 for n in range(41)] # G. C. Greubel, Jul 27 2024

a(n) = A000079(n-1) for n > 0.
O.g.f.: x*(1 - x) / (1 - 2*x) = x / (1 - x / (1 - x)).
a(n) = (1-n) * a(n-1) + 2 * Sum_{k=1..n-1} a(k) * a(n-k) if n>1. - Michael Somos, Jul 23 2011
E.g.f.: (exp(2*x) + 2*x - 1)/4. - Stefano Spezia, Aug 07 2022

A136175 Tribonacci array, T(n,k).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 11, 9, 8, 13, 20, 17, 15, 10, 24, 37, 31, 28, 19, 12, 44, 68, 57, 51, 35, 22, 14, 81, 125, 105, 94, 64, 41, 26, 16, 149, 230, 193, 173, 118, 75, 48, 30, 18, 274, 423, 355, 318, 217, 138, 88, 55, 33, 21, 504, 778, 653, 585, 399, 254, 162, 101, 61, 39, 23

Offset: 1

Clark Kimberling, Dec 18 2007

As an interspersion (and dispersion), the array is, as a sequence, a permutation of the positive integers. Column k consists of the numbers m such that the least summand in the tribonacci representation of m is T(1,k). For example, column 1 consists of numbers with least summand 1. This array arises from tribonacci representations in much the same way that the Wythoff array, A035513, arises from Fibonacci (or Zeckendorf) representations.
From Abel Amene, Jul 29 2012: (Start)
(Row 1) = A000073 (offset=4) a(0)=0, a(1)=0, a(2)=1
(Row 2) = A001590 (offset=5) a(0)=0, a(1)=1, a(2)=0
(Row 3) = A000213 (offset=4) a(0)=1, a(1)=1, a(2)=1
(Row 4) = A214899 (offset=5) a(0)=2, a(1)=1, a(2)=2
(Row 5) = A020992 (offset=6) a(0)=0, a(1)=2, a(2)=1
(Row 6) = A100683 (offset=6) a(0)=-1,a(1)=2, a(2)=2
(Row 7) = A135491 (offset=4) a(0)=2, a(1)=4, a(2)=8
(Row 8) = A214727 (offset=6) a(0)=1, a(1)=1, a(2)=2
(Row 9) = A081172 (offset=8) a(0)=1, a(1)=1, a(2)=0
(column 1) = A003265
(column 2) = A353083
(End) [Corrected and extended by John Keith, May 09 2022]

			Northwest corner:
1  2   4   7   13  24   44   81  149 274 504
3  6   11  20  37  68   125  230 423 778
5  9   17  31  57  105  193  355 653
8  15  28  51  94  173  318  585
10 19  35  64  118 217  399
12 22  41  75  138 254
14 26  48  88  162
16 30  55 101
18 33  61
21 39
23

Cf. A035513, A353083, A353084.

# maximum index in A73 such that A73 <= n.
A73floorIdx := proc(n)
    local k ;
    for k from 3 do
        if A000073(k) = n then
            return k ;
        elif A000073(k) > n then
            return k -1 ;
        end if ;
    end do:
end proc:
# tribonacci expansion coeffs of n
A278038 := proc(n)
    local k,L,nres ;
    k := A73floorIdx(n) ;
    L := [1] ;
    nres := n-A000073(k) ;
    while k >= 4 do
        k := k-1 ;
        if nres >= A000073(k) then
            L := [1,op(L)] ;
            nres := nres-A000073(k) ;
        else
            L := [0,op(L)] ;
        end if ;
    end do:
    return L ;
end proc:
A278038inv := proc(L)
    add( A000073(i+2)*op(i,L),i=1..nops(L)) ;
end proc:
A135175 := proc(n,k)
    option remember ;
    local a,known,prev,nprev,kprev,freb ;
    if n =1 then
        A000073(k+2) ;
    elif k>3 then
        procname(n,k-1)+procname(n,k-2)+procname(n,k-3) ;
    else
        if k = 1 then
            for a from 1 do
                known := false ;
                for nprev from 1 to n-1 do
                    for kprev from 1 do
                        if procname(nprev,kprev) > a then
                            break ;
                        elif procname(nprev,kprev) = a then
                            known := true ;
                        end if;
                    end do:
                end do:
                if not known then
                    return a ;
                end if;
            end do:
        else
            prev := procname(n,k-1) ;
            freb := A278038(prev) ;
            return A278038inv([0,op(freb)]) ;
        end if;
    end if;
end proc:
seq(seq(A135175(n,d-n),n=1..d-1),d=2..12) ; # R. J. Mathar, Jun 07 2022

T(1,1)=1, T(1,2)=2, T(1,3)=4, T(1,k)=T(1,k-1)+T(1,k-2)+T(1,k-3) for k>3. Row 1 is the tribonacci basis; write B(k)=T(1,k). Each row satisfies the recurrence T(n,k)=T(n,k-1)+T(n,k-2)+T(n,k-3). T(n,1) is least number not in an earlier row. If T(n,1) has tribonacci representation B(k(1))+B(k(2))+...+B(k(m)), then T(n,2) = B(k(2))+B(k(3))+...+B(k(m+1)) and T(n,3) = B(k(3))+B(k(4))+...+B(k(m+2)). (Continued shifting of indices gives the other terms in row n, also.)

T(3, 4) corrected and more terms by John Keith, May 09 2022

A357644 Number of integer compositions of n into parts that are alternately unequal and equal.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 8, 13, 17, 25, 30, 44, 58, 77, 98, 142, 176, 245, 311, 426, 548, 758, 952, 1319, 1682, 2308, 2934, 4059, 5132, 7087, 9008, 12395, 15757, 21728, 27552, 38019, 48272, 66515, 84462, 116467, 147812, 203825, 258772, 356686, 452876, 624399, 792578

Offset: 0

Gus Wiseman, Oct 14 2022

nonn

			The a(1) = 1 through a(7) = 13 compositions:
  (1)  (2)  (3)   (4)    (5)    (6)     (7)
            (12)  (13)   (14)   (15)    (16)
            (21)  (31)   (23)   (24)    (25)
                  (211)  (32)   (42)    (34)
                         (41)   (51)    (43)
                         (122)  (411)   (52)
                         (311)  (1221)  (61)
                                (2112)  (133)
                                        (322)
                                        (511)
                                        (2113)
                                        (3112)
                                        (12211)

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Without equal relations we have A000213, equal only A027383.
Even-length opposite: A003242, ranked by A351010, partitions A035457.
The version for partitions is A351006.
The opposite version is A357643, partitions A351005.
A011782 counts compositions.
A357621 gives half-alternating sum of standard compositions, skew A357623.
A357645 counts compositions by half-alternating sum, skew A357646.
Cf. A001590, A029862, A035544, A097805, A122129, A122134, A122135, A351003, A351004, A351007, A357136, A357641.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@Table[#[[i]]==#[[i+1]],{i,2,Length[#]-1,2}]&&And@@Table[#[[i]]!=#[[i+1]],{i,1,Length[#]-1,2}]&]],{n,0,10}]

More terms from Alois P. Heinz, Oct 19 2022

A127193 A 9th-order Fibonacci sequence.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8185, 16353, 32673, 65281, 130433, 260609, 520705, 1040385, 2078721, 4153345, 8298505, 16580657, 33128641, 66192001, 132253569, 264246529, 527972353, 1054904321

Offset: 1

Luis A Restrepo (luisiii(AT)mac.com), Jan 07 2007

9-Bonacci constant = 1.99802947...

Robert Price, Table of n, a(n) for n = 1..1000
E. S. Croot, Notes on Linear Recurrence Sequences
M. A. Lerma, Recurrence Relations
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1,1,1).

Cf. Fibonacci numbers A000045, tribonacci numbers A000213, tetranacci numbers A000288, pentanacci numbers A000322, hexanacci numbers A000383, 7th-order Fibonacci numbers A060455, octanacci numbers, A123526.

LinearRecurrence[{1,1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1,1},40] (* Ray Chandler, Aug 01 2015 *)
With[{c=Table[1,{9}]},LinearRecurrence[c,c,40]] (* Harvey P. Dale, Apr 08 2016 *)

x='x+O('x^50); Vec((x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9+7*x^10)/(1 -2*x+ x^10)) \\ G. C. Greubel, Jul 28 2017

For a(1)=...=a(9)=1, a(10)=9, a(n)= 2*a(n-1) - a(n-10). - Vincenzo Librandi, Dec 20 2010

G.f.: x*(1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8+7*x^9)/(1-2*x+x^10). - G. C. Greubel, Jul 28 2017

A135491 Number of ways to toss a coin n times and not get a run of four.

Original entry on oeis.org

1, 2, 4, 8, 14, 26, 48, 88, 162, 298, 548, 1008, 1854, 3410, 6272, 11536, 21218, 39026, 71780, 132024, 242830, 446634, 821488, 1510952, 2779074, 5111514, 9401540, 17292128, 31805182, 58498850, 107596160, 197900192, 363995202, 669491554, 1231386948, 2264873704

Offset: 0

James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See column 2 of Table 2 p. 11.
Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani, Non-overlapping matrices, Theoretical Computer Science, Vol. 658, Part A (2017), 36-45.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Emrah Kılıç, Talha Arıkan, Evaluation of Hessenberg determinants with recursive entries: generating function approach, Filomat (2017) Vol. 31, Issue 15, pp. 4945-4962.
A. V. Zharkova, Inaccesible States in Dynamic Systems Associated with Paths and Cycles, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11 (2011), 116-122.
Index entries for linear recurrences with constant coefficients, signature (1, 1, 1).

Cf. A000073. Column 2 of A265624. Cf. A135492, A135493, A000213, A058265.

LinearRecurrence[{1, 1, 1}, {1, 2, 4, 8}, 36] (* Vladimir Joseph Stephan Orlovsky, Jul 23 2011; first term 1 added by Georg Fischer, Apr 02 2019 *)

Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ Altug Alkan, Dec 10 2015

a(n) = 2*A000073(n+2) for n > 0.
a(n) = a(n-1) + a(n-2) + a(n-3) for n > 3.
G.f.: -(x+1)*(x^2+1)/(x^3+x^2+x-1).
a(n) = nearest integer to b*c^n, where b = 1.2368... and c = 1.839286755... is the real root of x^3-x^2-x-1 = 0. See A058265. - N. J. A. Sloane, Jan 06 2010
G.f.: (1-x^4)/(1-2*x+x^4) and generally to "not get a run of k" (1-x^k)/(1-2*x+x^k). - Geoffrey Critzer, Feb 01 2012
G.f.: Q(0)/x^2 - 2/x- 1/x^2, where Q(k) = 1 + (1+x)*x^2 + (2*k+3)*x - x*(2*k+1 +x+x^2)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 04 2013
a(n) = A000213(n+3) - A000213(n+2), n>=1. - Peter M. Chema, Jan 11 2017.

More terms from Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

A218354 T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.

Original entry on oeis.org

1, 3, 3, 5, 11, 5, 9, 41, 41, 9, 17, 149, 291, 149, 17, 31, 547, 2069, 2069, 547, 31, 57, 2007, 14811, 28661, 14811, 2007, 57, 105, 7361, 105913, 401253, 401253, 105913, 7361, 105, 193, 27001, 757305, 5609569, 10982565, 5609569, 757305, 27001, 193, 355

Offset: 1

R. H. Hardin, Oct 26 2012

From Andrew Howroyd, May 10 2017: (Start)
Number of n X k binary matrices with every 1 vertically or horizontally adjacent to some 0.
Number of dominating sets in the grid graph P_n X P_k. (End)

			Table starts
....1.......3...........5..............9.................17
....3......11..........41............149................547
....5......41.........291...........2069..............14811
....9.....149........2069..........28661.............401253
...17.....547.......14811.........401253...........10982565
...31....2007......105913........5609569..........300126903
...57....7361......757305.......78394141.........8199377227
..105...27001.....5415209.....1095695529.......224032447213
..193...99043....38722037....15314367301......6121258910011
..355..363299...276885777...214044940145....167250519310183
..653.1332617..1979899795..2991651891557...4569773233045519
.1201.4888173.14157473937.41813576818545.124859601874166153
...
Some solutions for n=3 k=4
..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 198 terms from R. H. Hardin)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Dominating Set
Wikipedia, Dominating Set

Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
Diagonal is A133515.
Cf. A089934 (independent vertex sets), A210662 (matchings).

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3).
k=2: a(n) = 3*a(n-1) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).
k=3: a(n) = 6*a(n-1) +5*a(n-2) +22*a(n-3) +7*a(n-4) +8*a(n-5) -18*a(n-6) -20*a(n-7) -a(n-8) +4*a(n-9) +3*a(n-10) +a(n-12).
Column k=1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){a(n-i)} z=1,2,3,4

A107239 Sum of squares of tribonacci numbers (A000073).

Original entry on oeis.org

0, 0, 1, 2, 6, 22, 71, 240, 816, 2752, 9313, 31514, 106590, 360606, 1219935, 4126960, 13961456, 47231280, 159782161, 540539330, 1828631430, 6186215574, 20927817799, 70798300288, 239508933824, 810252920400, 2741065994769, 9272959837818, 31370198430718

Offset: 0

Jonathan Vos Post, May 17 2005

			a(7) = 71 = 0^2 + 0^2 + 1^2 + 1^2 + 2^2 + 4^2 + 7^2

R. Schumacher, Explicit formulas for sums involving the squares of the first n Tribonacci numbers, Fib. Q., 58:3 (2020), 194-202.

G. C. Greubel, Table of n, a(n) for n = 0..1000
M. Feinberg, Fibonacci-Tribonacci, Fib. Quart. 1(3) (1963), 71-74.
Z. Jakubczyk, Advanced Problems and Solutions, Fib. Quart. 51 (3) (2013) 185, H-715.
Eric Weisstein's World of Mathematics, Tribonacci Number
Index entries for linear recurrences with constant coefficients, signature (3,1,3,-7,1,-1,1).

Cf. A000073, A000213, A085697.

Cf. A107240, A107241, A107242, A107243, A107244, A107245, A107246, A107247.

R:=PowerSeriesRing(Integers(), 40); [0,0] cat Coefficients(R!( x^2*(1-x-x^2-x^3)/((1+x+x^2-x^3)*(1-3*x-x^2-x^3)*(1-x)) )); // G. C. Greubel, Nov 20 2021

b:= proc(n) option remember; `if`(n<3, [n*(n-1)/2$2],
     (t-> [t, t^2+b(n-1)[2]])(add(b(n-j)[1], j=1..3)))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 22 2021

Accumulate[LinearRecurrence[{1,1,1},{0,0,1},30]^2] (* Harvey P. Dale, Sep 11 2011 *)
LinearRecurrence[{3,1,3,-7,1,-1,1}, {0,0,1,2,6,22,71}, 30] (* Ray Chandler, Aug 02 2015 *)

@CachedFunction
def T(n): # A000073
    if (n<2): return 0
    elif (n==2): return 1
    else: return T(n-1) +T(n-2) +T(n-3)
def A107231(n): return sum(T(j)^2 for j in (0..n))
[A107239(n) for n in (0..40)] # G. C. Greubel, Nov 20 2021

a(n) = T(0)^2 + T(1)^2 + ... + T(n)^2 where T(n) = A000073(n).
From R. J. Mathar, Aug 19 2008: (Start)
a(n) = Sum_{i=0..n} A085697(i).
G.f.: x^2*(1-x-x^2-x^3)/((1+x+x^2-x^3)*(1-3*x-x^2-x^3)*(1-x)). (End)
a(n) = 1/4 - (1/11)*Sum_{R = RootOf(_Z^3-_Z^2-_Z-1)} ((3 + 7*_R + 5*_R^2)/(3*_R^2 - 2*_R - 1)*_R^(-n) - (1/44)*Sum{_R = RootOf(Z^3+_Z^2+3*_Z-1)} ((-1 - 2*_R - 9*_R^2)/(3*_R^2 + 2*_R + 3)*_R^(-n). - _Robert Israel, Mar 26 2010
a(n+1) = A000073(n)*A000073(n+1) + ( (A000073(n+1) - A000073(n-1))^2 - 1 )/4 for n>0 [Jakubczyk]. - R. J. Mathar, Dec 19 2013

A214827 a(n) = a(n-1) + a(n-2) + a(n-3), with a(0) = 1, a(1) = a(2) = 5.

Original entry on oeis.org

1, 5, 5, 11, 21, 37, 69, 127, 233, 429, 789, 1451, 2669, 4909, 9029, 16607, 30545, 56181, 103333, 190059, 349573, 642965, 1182597, 2175135, 4000697, 7358429, 13534261, 24893387, 45786077, 84213725, 154893189, 284892991, 523999905

Offset: 0

Abel Amene, Jul 29 2012

See comments in A214727.

Robert Price, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Cf. A000213, A000288, A000322, A000383, A060455, A136175, A141036, A141523, A214825-A214831.

a:=[1,5,5];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Apr 24 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+4*x-x^2)/(1-x-x^2-x^3) )); // G. C. Greubel, Apr 24 2019

LinearRecurrence[{1,1,1},{1,5,5},40] (* Ray Chandler, Dec 08 2013 *)

my(x='x+O('x^40)); Vec((1+4*x-x^2)/(1-x-x^2-x^3)) \\ G. C. Greubel, Apr 24 2019

((1+4*x-x^2)/(1-x-x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 24 2019

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

a(n) = -A000073(n) + 4*A000073(n+1) + A000073(n+2). - R. J. Mathar, Jul 29 2012

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

A122542 Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 2, -1, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Sage

Formula

A166444 a(0) = 0, a(1) = 1 and for n > 1, a(n) = sum of all previous terms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A136175 Tribonacci array, T(n,k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A357644 Number of integer compositions of n into parts that are alternately unequal and equal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A127193 A 9th-order Fibonacci sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A135491 Number of ways to toss a coin n times and not get a run of four.

Views

Author