A131577 -id:A131577 - cp's OEIS frontend

A365381 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.

1, 2, 1, 4, 2, 2, 1, 8, 4, 4, 5, 2, 2, 1, 16, 8, 8, 10, 10, 7, 5, 5, 2, 2, 1, 32, 16, 16, 20, 20, 23, 15, 15, 12, 12, 8, 5, 5, 2, 2, 1, 64, 32, 32, 40, 40, 46, 47, 38, 33, 35, 29, 28, 21, 17, 14, 13, 8, 5, 5, 2, 2, 1, 128, 64, 64, 80, 80, 92, 94, 102, 79, 82, 76, 75, 68, 64, 53, 48, 43, 34, 33, 23, 19, 15, 13, 8, 5, 5, 2, 2, 1

Offset: 0

Gus Wiseman, Sep 08 2023

Row lengths are A000124(n) = 1 + n*(n+1)/2.

			Triangle begins:
   1
   2  1
   4  2  2  1
   8  4  4  5  2  2  1
  16  8  8 10 10  7  5  5  2  2  1
  32 16 16 20 20 23 15 15 12 12  8  5  5  2  2  1
  64 32 32 40 40 46 47 38 33 35 29 28 21 17 14 13  8  5  5  2  2  1
Array begins:
     k=0   k=1  k=2  k=3  k=4  k=5  k=6  k=7  k=8  k=9
-------------------------------------------------------
n=0:  1
n=1:  2     1
n=2:  4     2    2    1
n=3:  8     4    4    5    2    2    1
n=4:  16    8    8    10   10   7    5    5    2    2
n=5:  32    16   16   20   20   23   15   15   12   12
n=6:  64    32   32   40   40   46   47   38   33   35
n=7:  128   64   64   80   80   92   94   102  79   82
n=8:  256   128  128  160  160  184  188  204  207  184
n=9:  512   256  256  320  320  368  376  408  414  440
The T(5,8) = 12 subsets are:
  {3,5}  {1,2,5}  {1,2,3,4}  {1,2,3,4,5}
         {1,3,4}  {1,2,3,5}
         {1,3,5}  {1,2,4,5}
         {2,3,5}  {1,3,4,5}
         {3,4,5}  {2,3,4,5}

Row lengths are A000124 = number of distinct sums of subsets of {1..n}.
Central column/main diagonal is A365376.
A000009 counts sets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A093971, A103580, A131577, A151897, A326080, A364272, A364534, A365073, A365377, A365380.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],k]&]],{n,0,8},{k,0,n*(n+1)/2}]

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568

Offset: 0

Gus Wiseman, Sep 01 2023

