A178470 -id:A178470 - cp's OEIS frontend

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

0, 1, 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525, 255418101, 448227521

Offset: 0

N. J. A. Sloane and R. K. Guy

a(n+3) is the number of n-bit sequences that avoid 010. Example: For n=4 the 12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010. - David Callan, Mar 25 2004
a(n+2) is the number of compositions (ordered partitions) of n where no two adjacent parts are != 1, see example. - Joerg Arndt, Jan 26 2013
a(n+1) is the number of compositions of n avoiding the part 2. - Joerg Arndt, Jul 13 2014
Number of different positive braids with n crossings of 3 strands.
This is a_2(n) in the Doroslovacki reference. Note that there is a typo in the paper in the formula for a_2(n): the upper bound in the inner sum should be "n-i" not "i-1". - Max Alekseyev, Jun 26 2007
a(n) is the number of peakless Motzkin paths of length n-1 with no UHH...HD's starting at level > 0 (here n > 0 and U=(1,1), H=(1,0), D=(1,-1)). Example: a(5)=7 because from all 8 peakless Motzkin paths of length 5 (see A004148) only UUHDD does not qualify. - Emeric Deutsch, Sep 13 2004
Equals the INVERT transform of (1, 0, 1, 1, 1, ...); equivalent to a(n) = a(n-1) + a(n-3) + a(n-4) + ... - Gary W. Adamson, Apr 27 2009
a(n) is the number of length n-1 words on {0,1} such that each string of 1's is followed by a string of at least two 0's. For example, a(5) = 4 because we have: 0000, 0100, 1000, and 1100. - Geoffrey Critzer, Aug 09 2013
a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 0; 0, 1, 1; 1, 0, 0] or [1, 0, 1; 1, 1, 0; 0, 1, 0] or [1, 1, 0; 0, 0, 1; 1, 0, 1] or [1, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
For n >= 2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - Milan Janjic, Mar 07 2015
Apart from the first three terms, the total number of bargraphs of semiperimeter n of height at most two for n >= 2 starts 1, 2, 4, 7, 12, ... - Arnold Knopfmacher, Nov 02 2016
Number of DD-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are DD-equivalent iff the positions of pattern DD are identical in these paths. - Sergey Kirgizov, Apr 08 2018
From Gus Wiseman, Nov 25 2019: (Start)
For n > 0, also the number of subsets of {1, ..., n - 3} such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(3) = 1 through a(7) = 12 subsets are:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {2}
           {1,2}  {3}      {3}
                  {1,2}    {4}
                  {2,3}    {1,2}
                  {1,2,3}  {1,4}
                           {2,3}
                           {3,4}
                           {1,2,3}
                           {2,3,4}
                           {1,2,3,4}
(End)
The two-dimensional version, which counts sets of pairs where, if two pairs are separated by graph-distance 2, then the intermediate pair or pairs are also in the set, is A329871. - Gus Wiseman, Nov 30 2019
a(n+1) is the number of ways to tile a strip of length n with squares, dominoes, and tetrominoes, where the first tile cannot be a domino. - Greg Dresden and Myanna Nash, Aug 18 2020

			From _Joerg Arndt_, Jan 26 2013: (Start)
The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are
  [ 1]  [ 1 1 1 1 1 ]
  [ 2]  [ 1 1 1 2 ]
  [ 3]  [ 1 1 2 1 ]
  [ 4]  [ 1 1 3 ]
  [ 5]  [ 1 2 1 1 ]
  [ 6]  [ 1 3 1 ]
  [ 7]  [ 1 4 ]
  [ 8]  [ 2 1 1 1 ]
  [ 9]  [ 2 1 2 ]
  [10]  [ 3 1 1 ]
  [11]  [ 4 1 ]
  [12]  [ 5 ]
(End)
G.f. = x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 21*x^8 + 37*x^9 + ...

S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]
P. Chinn and S. Heubach, "Compositions of n with no occurrence of k", Congressus Numeratium, 2002, v. 162, pp. 33-51.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Cyclic permutations avoiding patterns in both one-line and cycle forms, arXiv:2312.05145 [math.CO], 2023. See p. 2.
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted quasisymmetric functions and the Hopf algebra of peak functions, arXiv:math/9904105 [math.CO], 1999.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 11.
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.
A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 112.
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Properties of a Ternary Infinite Word, arXiv:2206.01776 [cs.DM], 2022.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Complement Avoidance in Binary Words, arXiv:2209.09598 [math.CO], 2022.
J. Demetrovics et al., On the number of unions in a family of sets, in Combinatorial Math., Proc. 3rd Internat. Conf., Annals NY Acad. Sci., 555 (1989), 150-158.
R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
Nazim Fatès, Biswanath Sethi, and Sukanta Das, On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View, in Reversibility and Universality, Andrew Adamatzky, editor, Emergence, Complexity and Computation Vol. 30. Springer, 2018.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.
R. K. Guy, Letter to N. J. A. Sloane, Feb 1986
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,1,2).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 98
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy, arXiv:2011.08522 [math.CO], 2020.
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=0.
T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 0 peaks.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
Nicolas Ollinger and Jeffrey Shallit, The Repetition Threshold for Rote Sequences, arXiv:2406.17867 [math.CO], 2024.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913.
Bojan Vučković and Miodrag Živković, Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3), ResearchGate, January 2017, p. 3.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1).

