A052955 -id:A052955 - cp's OEIS frontend

A357187 First differences A357186 = "Take the k-th composition in standard order for each part k of the n-th composition in standard order, then add up everything.".

1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, -1, 1, 0, 0, -1, 1, 0, 0, 0, 1, 0, 0, -1, 0, 1, 0, -1, 1, 0, 0, -2, 1, 1, 0, -1, 1, 0, 0, 0, 0, 1, 0, -1, 1, 0, 0, -2, 1, 0, 0, 0, 1, 0, 0, -1, 0, 1, 0, -1, 1, 0, 0, -3, 1, 1, 0, 0, 1, 0, 0, -1, 0, 1, 0, -1, 1, 0, 0, -1, 1, 0

Offset: 0

Gus Wiseman, Sep 28 2022

sign

Are there any terms > 1?

The k-th composition in standard order (graded reverse-lexicographic, 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. This gives a bijective correspondence between nonnegative integers and integer compositions.

			We have A357186(5) - A357186(4) = 3 - 2 = 1, so a(4) = 1.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
Positions of first appearances appear to all belong to A052955.
Differences of A357186 (row-sums of A357135).
The version for partitions is A357458, differences of A325033.
Cf. A000120, A029837, A029931, A048896, A058891, A070939, A133494, A333766, A357134, A357137.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Differences[Table[stc/@stc[n]/.List->Plus,{n,0,100}]]

a(n) = A357186(n + 1) - A357186(n).

A268009 T(n,k)=Number of nXk 0..k arrays with every repeated value in every row and column unequal to the previous repeated value, and new values introduced in row-major sequential order.

Original entry on oeis.org

1, 2, 2, 4, 14, 3, 12, 159, 96, 5, 40, 3183, 7445, 726, 7, 154, 88243, 1396408, 381958, 5046, 11, 656, 3222467, 454238345, 700411548, 18691624, 35574, 15, 3074, 147078491, 231327070236, 2833253114538, 342829793123, 911680225, 242406, 23

Offset: 1

R. H. Hardin, Jan 24 2016

Table starts
..1.......2...........4..............12................40...............154
..2......14.........159............3183.............88243...........3222467
..3......96........7445.........1396408.........454238345......231327070236
..5.....726......381958.......700411548.....2833253114538.21815272076639694
..7....5046....18691624....342829793123.17551555370610669
.11...35574...911680225.166704329683286
.15..242406.43653230106
.23.1653750
.31

			Some solutions for n=3 k=4
..0..0..1..1....0..1..0..0....0..0..1..1....0..0..1..1....0..0..1..2
..1..1..0..2....0..0..1..1....1..2..1..2....1..1..2..2....1..2..1..3
..3..1..3..1....2..0..0..2....3..4..4..3....1..2..0..1....4..2..4..4

R. H. Hardin, Table of n, a(n) for n = 1..45

Column 1 is A052955(n-1).

Column 2 is A267913.

Empirical for column k:
k=1: a(n) = a(n-1) +2*a(n-2) -2*a(n-3)
k=2: [order 6] for n>8
k=3: [order 75]

A215936 a(n) = -2*a(n-1) + a(n-2) for n > 2, with a(0) = a(1) = 1, a(2) = 0.

Original entry on oeis.org

1, 1, 0, 1, -2, 5, -12, 29, -70, 169, -408, 985, -2378, 5741, -13860, 33461, -80782, 195025, -470832, 1136689, -2744210, 6625109, -15994428, 38613965, -93222358, 225058681, -543339720, 1311738121, -3166815962, 7645370045, -18457556052, 44560482149

Offset: 0

Michael Somos, Aug 28 2012

BINOMIAL transform is A052955.

Essentially the same as A000129, A069306, A048624, A215928, A077985, and A176981. - R. J. Mathar, Sep 08 2013

			G.f. = 1 + x + x^3 - 2*x^4 + 5*x^5 - 12*x^6 + 29*x^7 - 70*x^8 + 169*x^9 - 408*x^10 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. C. Firengiz and A. Dil, Generalized Euler-Seidel method for second order recurrence relations, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
Index entries for linear recurrences with constant coefficients, signature (-2,1).

Cf. A001542, A001653, A052955, A077985.

[1,1] cat [n le 2 select (n-1) else -2*Self(n-1)+Self(n-2): n in [1..35] ]; // Vincenzo Librandi, Sep 09 2013

CoefficientList[Series[(1 + 3 x + x^2)/(1 + 2 x - x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 09 2013 *)
a[ n_] := With[ {m = If[ n < 1, 1 - n, n], s = If[ n < 1, (-1)^n, 1]}, s SeriesCoefficient[ x (1 + 2 x) / (1 + 2 x - x^2), {x, 0, m}]]; (* Michael Somos, Mar 19 2019 *)

{a(n) = my(m=n, s=1); if(n<1, m=1-n; s=(-1)^n); s * polcoeff( x * (1 + 2*x) / (1 + 2*x - x^2) + x * O(x^m), m)}; /* Michael Somos, Mar 19 2019 */

G.f.: 1 / (1 - x / (1 + x / (1 + x / (1 + x)))) = (1 + 3*x + x^2) / (1 + 2*x - x^2).
a(n + 3) = A077985(n). a(n) * a(n+2) - a(n+1)^2 = -(-1)^n.
a(2*n + 1) = A001653(n). a(2*n + 2) = -A001542(n).
a(n) = Sum_{k=0..n} A147746(n,k)*(-1)^(n-k). - Philippe Deléham, Aug 30 2012
G.f.: 1 + x + x^2/(1-x)  - G(0)*x^2 /(2-2*x), where G(k)= 1 + 1/(1 - x*(2*k-1)/(x*(2*k+1) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 10 2013
a(n) = (-1)^n a(1-n) = A000129(-1-n) if n < 0. a(n-2) = 2*a(n-1) + a(n) if n<1 or n>2. - Michael Somos, Mar 19 2019
E.g.f.: exp(-x)*(4*cosh(sqrt(2)*x) + 3*sqrt(2)*sinh(sqrt(2)*x))/2 - 1. - Stefano Spezia, Oct 31 2024

A249724 Numbers k such that on row k of Pascal's triangle there is no multiple of 9 which would be less than any (potential) multiple of 4 on the same row.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 14, 16, 17, 20, 22, 23, 24, 25, 26, 28, 30, 32, 33, 34, 35, 36, 38, 40, 41, 42, 44, 48, 49, 50, 51, 52, 53, 56, 57, 58, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 76, 77, 78, 80, 84, 86, 88, 89, 92, 94, 96, 97, 98, 100, 101, 102, 104, 105, 106, 107, 108, 110, 112, 113, 114, 115, 116, 120, 121

Offset: 1

Antti Karttunen, Nov 04 2014

nonn

Disjoint union of {0} and the following sequences: A048278 (gives 7 other cases where there are neither multiples of 4 nor 9 on row k), A249722 (rows where a multiple of 4 is found before a multiple of 9), A249726 (cases where the least term on row k which is a multiple of 4 is also a multiple of 9, and vice versa, i.e., such a term a multiple of 36).

If A249717(k) < 3 then k is included in this sequence. This is a sufficient but not necessary condition, e.g., A249717(25) = 5, but 25 is also included in this sequence.

Antti Karttunen, Table of n, a(n) for n = 1..23590

Complement: A249723.

Cf. A007318, A052955, A249441, A249695, A249717, A048278, A048645, A051382, A249722, A249726.

A249724list(upto_n) = { my(i=0, n=0, dont_print=0); while(i

A060647 Number of alpha-beta evaluations in a tree of depth n and branching factor b=3.

Original entry on oeis.org

1, 3, 5, 11, 17, 35, 53, 107, 161, 323, 485, 971, 1457, 2915, 4373, 8747, 13121, 26243, 39365, 78731, 118097, 236195, 354293, 708587, 1062881, 2125763, 3188645, 6377291, 9565937, 19131875, 28697813, 57395627, 86093441, 172186883, 258280325, 516560651, 774840977

Offset: 0

Frank Ellermann, Apr 17 2001

			a(2n+1) = 2*a(2n) + 1, a(15) = a(2*7+1) = 2*a(14) + 1 = 2*4373 + 1 = 8747.

P. H. Winston, Artificial Intelligence, Addison-Wesley, 1977, pp. 115-122, (alpha-beta technique).

Harry J. Smith, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (1, 3, -3).

For b=2 see A052955.

Cf. A068911.

A060647 := proc(n,b) option remember: if n mod 2 = 0 then RETURN(2*b^(n/2)-1) else RETURN(b^((n-1)/2) +b^((n+1)/2)-1) fi: end: for n from 0 to 60 do printf(`%d,`, A060647(n,3)) od:
a[0]:=1:a[1]:=3:for n from 2 to 100 do a[n]:=3*a[n-2]+2 od: seq(a[n], n=0..33); # Zerinvary Lajos, Mar 17 2008

f[n_] := Simplify[Sqrt[3]^n(1 + 2/Sqrt[3]) + (1 - 2/Sqrt[3])(-Sqrt[3])^n - 1]; Table[ f[n], {n, 0, 34}] (* or *)
f[n_] := If[ EvenQ[n], 2(3^(n/2)) - 1, 3^((n - 1)/2) + 3^((n + 1)/2) - 1]; Table[ f[n], {n, 0, 34}] (* or *)
CoefficientList[ Series[(1 + 2x - x^2)/((1 - x)(1 - 3x^2)), {x, 0, 35}], x] (* Robert G. Wilson v, Nov 17 2005 *)

a(n) = { if (n%2==0, 2*(3^(n/2)) - 1, my(m=(n - 1)/2); 3^m + 3^(m + 1) - 1) } \\ Harry J. Smith, Jul 09 2009

a(2n) = 2*(3^n) - 1, a(2n+1) = 3^n + 3^(n+1) - 1.
Formula for b branches: a(2n) = 2*(b^n)-1, a(2n+1) = b^n+b^(n+1)-1.
a(n) = A068911(n+1) - 1.
G.f.: (1+2*z-z^2)/((1-z)*(1-3*z^2)). - Emeric Deutsch, Nov 18 2002
a(n) = (sqrt(3))^n(1+2/sqrt(3))+(1-2/sqrt(3))(-sqrt(3))^n-1. - Paul Barry, Apr 17 2004
a(2n+1) = 3*a(2n-1) + 2;  a(2n) = (a(2n-1) + a(2n+1))/2, with a(1)= 1. See A062318 for case where a(1)= 0.
a(n) = (2^((1+(-1)^n)/2))*(b^((2*n-1+(-1)^n)/4))+((1-(-1)^n)/2)*(b^((2*n+1-(-1)^n)/4))-1, with b=3. - Luce ETIENNE, Aug 30 2014

More terms from James Sellers, Apr 19 2001

A132340 a(n+1) = if {a(k):1<=k<=n} is a permutation of [1:n] then 2*a(n) else a(n)-1.

Original entry on oeis.org

1, 2, 4, 3, 6, 5, 10, 9, 8, 7, 14, 13, 12, 11, 22, 21, 20, 19, 18, 17, 16, 15, 30, 29, 28, 27, 26, 25, 24, 23, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85

Offset: 1

Reinhard Zumkeller, Aug 20 2007

nonn

Self-inverse permutation of natural numbers;
a(A052955(n)) = A027383(n);
a(A052955(n)-1)=a(A052955(n))/2; a(A052955(n)+1)=a(A052955(n))-1.
Almost certainly A132666 is a duplicate of this entry. - R. J. Mathar, Jun 12 2008

A180249 a(n) is the total number of k-reverses of n.

Original entry on oeis.org

1, 2, 4, 8, 16, 26, 50, 80, 130, 212, 342, 518, 820, 1276, 1864, 2960, 4336, 6704, 9710, 15068, 21368, 33420, 47082, 72950, 102316, 158888, 220882, 342616, 475108, 734816, 1015778, 1569680, 2161944, 3337952, 4587200, 7069748, 9699292, 14932444, 20445520

Offset: 1

John P. McSorley, Aug 19 2010

nonn

See sequence A180171 for the definition of a k-reverse of n.
Briefly, a k-reverse of n is a k-composition of n whose reverse is cyclically equivalent to itself.
This sequence is the total number of k-reverses of n for k=1,2,...,n.
It is the row sums of the 'R(n,k)' triangle from sequence A180171.
For example a(6)=26 because there are 26 k-reverses of n=6 for k=1,2,3,4,5, or 6.
They are, in cyclically equivalent, classes: {6}, {15,51}, {24,42},{33},{114,411,141},{222} {1113,3111,1311,1131}, {1122,2112,2211,1221}, {1212,2121}, {11112,21111,12111,11211,11121}, {111111}.

John P. McSorley: Counting k-compositions with palindromic and related structures. Preprint, 2010.

Andrew Howroyd, Table of n, a(n) for n = 1..200

If we ask for the number of cyclically equivalent classes we get sequence A052955.
For example the 6th term of A052955 is 11, corresponding to the 11 classes in the example above.
Row sums of A180171.
Cf. A056493, A180322.

f[n_Integer] := Block[{c = 0, k = 1, ip = IntegerPartitions@ n, lmt = 1 + PartitionsP@ n, ipk}, While[k < lmt, c += g[ ip[[k]]]; k++ ]; c]; g[lst_List] := Block[{c = 0, len = Length@ lst, per = Permutations@ lst}, While[ Length@ per > 0, rl = Union[ RotateLeft[ per[[1]], # ] & /@ Range@ len]; If[ MemberQ[rl, Reverse@ per[[1]]], c += Length@ rl]; per = Complement[ per, rl]]; c]; Array[f, 24] (* Robert G. Wilson v, Aug 25 2010 *)
b[n_] := Sum[MoebiusMu[n/d] * If[OddQ[d], 2, 3] * 2^Quotient[d-1, 2], {d, Divisors[n]}]; a[n_] := Sum[d*b[d], {d, Divisors[n]}] / 2; Array[a, 39] (* Jean-François Alcover, Nov 04 2017, after Andrew Howroyd *)

\\ here b(n) is A056493
b(n) = sumdiv(n, d, moebius(n/d) * if(d%2,2,3) * 2^((d-1)\2));
a(n) = sumdiv(n, d, d*b(d)) / 2; \\ Andrew Howroyd, Oct 07 2017

a(n) = Sum_{d|n} d*A056493(d)/2. - Andrew Howroyd, Oct 07 2017
From Petros Hadjicostas, Oct 15 2017: (Start)
a(n) = (n/2)*Sum_{d|n} (phi^(-1)(d)/d)*b(n/d), where phi^(-1)(n) = A023900(n) is the Dirichlet inverse of the Euler totient function and b(n) = A029744(n+1) (= 3*2^((n/2)-1), if n is even, and = 2^((n+1)/2), if n is odd).
G.f.: Sum_{n>=1} phi^(-1)(n)*g(x^n), where phi^(-1)(n) = A023900(n) and g(x) = x*(x+1)*(2*x+1)/(1-2*x^2)^2.
(End)

a(11) - a(24) from Robert G. Wilson v, Aug 25 2010
a(25) - a(27) from Robert G. Wilson v, Aug 29 2010
Terms a(28) and beyond from Andrew Howroyd, Oct 07 2017

A268180 T(n,k)=Number of nXk 0..k arrays with every repeated value in every row equal to, and in every column unequal to, the previous repeated value, and new values introduced in row-major sequential order.

Original entry on oeis.org

1, 2, 2, 5, 14, 3, 14, 187, 96, 5, 45, 3552, 9054, 726, 7, 163, 93311, 1589578, 494098, 5046, 11, 657, 3201247, 479973420, 829256141, 25770278, 35574, 15, 2910, 137687080, 225814538887, 3038628153922, 423155007379, 1339895662, 242406, 23

Offset: 1

R. H. Hardin, Jan 28 2016

Table starts
..1.......2...........5..............14................45...............163
..2......14.........187............3552.............93311...........3201247
..3......96........9054.........1589578.........479973420......225814538887
..5.....726......494098.......829256141.....3038628153922.21090319968167260
..7....5046....25770278....423155007379.19146833412153174
.11...35574..1339895662.214576839826736
.15..242406.68390077014
.23.1653750
.31

			Some solutions for n=3 k=4
..0..1..2..2....0..1..0..0....0..1..1..2....0..0..1..0....0..0..0..1
..0..0..3..1....0..1..0..0....0..0..1..3....0..1..2..2....0..0..1..0
..3..3..1..4....1..2..3..3....4..1..0..4....3..1..2..4....2..1..3..4

R. H. Hardin, Table of n, a(n) for n = 1..45

Column 1 is A052955(n-1).
Column 2 is A267913.
Row 1 is A268004.
Row 2 is A268005.

Empirical for column k:
k=1: a(n) = a(n-1) +2*a(n-2) -2*a(n-3)
k=2: [order 6] for n>8
k=3: [order 17] for n>19

A094723 a(n) = Pell(n+2) - 2^n.

Original entry on oeis.org

1, 3, 8, 21, 54, 137, 344, 857, 2122, 5229, 12836, 31413, 76686, 186833, 454448, 1103921, 2678674, 6494037, 15732284, 38089677, 92173782, 222961529, 539145416, 1303349513, 3150038746, 7611815613, 18390447188, 44426264421, 107310084894

Offset: 0

Paul Barry, May 23 2004

Binomial transform of A052955.

The sequence b(n) = 2*a(n), n >= -1, is an elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 23 and 464, lead to the b(n) sequence. For the central square these vectors lead to the companion sequence A175658. - Johannes W. Meijer, Aug 15 2010

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

Cf. A000129.

I:=[1, 3, 8]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-2*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 24 2012

LinearRecurrence[{4,-3, -2},{1,3,8},40] (* Vincenzo Librandi, Jun 24 2012 *)

G.f.: (1 - x - x^2)/((1-2*x)*(1 - 2*x - x^2)).
a(n) = ((1+sqrt(2))^n*(3*sqrt(2)/4+1) - (3*sqrt(2)/4-1)*(1-sqrt(2))^n) - 2^n.
a(n) = 4*a(n-1) - 3*a(n-2) - 2*a(n-3). - Vincenzo Librandi, Jun 24 2012

A107659 a(n) = Sum_{k=0..n} 2^max(k, n-k).

Original entry on oeis.org

1, 4, 10, 24, 52, 112, 232, 480, 976, 1984, 4000, 8064, 16192, 32512, 65152, 130560, 261376, 523264, 1047040, 2095104, 4191232, 8384512, 16771072, 33546240, 67096576, 134201344, 268410880, 536838144, 1073692672, 2147418112

Offset: 0

Mitch Harris

Define an infinite array by m(n,k) = 2^n-n+k for n>=k>=0 (in the lower left triangle) and by m(n,k) = 2^k+k-n for k>=n>=0 (in the upper right triangle). The antidiagonal sums of this array are a(n) = sum_{k=0..n} m(n-k,k). - J. M. Bergot, Aug 16 2013

			G.f. = 1 + 4*x + 10*x^2 + 24*x^3 + 52*x^4 + 112*x^5 + 232*x^6 + 480*x^7 + ... - _Michael Somos_, Jun 24 2018

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

Cf. A027383, A052955.

Table[Sum[2^Max[k,n-k],{k,0,n}],{n,0,30}] (* or *) LinearRecurrence[ {2,2,-4},{1,4,10},30] (* Harvey P. Dale, Nov 10 2013 *)
a[ n_] := 2^(n + 2) - (2 + Mod[n + 1, 2]) 2^Quotient[n + 1, 2]; (* Michael Somos, Jun 24 2018 *)

{a(n) = 2^(n+2) - (2 + (n+1)%2) * 2^((n+1)\2)}; /* Michael Somos, Jun 24 2018 */

a(2n) = 2^n(2^(n+2)-3), a(2n+1) = 2^n(2^(n+3)-4).
G.f.: (1+2*x)/[(1-2*x)*(1-2*x^2)].
a(n) = A122746(n) +2*A122746(n-1). - R. J. Mathar, Aug 16 2013
a(0)=1, a(1)=4, a(2)=10, a(n)=2*a(n-1)+2*a(n-2)-4*a(n-3). - Harvey P. Dale, Nov 10 2013
a(n) = 2^(n+2) - (2 + mod(n+1, 2)) * 2^floor((n+1)/2). - Michael Somos, Jun 24 2018
a(n) = - (2^(n+2)) * A052955(-n-3) for all n in Z. - Michael Somos, Jun 24 2018

cp's OEIS Frontend

A357187 First differences A357186 = "Take the k-th composition in standard order for each part k of the n-th composition in standard order, then add up everything.".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A268009 T(n,k)=Number of nXk 0..k arrays with every repeated value in every row and column unequal to the previous repeated value, and new values introduced in row-major sequential order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A215936 a(n) = -2*a(n-1) + a(n-2) for n > 2, with a(0) = a(1) = 1, a(2) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A249724 Numbers k such that on row k of Pascal's triangle there is no multiple of 9 which would be less than any (potential) multiple of 4 on the same row.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A060647 Number of alpha-beta evaluations in a tree of depth n and branching factor b=3.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A132340 a(n+1) = if {a(k):1<=k<=n} is a permutation of [1:n] then 2*a(n) else a(n)-1.

Views

Author

Keywords

Comments

Links

A180249 a(n) is the total number of k-reverses of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A268180 T(n,k)=Number of nXk 0..k arrays with every repeated value in every row equal to, and in every column unequal to, the previous repeated value, and new values introduced in row-major sequential order.

Views

Author

Keywords