nonn

			The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
  {1}  {1}    {1}      {1}
       {2}    {3}      {2}
       {1,2}  {1,2}    {4}
              {1,3}    {1,2}
              {2,3}    {1,3}
              {1,2,3}  {1,4}
                       {2,3}
                       {2,4}
                       {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

Andrew Howroyd, Table of n, a(n) for n = 0..100
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The case of positive coefficients is A088314.
The case of subsets containing n is A131577.
The binary version is A365314, positive A365315.
The binary complement is A365320, positive A365321.
The positive complement is counted by A365322.
A version for partitions is A365379, strict A365311.
The complement is counted by A365380.
The case of subsets without n is A365542.
A326083 and A124506 appear to count combination-free subsets.
A179822 and A326080 count sum-closed subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],combs[n,#]!={}&]],{n,0,5}]

a(n)={
  my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
  my(recurse(k,b)=
    if(bittest(b,0), 2^(n+1-k),
    if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
    self()(k+1, b) + self()(k+1, comb(k,b)) )));
  recurse(1, 1<Andrew Howroyd, Sep 04 2023

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023

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

A087117 Number of zeros in the longest string of consecutive zeros in the binary representation of n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 1, 0, 3, 2, 1, 1, 2, 1, 1, 0, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 5, 4, 3, 3, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 0, 6, 5, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 5, 4, 3, 3, 2, 2

Offset: 0

Reinhard Zumkeller, Aug 14 2003

The following four statements are equivalent: a(n) = 0; n = 2^k - 1 for some k > 0; A087116(n) = 0; A023416(n) = 0.

The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. Then a(k) is the maximum part of this composition, minus one. The maximum part is A333766(k). - Gus Wiseman, Apr 09 2020

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A023416, A007088, A007814.
Cf. A025480, A038374, A090046, A090047, A090048, A090049, A090050.
Positions of zeros are A000225.
Positions of terms <= 1 are A003754.
Positions of terms > 0 are A062289.
Positions of first appearances are A131577.
The version for prime indices is A252735.
The proper maximum is A333766.
The version for minimum is A333767.
Maximum prime index is A061395.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Runs are counted by A124767.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Runs-resistance is A333628.
- Weakly decreasing compositions are A114994.
- Weakly increasing compositions are A225620.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
Cf. A029931, A048793, A061395, A087117, A228351, A328594, A333217, A333218, A333219, A333767, A333768.

import Data.List (unfoldr, group)
a087117 0       = 1
a087117 n
  | null $ zs n = 0
  | otherwise   = maximum $ map length $ zs n where
  zs = filter ((== 0) . head) . group .
       unfoldr (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, May 01 2012

A087117 := proc(n)
    local d,l,zlen ;
    if n = 0 then
        return 1 ;
    end if;
    d := convert(n,base,2) ;
    for l from nops(d)-1 to 0 by -1 do
        zlen := [seq(0,i=1..l)] ;
        if verify(zlen,d,'sublist') then
            return l ;
        end if;
    end do:
    return 0 ;
end proc; # R. J. Mathar, Nov 05 2012

nz[n_]:=Max[Length/@Select[Split[IntegerDigits[n,2]],MemberQ[#,0]&]]; Array[nz,110,0]/.-\[Infinity]->0 (* Harvey P. Dale, Sep 05 2017 *)

h(n)=if(n<2, return(0)); my(k=valuation(n,2)); if(k, max(h(n>>k), k), n++; n>>=valuation(n,2); h(n-1))
a(n)=if(n,h(n),1) \\ Charles R Greathouse IV, Apr 06 2022

a(n) = max(A007814(n), a(A025480(n-1))) for n >= 2. - Robert Israel, Feb 19 2017
a(2n+1) = a(n) (n>=1); indeed, the binary form of 2n+1 consists of the binary form of n with an additional 1 at the end - Emeric Deutsch, Aug 18 2017
For n > 0, a(n) = A333766(n) - 1. - Gus Wiseman, Apr 09 2020

A365376 Number of subsets of {1..n} with a subset summing to n.

Original entry on oeis.org

1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713

Offset: 0

Gus Wiseman, Sep 08 2023

nonn

			The a(1) = 1 through a(4) = 10 sets:
  {1}  {2}    {3}      {4}
       {1,2}  {1,2}    {1,3}
              {1,3}    {1,4}
              {2,3}    {2,4}
              {1,2,3}  {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

The case containing n is counted by A131577.
The version with re-usable parts is A365073.
The complement is counted by A365377.
The complement w/ re-usable parts is A365380.
Main diagonal of A365381.
A000009 counts sets summing to n, multisets A000041.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237668, A326080, A364534.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]

isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023

from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365376(n):
    if n == 0: return 1
    nset = set(range(1,n+1))
    s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
    for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
        if sum(a) >= n:
            aset = set(a)
            for p in s:
                if p.issubset(aset):
                    c += 1
                    break
    return c # Chai Wah Wu, Sep 09 2023

a(n) = 2^n-A365377(n). - Chai Wah Wu, Sep 09 2023

a(16)-a(25) from Michel Marcus, Sep 09 2023
a(26)-a(32) from Chai Wah Wu, Sep 09 2023
a(33)-a(35) from Chai Wah Wu, Sep 10 2023

A090129 Smallest exponent such that -1 + 3^a(n) is divisible by 2^n.

Original entry on oeis.org

1, 2, 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, 17179869184

Offset: 1

Labos Elemer and Ralf Stephan, Jan 19 2004

A131577 and A011782 are companions, A131577(n) + A011782(n) = 2^n, (and differences each other). - Paul Curtz, Jan 18 2009
A090127 with offset 0: (1, 2, 2, 4, 8, ...) = A(x) / A(x^2), when A(x) = (1 + 2x + 4x^2 + 8x^3 + ...). - Gary W. Adamson, Feb 20 2010
From Wolfdieter Lang, Apr 18 2012: (Start)
a(n) is the order of 3 modulo 2^n. For n=1 and 2 this is obviously 1 and 2, respectively, and for n >= 3 it is 2^(n-2).
For a proof see, e.g., the Graeme McRae link under A068531, the section 'A Different Approach', proposed by Alexander Monnas, the first part, where the result from the expansion of (4-1)^(2^(k-2)) holds only for k >= 3. See also the Charles R Greathouse IV program below where this result has been used.
This means that the cycle generated by 3, taken modulo 2^n, has length a(n), and that 3 is not a primitive root modulo 2^n, if n >= 3 (because Euler's phi(2^n) = 2^(n-1), n >= 1, see A000010).
(End)
Let r(x) = (1 + 2x + 2x^2 + 4x^3 + ...). Then (1 + 2x + 4x^2 + 8x^3 + ...) = (r(x) * r(x^2) * r(x)^4 * r(x^8) * ...). - Gary W. Adamson, Sep 13 2016

			a(1) = 1 since -1 + 3 = 2 is divisible by 2^1;
a(2) = a(3) = 2 since -1 + 9 = 8 is divisible by 4 = 2^2 and also by 8 = 2^3;
a(5) = 8 since -1 + 6561 = 6560 = 32*205 is divisible by 2^5.
From _Wolfdieter Lang_, Apr 18 2012: (Start)
n=3: the order of 3 (mod 8) is a(3)=2 because the cycle generated by 3 is [3, 3^2==1 (mod 8)].
n=5: a(5) = 2^3 = 8 because the cycle generated by 3 is [3^1=3, 3^2=9, 3^3=27, 17, 19, 25, 11, 1] (mod 32).
  The multiplicative group mod 32 is non-cyclic (see A033949(10)) with the additional four cycles  [5, 25, 29, 17, 21, 9, 13, 1], [7, 17, 23, 1], [15, 1], and [31, 1]. This is the cycle structure of the (Abelian) group Z_8 x Z_2 (see one of the cycle graphs shown in the Wikipedia link 'List of small groups' for the order phi(32)=16, given under A192005).
(End)

Index to divisibility sequences

Cf. A068531, A069895, A088660, A090739, A090740, A091512.

Essentially the same as A000079.

t=Table[Part[Flatten[FactorInteger[ -1+3^(n)]], 2], {n, 1, 130}] Table[Min[Flatten[Position[t, j]]], {j, 1, 10}]
Join[{1,2},2^Range[30]] (* or *) Join[{1,2},NestList[2#&,2,30]] (* Harvey P. Dale, Nov 08 2012 *)

a(n)=2^(n+(n<3)-2) \\ Charles R Greathouse IV, Apr 09 2012

def A090129(n): return n if n<3 else 1<Chai Wah Wu, Jul 11 2022

a(n) = 2^(n-2) if n >= 3, 1 for n=1 and 2 for n=2 (see the order comment above).

a(n+2) = A152046(n) + A152046(n+1) = 2*A011782(n). - Paul Curtz, Jan 18 2009

a(11) through a(20) from R. J. Mathar, Aug 08 2008

More terms (powers of 2, see a comment above) from Wolfdieter Lang, Apr 18 2012

A246074 Paradigm Shift Sequence for a (-4,5) production scheme with replacement.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 18, 20, 22, 24, 28, 32, 36, 40, 44, 48, 56, 64, 72, 80, 88, 96, 112, 128, 144, 160, 176, 192, 224, 256, 288, 320, 352, 384, 448, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2560, 2816, 3072, 3584, 4096, 4608, 5120, 5632, 6144, 7168, 8192, 9216

Offset: 1

Jonathan T. Rowell, Aug 13 2014

This sequence is the solution to the following problem: "Suppose you have the choice of using one of three production options: apply a simple incremental action, bundle existing output as an integrated product (which requires p=-4 steps), or implement the current bundled action (which requires q=5 steps). The first use of a novel bundle erases (or makes obsolete) all prior actions. How large an output can be generated in n time steps?"
A production scheme with replacement R(p,q) eliminates existing output followinging a bundling action, while an additive scheme A(p,q) retains the output. The schemes correspond according to A(p,q)=R(p-q,q), with the replacement scheme serving as the default presentation.
This problem is structurally similar to the Copy and Paste Keyboard problem: Existing sequences (A178715 and A193286) should be regarded as Paradigm-Shift Sequences with production schemes R(1,1) and R(2,1) with replacement, respectively.
The ideal number of implementations per bundle, as measured by the geometric growth rate (p+zq root of z), is z = 2.
All solutions will be of the form a(n) = (qm+r) * m^b * (m+1)^d.
The paradigm shift sequence for the R(-4,5) scheme is also the solution to the R(-2,4) scheme.

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

Paradigm shift sequences with implementation step q=5: A103969, A246074, A246075, A246076, A246079, A246083, A246087, A246091, A246095, A246099, A246103.

Paradigm shift sequences with negative bundling steps: A103969, A246074, A246075, A246076, A246079, A029750, A246078, A029747, A246077, A029744, A029747, A131577.

Join[{1, 2, 3, 4, 5}, LinearRecurrence[{0, 0, 0, 0, 0, 2}, {6, 7, 8, 9, 10, 11}, 64]] (* Jean-François Alcover, Sep 25 2017 *)

Vec(x*(1+x)^2 * (1-x+x^2)^2 * (1+x+x^2)^2 / (1-2*x^6) + O(x^100)) \\ Colin Barker, Nov 18 2016

a(n) = (qd+r) * d^(C-R) * (d+1)^R, where r = (n-Cp) mod q, Q = floor( (R-Cp)/q ), R = Q mod (C+1), and d = floor ( Q/(C+1) ).
a(n) = 2*a(n-6) for all n >= 12.
G.f.: x*(1+x)^2 * (1-x+x^2)^2 * (1+x+x^2)^2 / (1-2*x^6). - Colin Barker, Nov 18 2016

A352521 Triangle read by rows where T(n,k) is the number of integer compositions of n with k strong nonexcedances (parts below the diagonal).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 0, 4, 5, 3, 3, 1, 0, 6, 8, 7, 6, 4, 1, 0, 9, 12, 15, 12, 10, 5, 1, 0, 13, 19, 27, 25, 22, 15, 6, 1, 0, 18, 32, 43, 51, 46, 37, 21, 7, 1, 0, 25, 51, 70, 94, 94, 83, 58, 28, 8, 1, 0, 35, 77, 117, 162, 184, 176, 141, 86, 36, 9, 1, 0

Offset: 0

Gus Wiseman, Mar 22 2022

			Triangle begins:
   1
   1   0
   1   1   0
   2   1   1   0
   3   2   2   1   0
   4   5   3   3   1   0
   6   8   7   6   4   1   0
   9  12  15  12  10   5   1   0
  13  19  27  25  22  15   6   1   0
  18  32  43  51  46  37  21   7   1   0
  25  51  70  94  94  83  58  28   8   1   0
For example, row n = 6 counts the following compositions (empty column indicated by dot):
  (6)    (51)   (312)   (1113)   (11112)  (111111)  .
  (15)   (114)  (411)   (1122)   (11121)
  (24)   (132)  (1131)  (2112)   (11211)
  (33)   (141)  (1212)  (2121)   (21111)
  (42)   (213)  (1221)  (3111)
  (123)  (222)  (1311)  (12111)
         (231)  (2211)
         (321)

Andrew Howroyd, Table of n, a(n) for n = 0..1325
MathOverflow, Why 'excedances' of permutations? [closed].

Row sums are A011782.
The version for partitions is A114088.
Row sums without the last term are A131577.
The version for permutations is A173018.
Column k = 0 is A219282.
The corresponding rank statistic is A352514.
The weak version is A352522, first column A238874, rank statistic A352515.
The opposite version is A352524, first column A008930, rank stat A352516.
The weak opposite version is A352525, first col A177510, rank stat A352517.
A008292 is the triangle of Eulerian numbers (version without zeros).
A238349 counts comps by fixed points, first col A238351, rank stat A352512.
A352490 is the strong nonexcedance set of A122111.
A352523 counts comps by nonfixed points, first A352520, rank stat A352513.
Cf. A088218, A115994, A238352, A350839, A352487, A352491.

pa[y_]:=Length[Select[Range[Length[y]],#>y[[#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],pa[#]==k&]],{n,0,15},{k,0,n}]

T(n)={my(v=vector(n+1, i, i==1), r=v); for(k=1, n, v=vector(#v, j, sum(i=1, j-1, if(k>i,x,1)*v[j-i])); r+=v); vector(#v, i, Vecrev(r[i], i))}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 19 2023

Terms a(66) and beyond from Andrew Howroyd, Jan 19 2023

A261781 Number T(n,k) of compositions of n where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 4, 16, 13, 0, 8, 66, 132, 75, 0, 16, 248, 924, 1232, 541, 0, 32, 892, 5546, 13064, 13060, 4683, 0, 64, 3136, 30720, 114032, 195020, 155928, 47293, 0, 128, 10888, 162396, 893490, 2327960, 3116220, 2075948, 545835

Offset: 0

Alois P. Heinz, Aug 31 2015

From Vaclav Kotesovec, Oct 14 2017: (Start)
Conjecture: For k > 0 the recurrence order for column k is equal to k*(k+1)/2.
Column k > 0 is asymptotic to c(k) * d(k)^n, where c(k) and d(k) are constants (dependent only on k).
k                           c(k)                            d(k)
1  A131577(n) ~ 0.50000000000000000000000000 * 2.00000000000000000000000000^n.
2  A293579(n) ~ 0.60355339059327376220042218 * 3.41421356237309504880168872^n.
3  A293580(n) ~ 0.64122035031051210658648604 * 4.84732210186307263951891624^n.
4  A293581(n) ~ 0.66065168848540565019767995 * 6.28521350788324520158143964^n.
5  A293582(n) ~ 0.67250239588725756267924287 * 7.72502395887257562679242875^n.
6  A293583(n) ~ 0.68048292906885160660288253 * 9.16579514882621927923459043^n.
7  A293584(n) ~ 0.68622254929933439577377124 * 10.6071156901906815408327973^n.
8  A293585(n) ~ 0.69054873168854973836384871 * 12.0487797070167958138215794^n.
9  A293586(n) ~ 0.69392626461456654033893782 * 13.4906727630621977261008808^n.
10 A293587(n) ~ 0.69663630864564830007443110 * 14.9327261729129660014886221^n.
---
Conjecture: d(k+1) - d(k) tends to 1/log(2).
d(2) - d(1) = 1.414213562373095048801688724209698...
d(3) - d(2) = 1.433108539489977590717227522340838...
d(4) - d(3) = 1.437891406020172562062523400686067...
d(5) - d(4) = 1.439810450989330425210989107036901...
d(6) - d(5) = 1.440771189953643652442161677346934...
d(7) - d(6) = 1.441320541364462261598206961226199...
d(8) - d(7) = 1.441664016826114272988782079622148...
d(9) - d(8) = 1.441893056045401912279301345910755...
d(10)- d(9) = 1.442053409850768275387741352145193...
1 / log(2)  = 1.442695040888963407359924681001892...
(End)

			A(3,2) = 16: 3aab, 3abb, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  2,    3;
  0,  4,   16,    13;
  0,  8,   66,   132,     75;
  0, 16,  248,   924,   1232,    541;
  0, 32,  892,  5546,  13064,  13060,   4683;
  0, 64, 3136, 30720, 114032, 195020, 155928, 47293;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Table 2.

Columns k=0..10 give A000007, A131577, A293579, A293580, A293581, A293582, A293583, A293584, A293585, A293586, A293587.
Row sums give A120733.
Main diagonal gives A000670.
T(2n,n) gives A261784.
T(n+1,n)/2 gives A083385.
Cf. A261719 (same for partitions), A261780.

A:= proc(n, k) option remember; `if`(n=0, 1,
      add(A(n-j, k)*binomial(j+k-1, k-1), j=1..n))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

A[n_, k_] := A[n, k] = If[n==0, 1,
    Sum[A[n-j, k]*Binomial[j+k-1, k-1], {j, 1, n}]];
T[n_, k_] := Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 08 2017, translated from Maple *)

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261780(n,k-i).

A088138 Generalized Gaussian Fibonacci integers.

Original entry on oeis.org

0, 1, 2, 0, -8, -16, 0, 64, 128, 0, -512, -1024, 0, 4096, 8192, 0, -32768, -65536, 0, 262144, 524288, 0, -2097152, -4194304, 0, 16777216, 33554432, 0, -134217728, -268435456, 0, 1073741824, 2147483648, 0, -8589934592, -17179869184, 0, 68719476736, 137438953472

Offset: 0

Paul Barry, Sep 20 2003

The sequence 0,1,-2,0,8,-16,... has g.f. x/(1+2*x-4*x^2), a(n) = 2^n*sin(2n*Pi/3)/sqrt(3) and is the inverse binomial transform of sin(sqrt(3)*x)/sqrt(3): 0,1,-3,0,9,...
a(n+1) is the Hankel transform of A100192. - Paul Barry, Jan 11 2007
a(n+1) is the trinomial transform of A010892: a(n+1) = Sum_{k=0..2n} trinomial(n,k)*A010892(k+1) where trinomial(n, k) = trinomial coefficients (A027907). - Paul Barry, Sep 10 2007
a(n+1) is the Hankel transform of A100067. - Paul Barry, Jun 16 2009
From Paul Curtz, Oct 04 2009: (Start)
1) a(n) = A131577(n)*A128834(n).
2) Binomial transform of 0,1,0,-3,0,9,0,-27, see A000244.
3) Sequence is identical to every 2n-th difference divided by (-3)^n.
4) a(3n) + a(3n+1) + a(3n+2) = (-1)^n*3*A001018(n) for n >= 1.
5) For missing terms in a(n) see A013731 = 4*A001018. (End)
The coefficient of i of Q^n, where Q is the quaternion 1+i+j+k. Due to symmetry, also the coefficients of j and of k. - Stanislav Sykora, Jun 11 2012 [The coefficients of 1 are in A138230. - Wolfdieter Lang, Jan 28 2016]
With different signs, 0, 1, -2, 0, 8, -16, 0, 64, -128, 0, 512, -1024, ... is the Lucas U(-2,4) sequence. - R. J. Mathar, Jan 08 2013

Robert Israel, Table of n, a(n) for n = 0..3300
Beata Bajorska-Harapińska, Barbara Smoleń, and Roman Wituła, On Quaternion Equivalents for Quasi-Fibonacci Numbers, Shortly Quaternaccis, Advances in Applied Clifford Algebras (2019) Vol. 29, 54.
Wikipedia, Lucas sequence
Index entries for linear recurrences with constant coefficients, signature (2,-4).
Index entries for Lucas sequences

Cf. A084102, A088137, A045873, A088139, A138230.

a:=[0,1];; for n in [3..40] do a[n]:=2*a[n-1]-4*a[n-2]; od; a; # Muniru A Asiru, Oct 23 2018

I:=[0,1]; [n le 2 select I[n] else 2*Self(n-1) - 4*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 15 2018

M:= <<1+I,1+I>|>:
T:= <<-I/2,0>|<0,I/2>>:
seq(LinearAlgebra:-Trace(T.M^n),n=0..100); # Robert Israel, Jan 28 2016

Join[{a=0,b=1},Table[c=2*b-4*a;a=b;b=c,{n,100}]] (* Vladimir Joseph Stephan Orlovsky, Jan 17 2011 *)
LinearRecurrence[{2, -4}, {0, 1}, 40] (* Vincenzo Librandi, Jan 29 2016 *)
Table[2^(n-2)*((-1)^Quotient[n-1,3]+(-1)^Quotient[n,3]), {n,0,40}] (*Federico Provvedi,Apr 24 2022*)

/* lists powers of any quaternion */
QuaternionToN(a,b,c,d,nmax) = {local (C);C = matrix(nmax+1,4);C[1,1]=1;for(n=2,nmax+1,C[n,1]=a*C[n-1,1]-b*C[n-1,2]-c*C[n-1,3]-d*C[n-1,4];C[n,2]=b*C[n-1,1]+a*C[n-1,2]+d*C[n-1,3]-c*C[n-1,4];C[n,3]=c*C[n-1,1]-d*C[n-1,2]+a*C[n-1,3]+b*C[n-1,4];C[n,4]=d*C[n-1,1]+c*C[n-1,2]-b*C[n-1,3]+a*C[n-1,4];);return (C);} /* Stanislav Sykora, Jun 11 2012 */

my(x='x+O('x^30)); concat([0], Vec(x/(1-2*x+4*x^2))) \\ G. C. Greubel, Oct 22 2018

a(n) = 2^(n-1)*polchebyshev(n-1, 2, 1/2); \\ Michel Marcus, May 02 2022

[lucas_number1(n,2,4) for n in range(0, 39)] # Zerinvary Lajos, Apr 23 2009

G.f.: x/(1-2*x+4*x^2).
E.g.f.: exp(x)*sin(sqrt(3)*x)/sqrt(3).
a(n) = 2*a(n-1) - 4*a(n-2), a(0)=0, a(1)=1.
a(n) = ((1+i*sqrt(3))^n - (1-i*sqrt(3))^n)/(2*i*sqrt(3)).
a(n) = Im( (1+i*sqrt(3))^n/sqrt(3) ).
a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k+1)*(-3)^k.
From Paul Curtz, Oct 04 2009: (Start)
a(n) = a(n-1) + a(n-2) + 2*a(n-3).
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3).
a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4). (End)
E.g.f.: exp(x)*sin(sqrt(3)*x)/sqrt(3) = G(0)*x^2 where G(k)= 1 + (3*k+2)/(2*x - 32*x^5/(16*x^4 - 3*(k+1)*(3*k+2)*(3*k+4)*(3*k+5)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2012
G.f.: x/(1-2*x+4*x^2) = 2*x^2*G(0) where G(k)= 1 + 1/(2*x - 32*x^5/(16*x^4 - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jul 27 2012
a(n) = -2^(n-1)*Product_{k=1..n}(1 + 2*cos(k*Pi/n)) for n >= 1. - Peter Luschny, Nov 28 2019
a(n) = 2^(n-1) * U(n-1, 1/2), where U(n, x) is the Chebyshev polynomial of the second kind. - Federico Provvedi, Apr 24 2022

cp's OEIS Frontend

A365381 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

A087117 Number of zeros in the longest string of consecutive zeros in the binary representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A365376 Number of subsets of {1..n} with a subset summing to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A090129 Smallest exponent such that -1 + 3^a(n) is divisible by 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A246074 Paradigm Shift Sequence for a (-4,5) production scheme with replacement.

Views

Author

Keywords

Comments

Links