Cf. A001608, A004148, A005314, A006498, A011973, A049864, A049853, A078065, A118891, A173022, A176971, A178470, A261041, A303696, A329871, A384153.
Bisection of Padovan sequence A000931.
Partial sums of A005314 shifted 3 times to the right, if we assume A005314(0) = 1.
Compositions without adjacent equal parts are A003242.
Compositions without isolated parts are A114901.
Row sums of A097230(n-2) for n>1.

a005251 n = a005251_list !! n
a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
   (drop 2 $ zipWith (+) a005251_list (tail a005251_list))
-- Reinhard Zumkeller, Dec 28 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-4): n in [1..45]]; // Vincenzo Librandi, Nov 30 2018

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1-x)/(1-2*x + x^2 - x^3) )); // Marius A. Burtea, Oct 24 2019

A005251 := proc(n) option remember; if n <= 2 then n elif n = 3 then 4 else 2*A005251(n - 1) - A005251(n - 2) + A005251(n - 3); fi; end;
A005251:=(-1+z)/(-1+2*z-z**2+z**3); # Simon Plouffe in his 1992 dissertation
a := n -> `if`(n<=1, n, hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4)):
seq(simplify(a(n)), n=0..36); # Peter Luschny, Apr 08 2018

LinearRecurrence[{2,-1,1},{0,1,1},40]  (* Harvey P. Dale, May 05 2011 *)
a[ n_]:= If[n<0, SeriesCoefficient[ -x(1-x)/(1 -x + 2x^2 -x^3), {x, 0, -n}], SeriesCoefficient[ x(1-x)/(1 -2x +x^2 -x^3), {x, 0, n}]] (* Michael Somos, Dec 13 2013 *)
a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n-2] + a[n-3]; Table[a[2 n-1], {n, 1, 20}] (* Rigoberto Florez, Oct 15 2019 *)
Table[If[n==0,0,Length[DeleteCases[Subsets[Range[n-3]],{_,x_,y_,_}/;x+2==y]]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)

Vec((1-x)/(1-2*x+x^2-x^3)+O(x^99)) /* Charles R Greathouse IV, Nov 20 2012 */

{a(n) = if( n<0, polcoeff( -x*(1-x)/(1 -x +2*x^2 -x^3) + x*O(x^-n), -n), polcoeff( x*(1-x)/(1 -2*x +x^2 -x^3) + x*O(x^n), n))} /* Michael Somos, Dec 13 2013 */

[sum( binomial(n-j-1, 2*j) for j in (0..floor((n-1)/3)) ) for n in (0..50)] # G. C. Greubel, Apr 13 2022

a(n) = 2*a(n-1) - a(n-2) + a(n-3).
G.f.: z*(1-z)/(1 - 2*z + z^2 - z^3). - Emeric Deutsch, Sep 13 2004
23*a_n = 3*P_{2n+1} + 7*P_{2n} - 2*P_{2n-1}, where P_n are the Perrin numbers, A001608. - Don Knuth, Dec 09 2008
a(n+1) = Sum_{k=0..n} binomial(n-k, 2k). - Richard L. Ollerton, May 12 2004
From Henry Bottomley, Feb 21 2001: (Start)
a(n) = (Sum_{ja(n) = A005314(n) - A005314(n-1).
a(n) = A049853(n-1) - a(n-1).
a(n) = A005314(n) - a(n-2). (End)
Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1). - Creighton Dement, Dec 21 2004
a(n+2) has g.f. (F_3(-x) + F_2(-x))/(F_4(-x) + F_3(-x)) = 1/(-x+1/(-x+1/(-x+1))) where F_n(x) is the n-th Fibonacci polynomial; see A011973. - Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009
a(n) = A173022(2^(n-2) - 1) for n > 1. - Reinhard Zumkeller, Feb 07 2010
BINOMIAL transform of A176971 is a(n+1). - Michael Somos, Dec 13 2013
a(n) = hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4) for n > 1. - Peter Luschny, Apr 08 2018
G.f.: z/(1-z-z^3-z^4-z^5-...) for the compositions of n-1 avoiding 2. The g.f. for the number of compositions of n avoiding the part k is 1/(1-z-...-z^(k-1) - z^(k+1)-...). - Gregory L. Simay, Sep 09 2018
If p,q,r are the three solutions to x^3 = 2x^2 - x + 1, then a(n) = (p-1)*p^n/((p-q)*(p-r)) + (q-1)*q^n/((q-p)*(q-r)) + (r-1)*r^n/((r-p)*(r-q)). - Greg Dresden and AnXing Yang, Aug 12 2025

A345192 Number of non-alternating compositions of n.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 20, 45, 99, 208, 437, 906, 1862, 3803, 7732, 15659, 31629, 63747, 128258, 257722, 517339, 1037652, 2079984, 4167325, 8346204, 16710572, 33449695, 66944254, 133959021, 268028868, 536231903, 1072737537, 2145905285, 4292486690, 8586035993, 17173742032, 34350108745, 68704342523, 137415168084

Offset: 0

Gus Wiseman, Jun 17 2021

nonn

First differs from A261983 at a(6) = 20, A261983(6) = 18.

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

			The a(2) = 1 through a(6) = 20 compositions:
  (11)  (111)  (22)    (113)    (33)
               (112)   (122)    (114)
               (211)   (221)    (123)
               (1111)  (311)    (222)
                       (1112)   (321)
                       (1121)   (411)
                       (1211)   (1113)
                       (2111)   (1122)
                       (11111)  (1131)
                                (1221)
                                (1311)
                                (2112)
                                (2211)
                                (3111)
                                (11112)
                                (11121)
                                (11211)
                                (12111)
                                (21111)
                                (111111)

Andrew Howroyd, Table of n, a(n) for n = 0..1000

The complement is counted by A025047 (ascend: A025048, descend: A025049).
Dominates A261983 (non-anti-run compositions), ranked by A348612.
These compositions are ranked by A345168, complement A345167.
The case without twins is A348377.
The version for factorizations is A348613.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts alternating compositions with twins.
A344605 counts alternating patterns with twins.
A344654 counts non-twin partitions with no alternating permutation.
A345162 counts normal partitions with no alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
Patterns:
- A128761 avoiding (1,2,3) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000070, A008965, A178470, A238279, A333755, A335126, A344606, A344653, A344740, A345163, A345166, A345169, A345173, A348380.

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!wigQ[#]&]],{n,0,15}]

a(n) = A011782(n) - A025047(n).

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 3, 10, 10, 21, 22, 49, 51, 105, 126, 233, 292, 529, 678, 1181, 1585, 2654, 3654, 6016, 8416, 13606, 19395, 30840, 44517, 70087, 102070, 159304, 233941, 362429, 535520, 825358, 1225117, 1880220, 2801749, 4285086, 6404354, 9769782, 14634907

Offset: 0

Christian G. Bower, Jan 05 2006

nonn

			The 5 compositions of 6 are 3+3, 2+2+2, 2+2+1+1, 1+1+2+2, 1+1+1+1+1+1.
From _Gus Wiseman_, Nov 25 2019: (Start)
The a(2) = 1 through a(9) = 10 compositions:
  (11)  (111)  (22)    (11111)  (33)      (11122)    (44)        (333)
               (1111)           (222)     (22111)    (1133)      (11133)
                                (1122)    (1111111)  (2222)      (33111)
                                (2211)               (3311)      (111222)
                                (111111)             (11222)     (222111)
                                                     (22211)     (1111122)
                                                     (111122)    (1112211)
                                                     (112211)    (1122111)
                                                     (221111)    (2211111)
                                                     (11111111)  (111111111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..4000
N. J. A. Sloane, Transforms

The case of partitions is A007690.
Compositions with no adjacent parts equal are A003242.
Compositions with all multiplicities > 1 are A240085.
Compositions with minimum multiplicity 1 are A244164.
Compositions with at least two adjacent parts equal are A261983.
Cf. A178470, A238130, A274174, A329863.

g:= proc(n, i) option remember; add(b(n-i*j, i), j=2..n/i) end:
b:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(i=l, 0, g(n,i)), i=1..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 29 2019

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Min@@Length/@Split[#]>1&]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)
g[n_, i_] := g[n, i] = Sum[b[n - i*j, i], {j, 2, n/i}] ;
b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[i==l, 0, g[n, i]], {i, 1, n/2}]];
a[n_] := b[n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 23 2021, after Alois P. Heinz *)

A_x(N,k) = { my(x='x+O('x^N), g=1/(1-sum(i=1,N,sum(j=k+1,N, x^(i*j))/(1+ sum(j=k+1,N, x^(i*j)))))); Vec(g)}
A_x(50,1) \\ John Tyler Rascoe, May 17 2024

INVERT(iMOEBIUS(iINVERT(A000012 shifted right 2 places)))

G.f.: A(x,1) is the k = 1 case of A(x,k) = 1/(1 - Sum_{i>0} ( (Sum_{j>k} x^(i*j))/(1 + Sum_{j>k} x^(i*j)) )) where A(x,k) is the g.f. for compositions of n with all run-lengths > k. - John Tyler Rascoe, May 16 2024

A261983 Number of compositions of n such that at least two adjacent parts are equal.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 18, 41, 89, 185, 388, 810, 1670, 3435, 7040, 14360, 29226, 59347, 120229, 243166, 491086, 990446, 1995410, 4016259, 8076960, 16231746, 32599774, 65437945, 131293192, 263316897, 527912140, 1058061751, 2120039885, 4246934012, 8505864640

Offset: 0

Alois P. Heinz, Sep 07 2015

nonn

			a(5) = 9: 311, 113, 221, 122, 2111, 1211, 1121, 1112, 11111.
From _Gus Wiseman_, Jul 07 2020: (Start)
The a(2) = 1 through a(6) = 18 compositions:
  (1,1)  (1,1,1)  (2,2)      (1,1,3)      (3,3)
                  (1,1,2)    (1,2,2)      (1,1,4)
                  (2,1,1)    (2,2,1)      (2,2,2)
                  (1,1,1,1)  (3,1,1)      (4,1,1)
                             (1,1,1,2)    (1,1,1,3)
                             (1,1,2,1)    (1,1,2,2)
                             (1,2,1,1)    (1,1,3,1)
                             (2,1,1,1)    (1,2,2,1)
                             (1,1,1,1,1)  (1,3,1,1)
                                          (2,1,1,2)
                                          (2,2,1,1)
                                          (3,1,1,1)
                                          (1,1,1,1,2)
                                          (1,1,1,2,1)
                                          (1,1,2,1,1)
                                          (1,2,1,1,1)
                                          (2,1,1,1,1)
                                          (1,1,1,1,1,1)
(End)

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

Column k=1 of A261981.
Cf. A011782, A262046.
The complement A003242 counts anti-runs.
Sum of positive-indexed terms of row n of A106356.
Row sums of A131044.
The (1,1,1) matching case is A335464.
Strict compositions are A032020.
Compositions with adjacent parts coprime are A167606.
Compositions with equal parts contiguous are A274174.
Cf. A114901, A178470, A242882, A244164, A325534, A335448, A335452.

b:= proc(n, i) option remember; `if`(n=0, 0, add(
      `if`(i=j, ceil(2^(n-j-1)), b(n-j, j)), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,x_,_}]&]],{n,0,10}] (* Gus Wiseman, Jul 06 2020 *)
