A000126 -id:A000126 - cp's OEIS frontend

A066067 Number of binary strings u of any length with property that length(u) + number of 0's in u <= n (only one of a string and its reversal are counted).

1, 2, 3, 6, 10, 18, 29, 49, 78, 128, 203, 329, 523, 844, 1347, 2172, 3480, 5614, 9023, 14567, 23466, 37910, 61165, 98865, 159677, 258190, 417283, 674890, 1091214, 1765146, 2854793, 4618373, 7470614, 12086436, 19552903, 31635193, 51181367, 82809832

Offset: 1

Frank Ellermann, Dec 02 2001

nonn

If 0 is replaced by 2 (as in A007931) "length + 0-bits" is simply the total of ternary digits (e.g., 3 for 21 instead of 01).

			a(3) = 3: 0 01 111 (e.g. 01: length 2 + 1 zero = 3).
a(4) = 6: 0 01 00 011 101 1111.
a(5) =10: 0 01 00 011 101 001 010 0111 1011 11111.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-4,4,-2,1,1,-1)

If reversals are counted as distinct then we obtain A000126.
A007931 (binary strings represented by ternary numbers),
Cf. A035615 (binary "same game").

CoefficientList[Series[x (-x^7-x^4+3x^3-2x^2-x+1)/((1-x-x^2) (1-x^2-x^4) (1-x)^2),{x,0,50}],x] (* Harvey P. Dale, Jun 15 2011 *)

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

More terms from Harvey P. Dale, Jun 15 2011

A210677 a(n) = a(n-1) + a(n-2) + n + 1, a(0) = a(1) = 1.

Original entry on oeis.org

1, 1, 5, 10, 20, 36, 63, 107, 179, 296, 486, 794, 1293, 2101, 3409, 5526, 8952, 14496, 23467, 37983, 61471, 99476, 160970, 260470, 421465, 681961, 1103453, 1785442, 2888924, 4674396, 7563351, 12237779, 19801163, 32038976, 51840174, 83879186, 135719397, 219598621, 355318057

Offset: 0

Alex Ratushnyak, May 09 2012

Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A081659: a(n)=a(n-1)+a(n-2)+n-5, a(0)=a(1)=1 (except first 2 terms and sign).
Cf. A001924: a(n)=a(n-1)+a(n-2)+n-4, a(0)=a(1)=1 (except first 4 terms).
Cf. A000126: a(n)=a(n-1)+a(n-2)+n-2, a(0)=a(1)=1 (except first term).
Cf. A066982: a(n)=a(n-1)+a(n-2)+n-1, a(0)=a(1)=1.
Cf. A030119: a(n)=a(n-1)+a(n-2)+n, a(0)=a(1)=1.
Cf. A210678: a(n)=a(n-1)+a(n-2)+n+2, a(0)=a(1)=1.

LinearRecurrence[{3, -2, -1, 1}, {1, 1, 5, 10}, 39] (* Jean-François Alcover, Oct 05 2017 *)

From Colin Barker, Jun 30 2012: (Start)
a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4).
G.f.: (1 - 2*x + 4*x^2 - 2*x^3)/((1 - x)^2*(1 - x - x^2)). (End)
E.g.f.: exp(x/2)*(25*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(4 + x). - Stefano Spezia, Feb 24 2023

A210728 a(n) = a(n-1) + a(n-2) + n + 2 with n>1, a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 7, 14, 27, 48, 83, 140, 233, 384, 629, 1026, 1669, 2710, 4395, 7122, 11535, 18676, 30231, 48928, 79181, 128132, 207337, 335494, 542857, 878378, 1421263, 2299670, 3720963, 6020664, 9741659, 15762356, 25504049, 41266440, 66770525, 108037002, 174807565

Offset: 0

Alex Ratushnyak, May 10 2012

Bruno Berselli, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A065220: a(n)=a(n-1)+a(n-2)+n-5, a(0)=1,a(1)=2 (except first 2 terms).
Cf. A168043: a(n)=a(n-1)+a(n-2)+n-3, a(0)=1,a(1)=2 (except first 2 terms).
Cf. A131269: a(n)=a(n-1)+a(n-2)+n-2, a(0)=1,a(1)=2.
Cf. A000126: a(n)=a(n-1)+a(n-2)+n-1, a(0)=1,a(1)=2.
Cf. A104161: a(n)=a(n-1)+a(n-2)+n,   a(0)=1,a(1)=2 (except the first term).
Cf. A192969: a(n)=a(n-1)+a(n-2)+n+1, a(0)=1,a(1)=2.
Cf. A210729: a(n)=a(n-1)+a(n-2)+n+3, a(0)=1,a(1)=2.

RecurrenceTable[{a[0] == 1, a[1] == 2, a[n] == a[n - 1] + a[n - 2] + n + 2}, a, {n, 36}] (* Bruno Berselli, Jun 27 2012 *)
nxt[{n_,a_,b_}]:={n+1,b,a+b+n+3}; NestList[nxt,{1,1,2},40][[;;,2]] (* Harvey P. Dale, Aug 26 2024 *)

G.f.: (1-x+3*x^2-2*x^3)/((1-x)^2*(1-x-x^2)). - Bruno Berselli, Jun 27 2012
a(n) = ((5+sqrt(5))*(1+sqrt(5))^(n+1)-(5-sqrt(5))*(1-sqrt(5))^(n+1))/(2^(n+1)*sqrt(5))-n-5. - Bruno Berselli, Jun 27 2012
a(n) = -n-5+A022112(n+1). R. J. Mathar, Jul 03 2012

A210729 a(n) = a(n-1) + a(n-2) + n + 3 with n>1, a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 8, 16, 31, 55, 95, 160, 266, 438, 717, 1169, 1901, 3086, 5004, 8108, 13131, 21259, 34411, 55692, 90126, 145842, 235993, 381861, 617881, 999770, 1617680, 2617480, 4235191, 6852703, 11087927, 17940664, 29028626, 46969326, 75997989, 122967353

Offset: 0

Alex Ratushnyak, May 10 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A065220: a(n)=a(n-1)+a(n-2)+n-5, a(0)=1,a(1)=2 (except first 2 terms).
Cf. A168043: a(n)=a(n-1)+a(n-2)+n-3, a(0)=1,a(1)=2 (except first 2 terms).
Cf. A131269: a(n)=a(n-1)+a(n-2)+n-2, a(0)=1,a(1)=2.
Cf. A000126: a(n)=a(n-1)+a(n-2)+n-1, a(0)=1,a(1)=2.
Cf. A104161: a(n)=a(n-1)+a(n-2)+n,   a(0)=1,a(1)=2 (except the first term).
Cf. A192969: a(n)=a(n-1)+a(n-2)+n+1, a(0)=1,a(1)=2.
Cf. A210728: a(n)=a(n-1)+a(n-2)+n+2, a(0)=1,a(1)=2.
Cf. A000032, A000045.

F:=Fibonacci;; List([0..40], n-> 2*F(n+3)+3*F(n+1)-n-6); # G. C. Greubel, Jul 09 2019

[3*Fibonacci(n+1)+2*Fibonacci(n+3)-n-6: n in [0..40]]; // Vincenzo Librandi, Jul 18 2013

Table[3*Fibonacci[n+1]+2*Fibonacci[n+3]-n-6,{n,0,40}] (* Vaclav Kotesovec, May 13 2012 *)

vector(40, n, n--; f=fibonacci; 2*f(n+3)+3*f(n+1)-n-6) \\ G. C. Greubel, Jul 09 2019

prpr, prev = 1,2
for n in range(2, 99):
    current = prev+prpr+n+3
    print(prpr, end=',')
    prpr = prev
    prev = current

f=fibonacci; [2*f(n+3)+3*f(n+1)-n-6 for n in (0..40)] # G. C. Greubel, Jul 09 2019

G.f.: (1-x+4*x^2-3*x^3)/((1-x-x^2)*(1-x)^2).
a(n) = 3*Fibonacci(n+1)+2*Fibonacci(n+3)-n-6. - Vaclav Kotesovec, May 13 2012
a(n) = 2*Lucas(n+2) + Fibonacci(n+1) - (n+6). - G. C. Greubel, Jul 09 2019

A306416 Number of ordered set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Original entry on oeis.org

1, 0, 0, 0, 2, 0, 26, 84, 950, 6000, 62522, 556116, 6259598, 69319848, 874356338, 11384093196, 161462123894, 2397736692144, 37994808171962, 631767062124564, 11088109048500158, 203828700127054008, 3928762035148317314, 79079452776283889820, 1661265965479375937030, 36332908076071038467520, 826376466514358722894154

Offset: 0

Gus Wiseman, Feb 14 2019

nonn

			The a(4) = 2 ordered set partitions are: {{1,3},{2,4}}, {{2,4},{1,3}}.

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000126, A000296, A000670, A001610, A032032 (adjacencies allowed), A052841 (singletons allowed), A124323, A169985, A306417, A324011 (orderless case), A324012, A324015.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[Length[stn]!,{stn,Select[sps[Range[n]],And[Count[#,{_}]==0,Total[If[First[#]==1&&Last[#]==n,1,0]+Count[Subtract@@@Partition[#,2,1],-1]&/@#]==0]&]}],{n,0,10}]

a(12)-a(26) from Alois P. Heinz, Feb 14 2019

A306418 Regular triangle read by rows where T(n, k) is the number of set partitions of {1, ..., n} requiring k steps of removing singletons and cyclical adjacency initiators until reaching a fixed point, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 3, 0, 1, 2, 12, 0, 0, 0, 12, 35, 5, 0, 0, 5, 56, 100, 42, 0, 0, 0, 14, 282, 343, 231, 7, 0, 0, 0, 66, 1406, 1476, 1088, 104, 0, 0, 0, 0, 307, 7592, 7383, 4929, 909, 27, 0, 0, 0, 0, 1554, 44227, 40514, 22950, 6240, 470, 20, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 14 2019

See Callan's article for details on this transformation (SeparateIS).

			Triangle begins:
    1
    0    1
    0    2    0
    0    2    3    0
    1    2   12    0    0
    0   12   35    5    0    0
    5   56  100   42    0    0    0
   14  282  343  231    7    0    0    0
   66 1406 1476 1088  104    0    0    0    0
  307 7592 7383 4929  909   27    0    0    0    0

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Row sums are A000110. First column is A324011.

Cf. A000126, A000296, A001610, A306416, A306417, A324012.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
qbj[stn_]:=With[{ini=Join@@Table[Select[s,If[#==Max@@Max@@@stn,MemberQ[s,First[Union@@stn]],MemberQ[s,(Union@@stn)[[Position[Union@@stn,#][[1,1]]+1]]]]&],{s,stn}],sng=Join@@Select[stn,Length[#]==1&]},DeleteCases[Table[Complement[s,Union[sng,ini]],{s,stn}],{}]];
Table[Length[Select[sps[Range[n]],Length[FixedPointList[qbj,#]]-2==k&]],{n,0,8},{k,0,n}]

A350603 Irregular triangle read by rows: row n lists the elements of the set S_n in increasing order, where S_0 = {0}, and S_n is obtained by applying the operations x -> x+1 and x -> 2*x to S_{n-1}.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64

Offset: 0

N. J. A. Sloane, Jan 12 2022, following a suggestion from James Propp

Theorem: S_n contains Fibonacci(n+2) elements.
Proof from Adam P. Goucher, Jan 12 2022 (Start)
Let 'D' and 'I' be the 'double' and 'increment' operators, acting on 0 from the right. Then every element of S_n can be written as a length-n word over {D,I}. E.g., S_4 contains
   0: DDDD
   1: DDDI
   2: DDID
   3: DIDI
   4: DIDD
   5: IDDI
   6: IDID
   8: IDDD
We can avoid having two adjacent 'I's (because we can transform it into an equivalent word by prepending a 'D' -- which has no effect -- and then replacing the first 'DII' with 'ID').
Subject to the constraint that there are no two adjacent 'I's, these 'II'-less words all represent distinct integers (because of the uniqueness of binary expansions).
So we're left with the problem of enumerating length-n words over the alphabet {I, D} which do not contain 'II' as a substring. These are easily seen to be the Fibonacci numbers because we can check n=0 and n=1 and verify that the recurrence relation holds since a length-n word is either a length-(n-1) word followed by 'D' or a length-(n-2) word followed by 'DI'. QED (End)
From Rémy Sigrist, Jan 12 2022: (Start)
For any m >= 0, the value m first appears on row A056792(m).
For any n > 0: row n minus row n-1 corresponds to row n of A243571.
(End)

			The first few sets S_n are:
[0],
[0, 1],
[0, 1, 2],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4, 5, 6, 8],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64],
...

Alois P. Heinz, Rows n = 0..21, flattened

Cf. A000045, A000126, A002977, A056792, A122554, A243571, A350604.

T:= proc(n) option remember; `if`(n=0, 0,
      sort([map(x-> [x+1, 2*x][], {T(n-1)})[]])[])
    end:
seq(T(n), n=0..8);  # Alois P. Heinz, Jan 12 2022

T[n_] := T[n] = If[n==0, {0}, {#+1, 2#}& /@ T[n-1] // Flatten //
      Union];
Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

from itertools import chain, islice
def A350603_gen(): # generator of terms
    s = {0}
    while True:
        yield from sorted(s)
        s = set(chain.from_iterable((x+1,2*x) for x in s))
A350603_list = list(islice(A350603_gen(),30)) # Chai Wah Wu, Jan 12 2022

Definition made more precise by Chai Wah Wu, Jan 12 2022

A111645 Expansion of (x+1)(1-3x)/((x^2+4x+1)(x^2-2*x-1)).

Original entry on oeis.org

-1, 8, -37, 156, -625, 2436, -9341, 35464, -133809, 502896, -1885317, 7056580, -26384961, 98589388, -368228797, 1374944336, -5133041825, 19160828056, -71518973861, 266936079404, -996276071249, 3718290672596, -13877182280637, 51791152239960, -193289149920721

Offset: 0

Creighton Dement, Aug 10 2005

In reference to the program code, the sequence of Pell numbers A000126 is given by 1kbaseseq[C*J]. A001353 is 1ibaseiseq[C*J].

Floretion Algebra Multiplication Program, FAMP Code: 1jbasejseq[C*J] with C = - 'j + 'k - j' + k' - 'ii' - 'ij' - 'ik' - 'ji' - 'ki' and J = + j' + k' + 1.5'ii' + .5'jj' + .5'kk' + .5e

Index entries for linear recurrences with constant coefficients, signature (-6,-8,2,1).

Cf. A111639, A111640, A111641, A111642, A111643, A111644, A000126.

CoefficientList[Series[(x+1)(1-3x)/((x^2+4x+1)(x^2-2x-1)),{x,0,30}],x] (* or *) LinearRecurrence[{-6,-8,2,1},{-1,8,-37,156},30] (* Harvey P. Dale, Nov 19 2015 *)

a(0)=-1, a(1)=8, a(2)=-37, a(3)=156, a(n)=-6*a(n-1)-8*a(n-2)+2*a(n-3)+a(n-4). - Harvey P. Dale, Nov 19 2015

2*a(n) = -7*A125905(n)-A125905(n-1) -A077985(n-1)+5*A077985(n). - R. J. Mathar, Sep 11 2019

A196875 a(n) = a(n-4) + a(n-3) + a(n-2) + a(n-1) + (n-5).

Original entry on oeis.org

1, 1, 1, 1, 4, 8, 16, 32, 64, 125, 243, 471, 911, 1759, 3394, 6546, 12622, 24334, 46910, 90427, 174309, 335997, 647661, 1248413, 2406400, 4638492, 8940988, 17234316, 33220220, 64034041, 123429591, 237918195, 458602075, 883983931, 1703933822, 3284438054

Offset: 1

Aditya Subramanian, Oct 07 2011

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,0,0,-1,1).

Cf. A000126, A196787.

a:= n-> (Matrix(6, (i, j)-> `if`(i=j-1, 1, `if`(i=6, [1, -1, 0, 0, -2, 3][j], 0)))^n. <<-1, 1, 1, 1, 1, 4>>)[1, 1]: seq(a(n), n=1..50); # Alois P. Heinz, Oct 15 2011

nn = 40; a[1] = a[2] = a[3] = a[4] = 1; Do[a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4] + (n - 5), {n, 5, nn}]; Table[a[n], {n, nn}] (* T. D. Noe, Oct 07 2011 *)
RecurrenceTable[{a[1]==a[2]==a[3]==a[4]==1,a[n]==a[n-1]+a[n-2]+a[n-3]+a[n-4]+(n-5)},a,{n,40}] (* or *) LinearRecurrence[{3,-2,0,0,-1,1},{1,1,1,1,4,8},40] (* Harvey P. Dale, Aug 25 2014 *)

G.f.: (x^5-3*x^4+2*x-1)*x / ((x^4+x^3+x^2+x-1)*(x-1)^2 ).
a(n) = +3*a(n-1) -2*a(n-2) -a(n-5) +a(n-6).
a(n) = 5/9-n/3 +(10*A000078(n) +17*A000078(n+1) +21*A000078(n+2) -14*A000078(n+3))/9. - R. J. Mathar, Oct 16 2011

A196876 a(n) = a(n-no-1)+....+a(n-1)+(n-no-2) where no is the 'no+1'th order of the series and 'n' is the element number, here no=6.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 7, 14, 28, 56, 112, 224, 448, 896, 1786, 3559, 7091, 14127, 28143, 56063, 111679, 222463, 443141, 882724, 1758358, 3502590, 6977038, 13898014, 27684350, 55146238, 109849336, 218815949, 435873541, 868244493, 1729511949, 3445125885

Offset: 1

Aditya Subramanian, Oct 07 2011

A196787, A000126, and A000124 are all specific series of this general formula of series. When no=2 the series is A196787. When no=0 the series is A000124 with an additional '1' at the beginning. When no=1 the series is A000126 with an additional '1' at the beginning.

The data given above is the series with no=6 and n=25, having a(1)=.....a(no+1)=1 initially.

			For n=25, no=6, then a(1)=1, a(2)=1, ......, a(no)=1 and a(7)=a(1)+a(2)+....a(no)+(6-no), a(8)=a(2)+...a(no+1)+(7-no), a(n)=a(n-no)+....a(n-1)+((n-1)-no) and so a(25)=a(19)+....a(24)+(24-6).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,0,0,0,0,0,-1,1).

A196876 := proc(n)
        option remember;
        if n <= 7 then
                1;
        else
                n-6-2+add(procname(n-i),i=1..7) ;
        end if;
end proc: # R. J. Mathar, Oct 21 2011

CoefficientList[Series[(- 1 + 2 x - 6 x^7 + 4 x^8)/((x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x - 1) (x - 1)^2), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 11 2012 *)

a(n)=1 if n<=7, else a(n) = n-no-2+sum_{i=1..no+1} a(n-i), no=6.

G.f.: x*( -1+2*x-6*x^7+4*x^8 ) / ( (x^7+x^6+x^5+x^4+x^3+x^2+x-1)*(x-1)^2 ). - R. J. Mathar, Oct 21 2011

cp's OEIS Frontend

A066067 Number of binary strings u of any length with property that length(u) + number of 0's in u <= n (only one of a string and its reversal are counted).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A210677 a(n) = a(n-1) + a(n-2) + n + 1, a(0) = a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A210728 a(n) = a(n-1) + a(n-2) + n + 2 with n>1, a(0)=1, a(1)=2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A210729 a(n) = a(n-1) + a(n-2) + n + 3 with n>1, a(0)=1, a(1)=2.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Python

Sage

Formula

A306416 Number of ordered set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A306418 Regular triangle read by rows where T(n, k) is the number of set partitions of {1, ..., n} requiring k steps of removing singletons and cyclical adjacency initiators until reaching a fixed point, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A350603 Irregular triangle read by rows: row n lists the elements of the set S_n in increasing order, where S_0 = {0}, and S_n is obtained by applying the operations x -> x+1 and x -> 2*x to S_{n-1}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Extensions

A111645 Expansion of (x+1)*(1-3*x)/((x^2+4*x+1)*(x^2-2*x-1)).

Views

A111645 Expansion of (x+1)(1-3x)/((x^2+4x+1)(x^2-2*x-1)).