b[n_, i_] := b[n, i] = If[n == 0, 0, Sum[If[i == j, Ceiling[2^(n-j-1)], b[n-j, j]], {j, 1, n}]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 20 2023, after Alois P. Heinz's Maple code *)

a(n) ~ 2^(n-1). - Vaclav Kotesovec, Sep 08 2015

a(n) = A011782(n) - A003242(n). - Emeric Deutsch, Jul 03 2020

A342098 Number of (necessarily strict) integer partitions of n with all adjacent parts having quotients > 2.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 23, 25, 26, 28, 31, 33, 35, 38, 40, 42, 45, 48, 51, 55, 58, 61, 65, 68, 72, 77, 81, 85, 90, 94, 98, 104, 109, 114, 121, 127, 132, 139, 146

Offset: 1

Gus Wiseman, Mar 04 2021

nonn

The decapitation of such a partition (delete the greatest part) is term-wise less than its negated first-differences.

			The a(1) = 1 through a(16) = 8 partitions (A..G = 10..16):
  1  2  3  4   5   6   7   8   9   A   B    C    D    E    F    G
           31  41  51  52  62  72  73  83   93   94   A4   B4   B5
                       61  71  81  82  92   A2   A3   B3   C3   C4
                                   91  A1   B1   B2   C2   D2   D3
                                       731  831  C1   D1   E1   E2
                                                 931  941  A41  F1
                                                      A31  B31  B41
                                                                C31

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..3000

The version allowing equality is A000929.
The case of equality (all adjacent parts having quotient 2) is A154402.
The multiplicative version is A342083.
The version with all quotients <= 2 is A342094 (strict: A342095).
The version with all quotients < 2 is A342096 (strict: A342097).
A000009 counts strict partitions.
A003114 counts partitions with adjacent parts differing by more than 1.
A034296 counts partitions with adjacent parts differing by at most 1.
Cf. A027193, A001055, A001227, A003242, A167606, A178470, A337135, A342084, A342085.

Table[Length[Select[IntegerPartitions[n],And@@Thread[Differences[-#]>Rest[#]]&]],{n,30}]

A178472 Number of compositions (ordered partitions) of n where the gcd of the part sizes is not 1.

Original entry on oeis.org

0, 1, 1, 2, 1, 5, 1, 8, 4, 17, 1, 38, 1, 65, 19, 128, 1, 284, 1, 518, 67, 1025, 1, 2168, 16, 4097, 256, 8198, 1, 16907, 1, 32768, 1027, 65537, 79, 133088, 1, 262145, 4099, 524408, 1, 1056731, 1, 2097158, 16636, 4194305, 1, 8421248, 64, 16777712, 65539

Offset: 1

Franklin T. Adams-Watters, May 28 2010

nonn

Of course, all part sizes must be greater than 1; that condition alone gives the Fibonacci numbers, which is thus an upper bound.

Also the number of periodic compositions of n, where a sequence is periodic if its cyclic rotations are not all different. Also compositions with non-relatively prime run-lengths. - Gus Wiseman, Nov 10 2019

			For n=6, we have 5 compositions: <6>, <4,2>, <2,4>, <2,2,2>, and <3,3>.
From _Gus Wiseman_, Nov 10 2019: (Start)
The a(2) = 1 through a(9) = 4 non-relatively prime compositions:
  (2)  (3)  (4)    (5)  (6)      (7)  (8)        (9)
            (2,2)       (2,4)         (2,6)      (3,6)
                        (3,3)         (4,4)      (6,3)
                        (4,2)         (6,2)      (3,3,3)
                        (2,2,2)       (2,2,4)
                                      (2,4,2)
                                      (4,2,2)
                                      (2,2,2,2)
The a(2) = 1 through a(9) = 4 periodic compositions:
  11  111  22    11111  33      1111111  44        333
           1111         222              1313      121212
                        1212             2222      212121
                        2121             3131      111111111
                        111111           112112
                                         121121
                                         211211
                                         11111111
The a(2) = 1 through a(9) = 4 compositions with non-relatively prime run-lengths:
  11  111  22    11111  33      1111111  44        333
           1111         222              1133      111222
                        1122             2222      222111
                        2211             3311      111111111
                        111111           111122
                                         112211
                                         221111
                                         11111111
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Hunki Baek, Sejeong Bang, Dongseok Kim, and Jaeun Lee, A bijection between aperiodic palindromes and connected circulant graphs, arXiv:1412.2426 [math.CO], 2014. See Table 2.

Cf. A000045, A008683, A011782, A178470.
Periodic binary words are A152061.
Cf. A000740, A027375, A059966, A121016, A329140, A329145.

A178472 := n -> (2^n - add(mobius(n/d)*2^d, d in divisors(n)))/2:
seq(A178472(n), n=1..51); # Peter Luschny, Jan 21 2018

Table[2^(n - 1) - DivisorSum[n, MoebiusMu[n/#]*2^(# - 1) &], {n, 51}] (* Michael De Vlieger, Jan 20 2018 *)

vector(60,n,2^(n-1)-sumdiv(n,d,2^(d-1)*moebius(n/d)))

from sympy import mobius, divisors
def A178472(n): return -sum(mobius(n//d)<Chai Wah Wu, Sep 21 2024

a(n) = Sum_{d|n & d

a(n) = 2^(n-1) - A000740(n).

a(n) = A152061(n)/2. - George Beck, Jan 20 2018

a(p) = 1 for p prime. - Chai Wah Wu, Sep 21 2024

Ambiguous term a(0) removed by Max Alekseyev, Jan 02 2012

A342094 Number of integer partitions of n with no adjacent parts having quotient > 2.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 13, 16, 21, 27, 37, 44, 59, 75, 94, 117, 153, 186, 238, 296, 369, 458, 573, 701, 870, 1068, 1312, 1601, 1964, 2384, 2907, 3523, 4270, 5159, 6235, 7491, 9021, 10819, 12964, 15494, 18517, 22049, 26260, 31195, 37020, 43851, 51906, 61290

Offset: 1

Gus Wiseman, Mar 02 2021

nonn

The decapitation of such a partition (delete the greatest part) is term-wise greater than or equal to its negated first-differences.

			The a(1) = 1 through a(8) = 13 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (211)   (221)    (42)      (322)      (53)
                    (1111)  (2111)   (222)     (421)      (332)
                            (11111)  (321)     (2221)     (422)
                                     (2211)    (3211)     (2222)
                                     (21111)   (22111)    (3221)
                                     (111111)  (211111)   (4211)
                                               (1111111)  (22211)
                                                          (32111)
                                                          (221111)
                                                          (2111111)
                                                          (11111111)

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..250

The version with no adjacent parts having quotient < 2 is A000929.
The case of equality (all adjacent parts having quotient 2) is A154402.
A strong multiplicative version is A342083 or A342084.
The multiplicative version is A342085, with reciprocal version A337135.
The strict case is A342095.
The version with all adjacent parts having quotient < 2 is A342096, with strict case A342097.
The version with all adjacent parts having quotient > 2 is A342098.
The Heinz numbers of these partitions are listed by A342191.
A000009 counts strict partitions.
A003114 counts partitions with adjacent parts differing by more than 1.
A034296 counts partitions with adjacent parts differing by at most 1.
A038548 counts inferior (or superior) divisors, listed by A161906.
A161908 lists superior prime divisors.
Cf. A001055, A001227, A003242, A027193, A167606, A178470, A253784, A341591.

Table[Length[Select[IntegerPartitions[n],And@@Thread[Differences[-#]<=Rest[#]]&]],{n,30}]

A348612 Numbers k such that the k-th composition in standard order is not an anti-run, i.e., has adjacent equal parts.

Original entry on oeis.org

3, 7, 10, 11, 14, 15, 19, 21, 23, 26, 27, 28, 29, 30, 31, 35, 36, 39, 42, 43, 46, 47, 51, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 67, 71, 73, 74, 75, 78, 79, 83, 84, 85, 86, 87, 90, 91, 92, 93, 94, 95, 99, 100, 103, 106, 107, 110, 111, 112, 113, 114, 115, 116

Offset: 1

Gus Wiseman, Nov 03 2021

nonn

First differs from A345168 in lacking 37, corresponding to the composition (3,2,1).

A composition of n is a finite sequence of positive integers summing to n. 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.

			The terms and corresponding standard compositions begin:
     3: (1,1)          35: (4,1,1)        61: (1,1,1,2,1)
     7: (1,1,1)        36: (3,3)          62: (1,1,1,1,2)
    10: (2,2)          39: (3,1,1,1)      63: (1,1,1,1,1,1)
    11: (2,1,1)        42: (2,2,2)        67: (5,1,1)
    14: (1,1,2)        43: (2,2,1,1)      71: (4,1,1,1)
    15: (1,1,1,1)      46: (2,1,1,2)      73: (3,3,1)
    19: (3,1,1)        47: (2,1,1,1,1)    74: (3,2,2)
    21: (2,2,1)        51: (1,3,1,1)      75: (3,2,1,1)
    23: (2,1,1,1)      53: (1,2,2,1)      78: (3,1,1,2)
    26: (1,2,2)        55: (1,2,1,1,1)    79: (3,1,1,1,1)
    27: (1,2,1,1)      56: (1,1,4)        83: (2,3,1,1)
    28: (1,1,3)        57: (1,1,3,1)      84: (2,2,3)
    29: (1,1,2,1)      58: (1,1,2,2)      85: (2,2,2,1)
    30: (1,1,1,2)      59: (1,1,2,1,1)    86: (2,2,1,2)
    31: (1,1,1,1,1)    60: (1,1,1,3)      87: (2,2,1,1,1)

Constant run compositions are counted by A000005, ranked by A272919.
Counting these compositions by sum and length gives A131044.
These compositions are counted by A261983.
The complement is A333489, counted by A003242.
The non-alternating case is A345168, complement A345167.
A011782 counts compositions, strict A032020.
A238279 counts compositions by sum and number of maximal runs.
A274174 counts compositions with equal parts contiguous.
A336107 counts non-anti-run permutations of prime factors.
A345195 counts non-alternating anti-runs, ranked by A345169.
For compositions in standard order (rows of A066099):
- Length is A000120.
- Sum is A070939
- Maximal runs are counted by A124767.
- Strict compositions are ranked by A233564.
- Maximal anti-runs are counted by A333381.
- Runs-resistance is A333628.
Cf. A029931, A048793, A106356, A114901, A167606, A178470, A228351, A244164, A262046, A335452, A335464.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[100],MatchQ[stc[#],{_,x_,x_,_}]&]

A357182 Number of integer compositions of n with the same length as their alternating sum.

Original entry on oeis.org

1, 1, 0, 0, 1, 3, 1, 4, 6, 20, 13, 48, 50, 175, 141, 512, 481, 1719, 1491, 5400, 4929, 17776, 15840, 57420, 52079, 188656, 169989, 617176, 559834, 2033175, 1842041, 6697744, 6085950, 22139780, 20123989, 73262232, 66697354, 242931321, 221314299, 806516560

Offset: 0

Gus Wiseman, Sep 28 2022

nonn

A composition of n is a finite sequence of positive integers summing to n.

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			The a(1) = 1 through a(8) = 6 compositions:
  (1)  (31)  (113)  (42)  (124)  (53)
             (212)        (223)  (1151)
             (311)        (322)  (2141)
                          (421)  (3131)
                                 (4121)
                                 (5111)

For product instead of length we have A114220.
For sum equal to twice alternating sum we have A262977, ranked by A348614.
For product equal to sum we have A335405, ranked by A335404.
For absolute value we have A357183.
These compositions are ranked by A357184.
The case of partitions is A357189.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A025047 counts alternating compositions, ranked by A345167.
A124754 gives alternating sums of standard compositions.
A238279 counts compositions by sum and number of maximal runs.
A261983 counts non-anti-run compositions.
A357136 counts compositions by alternating sum.
Cf. A000120, A032020, A070939, A106356, A114901, A131044, A178470, A233564, A242882, A262046, A301987.

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[#]==ats[#]&]],{n,0,15}]

a(21)-a(39) from Alois P. Heinz, Sep 29 2022

Showing 1-10 of 26 results. Next

cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A345192 Number of non-alternating compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A261983 Number of compositions of n such that at least two adjacent parts are equal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342098 Number of (necessarily strict) integer partitions of n with all adjacent parts having quotients > 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A178472 Number of compositions (ordered partitions) of n where the gcd of the part sizes is not 1.