A045690 -id:A045690 - cp's OEIS frontend

A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.

1, 2, 2, 4, 6, 12, 20, 40, 74, 148, 284, 568, 1116, 2232, 4424, 8848, 17622, 35244, 70340, 140680, 281076, 562152, 1123736, 2247472, 4493828, 8987656, 17973080, 35946160, 71887896, 143775792, 287542736, 575085472, 1150153322, 2300306644, 4600578044, 9201156088

Offset: 0

N. J. A. Sloane

This is the number of binary words w of length n such that there is no nonempty word x, different from w, which is both a prefix and a suffix of w. - N. J. A. Sloane, Nov 09 2012
Many authors use the term "unbordered" for "bifix-free". The Lothaire (1997) reference refers to bifix-free words as primary words (Chapter 8). - David Callan, Sep 25 2006
Also the number of binary "prime palstars" of length 2n (Rampersad, Shallit, & Wang 2011). - Jeffrey Shallit, Aug 14 2014

			Bi-fix free words of lengths 1 through 4:
0, 1
10, 01
100, 110, 011, 001
1000, 1100, 1110, 0111, 0011, 0001.

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 28.
M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 1997, see p. 153.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..3323 (first 501 terms from T. D. Noe)
E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani, Cross-bifix-free sets in two dimensions, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.
S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.
G. Blom, Problem 94-20: Overlapping binary sequences, SIAM Review 37 (1995), 619-620.
Joshua Cooper and Danny Rorabaugh, Asymptotic Density of Zimin Words, arXiv preprint arXiv:1510.03917 [math.CO], 2015-2016.
Daniel Gabric and Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
D. J. Greaves and S. J. Montgomery-Smith, Unforgeable Marker Sequences.
L. J. Guibas and A. M. Odlyzko, Periods in Strings, Journal of Combinatorial Theory A 30 (1981) 19-42. Their L_n(0) is A003000(n).
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154, see p. 143.
T. Harju and D. Nowotka, Border correlation of binary words.
P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706. [pdf]
Jakob Radoszewski, Wojciech Rytter, and Tomasz Waleń, Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words, Int'l Symp. String Proc. Info. Retrieval (2024), Springer, Cham, LNCS Vol. 14899, 257-271.
N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, Info. Proc. Letters 111 (2011), 420-422. - _Jeffrey Shallit_, Aug 14 2014
N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, arXiv:1008.2440 [cs.FL], 2010.
D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372 [math.CO], 2015.
Sarah Nibs, Java program for this sequence and A122536.

Equals 2 * A045690 for n > 0. Complement gives A094536.

Cf. A019308, A019309, A094537, A242430.

A[0]:= 1:
for n from 1 to 100 do
if n::odd then A[n]:= 2*A[n-1] else A[n]:= 2*A[n-1]-A[n/2] fi
od:
seq(A[n],n=0..100); # Robert Israel, Aug 14 2014

a[0]=1;a[n_]:=a[n]=2*a[n-1]-(1+(-1)^n)/2*a[Floor[n/2]]; Table[a[n], {n, 0, 34}]
a[0]=1; a[n_]:=a[n]=2*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

a(2*n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n).
a(n)/2^n converges to A242430.
a(0)=1; a(n)=2*a(n-1)-(1/2)*(1+(-1)^n)*a([n/2]). - Farideh Firoozbakht, Jun 10 2004
G.f.: g(x) satisfies (1-2*x)*g(x) = 2 - g(x^2). - Robert Israel, Jan 12 2015

New description and reference from Jeffrey Shallit, Sep 15 1996
Additional comments from Torsten.Sillke(AT)lhsystems.com, Jan 17 2001
More terms from Farideh Firoozbakht, Jun 10 2004

A040039 First differences of A033485; also A033485 with terms repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

N. J. A. Sloane and J. H. Conway

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009
Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.
Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018
From Gus Wiseman, Apr 06 2021: (Start)
This sequence counts both of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:
  {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
            {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
                          {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
                                        {3,7}    {3,8}    {3,9}
                                        {1,3,7}  {1,3,8}  {4,9}
                                                          {1,3,9}
                                                          {1,4,9}
2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).
Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:
  1  11  21   211   221    2211    421      4211      4221
         111  1111  2111   21111   2221     22211     22221
                    11111  111111  22111    221111    42111
                                   211111   2111111   222111
                                   1111111  11111111  2211111
                                                      21111111
                                                      111111111
(End)

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A000123.
Cf. A088567, A089054.
Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
The equal case is A001511.
The reflected version is A045690.
The unequal (anti-run) version is A045691.
A000929 counts partitions with all adjacent parts x >= 2y.
A002843 counts compositions with all adjacent parts x <= 2y.
A018819 counts partitions into powers of 2.
A154402 counts partitions with all adjacent parts x = 2y.
A274199 counts compositions with all adjacent parts x < 2y.
A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
Cf. A000009, A003114, A003242, A224957, A342191, A342330.

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]
From Joerg Arndt, Oct 02 2013: (Start)
G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
a(n) = 1/2 * A018819(n+2).
(End)
a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015
Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018

A350842 Number of integer partitions of n with no difference -2.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 9, 12, 16, 24, 30, 40, 54, 69, 89, 118, 146, 187, 239, 297, 372, 468, 575, 711, 880, 1075, 1314, 1610, 1947, 2359, 2864, 3438, 4135, 4973, 5936, 7090, 8466, 10044, 11922, 14144, 16698, 19704, 23249, 27306, 32071, 37639, 44019, 51457, 60113

Offset: 0

Gus Wiseman, Jan 20 2022

nonn

			The a(1) = 1 through a(7) = 12 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (211)   (41)     (51)      (52)
                    (1111)  (221)    (222)     (61)
                            (2111)   (321)     (322)
                            (11111)  (411)     (511)
                                     (2211)    (2221)
                                     (21111)   (3211)
                                     (111111)  (4111)
                                               (22111)
                                               (211111)
                                               (1111111)

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

Heinz number rankings are in parentheses below.
The version for no difference 0 is A000009.
The version for subsets of prescribed maximum is A005314.
The version for all differences < -2 is A025157, non-strict A116932.
The version for all differences > -2 is A034296, strict A001227.
The opposite version is A072670.
The version for no difference -1 is A116931 (A319630), strict A003114.
The multiplicative version is A350837 (A350838), strict A350840.
The strict case is A350844.
The complement for quotients is counted by A350846 (A350845).
A000041 = integer partitions.
A027187 = partitions of even length.
A027193 = partitions of odd length (A026424).
A323092 = double-free partitions (A320340), strict A120641.
A325534 = separable partitions (A335433).
A325535 = inseparable partitions (A335448).
A350839 = partitions with a gap and conjugate gap (A350841).
Cf. A000070, A000929, A001511, A003242, A007359, A018819, A040039, A045690, A045691, A101417, A154402, A323093.

Table[Length[Select[IntegerPartitions[n],FreeQ[Differences[#],-2]&]],{n,0,30}]

A002083 Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 11, 22, 42, 84, 165, 330, 654, 1308, 2605, 5210, 10398, 20796, 41550, 83100, 166116, 332232, 664299, 1328598, 2656866, 5313732, 10626810, 21253620, 42505932, 85011864, 170021123, 340042246, 680079282, 1360158564

Offset: 1

N. J. A. Sloane

Number of compositions p(1) + p(2) + ... + p(k) = n of n into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j), see example - Claude Lenormand (claude.lenormand(AT)free.fr), Jan 29 2001 (clarified by Joerg Arndt, Feb 01 2013)
a(n) is the number of sequences (b(1),b(2),...) of unspecified length satisfying b(1) = 1, 1 <= b(i) <= 1 + Sum[b(j),{j,i-1}] for i>=2, Sum[b(i)] = n-1. For example, a(5) = 3 counts (1, 1, 1, 1), (1, 2, 1), (1, 1, 2). These sequences are generated by the Mathematica code below. - David Callan, Nov 02 2005
a(n+1) is the number of padded compositions (d_1,d_2,...,d_n) of n satisfying d_i <= i for all i. A padded composition of n is obtained from an ordinary composition (c_1,c_2,...,c_r) of n (r >= 1, each c_i >= 1, Sum_{i=1..r} c_i = n) by inserting c_i - 1 zeros immediately after each c_i. Thus (3,1,2) -> (3,0,0,1,2,0) is a padded composition of 6 and a padded composition of n has length n. For example, with n=4, a(5) counts (1,1,1,1), (1,1,2,0), (1,2,0,1). - David Callan, Feb 04 2006
From David Callan, Sep 25 2006: (Start)
a(n) is the number of ordered trees on n edges in which (i) every node (= non-root non-leaf vertex) has at least 2 children and (ii) each leaf is either the leftmost or rightmost child of its parent.
For example, a(4)=2 counts
    ./\.../\
    /\...../\,
  and a(5)=3 counts
    .|.......|....../|\
    / \...../ \...../ \
    ../\.../\.
(End)
Starting with offset 2 = eigensequence of triangle A101688 and row sums of triangle A167948. - Gary W. Adamson, Nov 15 2009
If we remove the condition that a(2) = 1, then the resulting sequence is A045690 minus the first term. - Chai Wah Wu, Nov 08 2022

			From _Joerg Arndt_, Feb 01 2013: (Start)
The a(7) = 11 compositions p(1) + p(2) + ... + p(k) = 7 of 7 into positive parts p(i) with p(1)=1 and p(k) <= Sum_{j=1..k-1} p(j) are
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 1 2 ]
[ 3]  [ 1 1 1 1 2 1 ]
[ 4]  [ 1 1 1 1 3 ]
[ 5]  [ 1 1 1 2 1 1 ]
[ 6]  [ 1 1 1 2 2 ]
[ 7]  [ 1 1 1 3 1 ]
[ 8]  [ 1 1 2 1 1 1 ]
[ 9]  [ 1 1 2 1 2 ]
[10]  [ 1 1 2 2 1 ]
[11]  [ 1 1 2 3 ]
(End)

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.28.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 1..3325 (first 200 terms from T. D. Noe)
Magnus Aspenberg and Rodrigo Perez, Control of cancellations that restrain the growth of a binomial recursion, arXiv:1006.1340 [math.CO], 2010. Mentions this sequence.
P. Capell and T. V. Narayana, On knock-out tournaments, Canad. Math. Bull. 13 1970 105-109.
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
G. Kreweras, and P. Moszkowski, A new enumerative property of the Narayana numbers, Journal of statistical planning and inference 14.1 (1986): 63-67.
D. Levin, L. Pudwell, M. Riehl and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
J. W. Moon, R. K. Guy and N. J. A. Sloane, Correspondence, 1988
T. V. Narayana, Quelques résultats relatifs aux tournois "knock-out" et leurs applications aux comparaisons aux paires, C. R. Acad. Sci. Paris, Series A-B 267 1968 A32-A33.
T. V. Narayana and J. Zidek, Contributions to the theory of tournaments I, Cahiers du Bur. Univ. de Rech. Oper., 13 (1969), 1-18. [MR 0256734, 41 #1390]
John Riordan and N. J. A. Sloane, Correspondence, 1974
M. A. Stern, 5. Aufgaben., Journal für die reine und angewandte Mathematik (Crelle's journal), volume 18, 1838, p. 100.
Mauro Torelli, Increasing integer sequences and Goldbach's conjecture, RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 40:2 (2006), pp. 107-121.
B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84
B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint.
Bayard Edmund Wynne and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.
Index entries for "core" sequences

Cf. A045690. A058222 gives sums of words.
Cf. A001045, A002487, A101688, A167948.
Cf. A242729.
Bisections: A245094, A259858.

a002083 n = a002083_list !! (n-1)
a002083_list = 1 : f [1] where
   f xs = x : f (x:xs) where x = sum $ take (div (1 + length xs) 2) xs
-- Reinhard Zumkeller, Dec 27 2011

A002083 := proc(n) option remember; if n<=3 then 1 elif n mod 2 = 0 then 2*procname(n-1) else 2*procname(n-1)-procname((n-1)/2); end if; end proc:
a := proc(n::integer) # A002083 Narayana-Zidek-Capell numbers: a(2n)=2a(2n-1), a(2n+1)=2a(2n)-a(n). local k; option remember; if n = 0 then 1 else add(K(n-k+1, k)*procname(n - k), k = 1 .. n); #else add(K((n-k)!, k!)*procname(n - k), k = 1 .. n); end if end proc; K := proc(n::integer, k::integer) local KC; if 0 <= k and k <= n then KC := 1 else KC := 0 end if; end proc; # Thomas Wieder, Jan 13 2008

a[1] = 1; a[n_] := a[n] = Sum[a[k], {k, n/2, n-1} ]; Table[ a[n], {n, 2, 70, 2} ] (* Robert G. Wilson v, Apr 22 2001 *)
bSequences[1]={ {1} }; bSequences[n_]/;n>=2 := bSequences[n] = Flatten[Table[Map[Join[ #, {i}]&, bSequences[n-i]], {i, Ceiling[n/2]}], 1] (* David Callan *)
a=ConstantArray[0,20]; a[[1]]=1; a[[2]]=1; Do[If[EvenQ[n],a[[n]]=2a[[n-1]],a[[n]]=2a[[n-1]]-a[[(n-1)/2]]];,{n,3,20}]; a (* Vaclav Kotesovec, Nov 19 2012 *)

PARI
```
a(n)=if(n<3,n>0,2*a(n-1)-(n%2)*a(n\2))
```

a(n)=local(A=1+x);for(i=1,n,A=(1-x-x^2*subst(A,x,x^2+O(x^n)))/(1-2*x));polcoeff(A,n) \\ Paul D. Hanna, Mar 17 2010

from functools import lru_cache
@lru_cache(maxsize=None)
def A002083(n): return 1 if n <=3 else (A002083(n-1)<<1)-(A002083(n>>1) if n&1 else 0) # Chai Wah Wu, Nov 07 2022

a(1)=1, else a(n) is sum of floor(n/2) previous terms.
Conjecture: lim_{n->oo} a(n)/2^(n-3) = a constant ~0.633368 (=2*A242729). - Gerald McGarvey, Jul 18 2004
First column of A155092. - Mats Granvik, Jan 20 2009
a(n+2) = A037254(n,1) = A037254(n,floor(n/2)+1). - Reinhard Zumkeller, Nov 18 2012
Limit is equal to 0.633368347305411640436713144616576659... = 2*Atkinson-Negro-Santoro constant = 2*A242729, see Finch's book, chapter 2.28 (Erdős' Sum-Distinct Set Constant), pp. 189, 552. - Vaclav Kotesovec, Nov 19 2012
a(n) is the permanent of the (n-1) X (n-1) matrix with (i, j) entry = 1 if i-1 <= j <= 2*i-1 and = 0 otherwise. - David Callan, Nov 02 2005
a(n) = Sum_{k=1..n} K(n-k+1, k)*a(n-k), where K(n,k) = 1 if 0 <= k AND k <= n and K(n,k)=0 else. (Several arguments to the K-coefficient K(n,k) can lead to the same sequence. For example, we get A002083 also from a(n) = Sum_{k=1..n} K((n-k)!,k!)*a(n-k), where K(n,k) = 1 if 0 <= k <= n and 0 else. See also the comment to a similar formula for A002487.) - Thomas Wieder, Jan 13 2008
G.f. satisfies: A(x) = (1-x - x^2*A(x^2))/(1-2x). - Paul D. Hanna, Mar 17 2010

Definition clarified by Chai Wah Wu, Nov 08 2022

A342083 Number of chains of strictly inferior divisors from n to 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 2, 4, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 6, 1, 3, 2, 3, 1, 5, 2, 4, 2, 2, 1, 7, 1, 2, 3, 3, 2, 5, 1, 3, 2, 4, 1, 8, 1, 2, 3, 3, 2, 5, 1, 6, 2, 2, 1, 7, 2, 2, 2

Offset: 1

Gus Wiseman, Feb 28 2021

nonn

We define a divisor d|n to be strictly inferior if d < n/d. Strictly inferior divisors are counted by A056924 and listed by A341674.
These chains have first-quotients (in analogy with first-differences) that are term-wise > their decapitation (maximum element removed). Equivalently, x > y^2 for all adjacent x, y. For example, the divisor chain q = 60/6/2/1 has first-quotients (10,3,2), which are > (6,2,1), so q is counted under a(60).
Also the number of factorizations of n where each factor is greater than the product of all previous factors.

			The a(n) chains for n = 2, 6, 12, 24, 42, 48, 60, 72:
  2/1  6/1    12/1    24/1    42/1      48/1      60/1      72/1
       6/2/1  12/2/1  24/2/1  42/2/1    48/2/1    60/2/1    72/2/1
              12/3/1  24/3/1  42/3/1    48/3/1    60/3/1    72/3/1
                      24/4/1  42/6/1    48/4/1    60/4/1    72/4/1
                              42/6/2/1  48/6/1    60/5/1    72/6/1
                                        48/6/2/1  60/6/1    72/8/1
                                                  60/6/2/1  72/6/2/1
                                                            72/8/2/1
The a(n) factorizations for n = 2, 6, 12, 24, 42, 48, 60, 72:
  2  6    12   24    42     48     60      72
     2*3  2*6  3*8   6*7    6*8    2*30    8*9
          3*4  4*6   2*21   2*24   3*20    2*36
               2*12  3*14   3*16   4*15    3*24
                     2*3*7  4*12   5*12    4*18
                            2*3*8  6*10    6*12
                                   2*3*10  2*4*9
                                           2*3*12

Amiram Eldar, Table of n, a(n) for n = 1..10000

The restriction to powers of 2 is A040039.
Not requiring strict inferiority gives A074206 (ordered factorizations).
The weakly inferior version is A337135.
The strictly superior version is A342084.
The weakly superior version is A342085.
The additive version is A342098, or A000929 allowing equality.
A000005 counts divisors.
A001055 counts factorizations.
A003238 counts chains of divisors summing to n-1, with strict case A122651.
A038548 counts inferior (or superior) divisors.
A056924 counts strictly inferior (or strictly superior) divisors.
A067824 counts strict chains of divisors starting with n.
A167865 counts strict chains of divisors > 1 summing to n.
A207375 lists central divisors.
A253249 counts strict chains of divisors.
A334996 counts ordered factorizations by product and length.
A334997 counts chains of divisors of n by length.
A342086 counts chains of divisors with strictly increasing quotients > 1.
- Inferior: A033676, A066839, A072499, A161906.
- Superior: A033677, A070038, A161908.
- Strictly Inferior: A060775, A070039, A333806, A341674.
- Strictly Superior: A048098, A064052, A140271, A238535, A341673.
Cf. A000203, A001248, A002033, A006530, A018819, A020639, A045690, A337105, A342087, A342094, A342095, A342096, A342097.

cen[n_]:=If[n==1,{{1}},Prepend[#,n]&/@Join@@cen/@Select[Divisors[n],#

G.f.: x + Sum_{k>=1} a(k) * x^(k*(k + 1)) / (1 - x^k). - Ilya Gutkovskiy, Nov 03 2021

A342084 Number of chains of distinct strictly superior divisors starting with n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 4, 2, 2, 1, 9, 1, 2, 2, 4, 1, 7, 1, 6, 2, 2, 2, 10, 1, 2, 2, 9, 1, 6, 1, 4, 4, 2, 1, 19, 1, 4, 2, 4, 1, 8, 2, 9, 2, 2, 1, 20, 1, 2, 4, 10, 2, 6, 1, 4, 2, 7, 1, 29, 1, 2, 4, 4, 2, 6, 1, 19, 3, 2, 1, 19, 2

Offset: 1

Gus Wiseman, Feb 28 2021

nonn

We define a divisor d|n to be strictly superior if d > n/d. Strictly superior divisors are counted by A056924 and listed by A341673.
These chains have first-quotients (in analogy with first-differences) that are term-wise < their decapitation (maximum element removed). Equivalently, x < y^2 for all adjacent x, y. For example, the divisor chain q = 30/6/3 has first-quotients (5,2), which are < (6,3), so q is counted under a(30).
Also the number of ordered factorizations of n where each factor is less than the product of all previous factors.

			The a(n) chains for n = 2, 6, 12, 16, 24, 30, 32, 36:
  2  6    12      16      24         30       32         36
     6/3  12/4    16/8    24/6       30/6     32/8       36/9
          12/6    16/8/4  24/8       30/10    32/16      36/12
          12/6/3          24/12      30/15    32/8/4     36/18
                          24/6/3     30/6/3   32/16/8    36/12/4
                          24/8/4     30/10/5  32/16/8/4  36/12/6
                          24/12/4    30/15/5             36/18/6
                          24/12/6                        36/18/9
                          24/12/6/3                      36/12/6/3
                                                         36/18/6/3
The a(n) ordered factorizations for n = 2, 6, 12, 16, 24, 30, 32, 36:
  2  6    12     16     24       30     32       36
     3*2  4*3    8*2    6*4      6*5    8*4      9*4
          6*2    4*2*2  8*3      10*3   16*2     12*3
          3*2*2         12*2     15*2   4*2*4    18*2
                        3*2*4    3*2*5  8*2*2    4*3*3
                        4*2*3    5*2*3  4*2*2*2  6*2*3
                        4*3*2    5*3*2           6*3*2
                        6*2*2                    9*2*2
                        3*2*2*2                  3*2*2*3
                                                 3*2*3*2

Amiram Eldar, Table of n, a(n) for n = 1..10000

The restriction to powers of 2 is A045690, with reciprocal version A040039.
The inferior version is A337135.
The strictly inferior version is A342083.
The superior version is A342085.
The additive version allowing equality is A342094 or A342095.
The additive version is A342096 or A342097.
A000005 counts divisors.
A001055 counts factorizations.
A003238 counts divisibility chains summing to n-1, with strict case A122651.
A038548 counts inferior (or superior) divisors.
A056924 counts strictly inferior (or strictly superior) divisors.
A067824 counts strict chains of divisors starting with n.
A074206 counts strict chains of divisors from n to 1 (also ordered factorizations).
A167865 counts strict chains of divisors > 1 summing to n.
A207375 lists central divisors.
A253249 counts strict chains of divisors.
A334996 counts ordered factorizations by product and length.
A334997 counts chains of divisors of n by length.
- Inferior: A033676, A063962, A066839, A072499, A161906.
- Superior: A033677, A070038, A161908, A341591.
- Strictly Inferior: A060775, A070039, A333806, A341674.
- Strictly Superior: A064052/A048098, A140271, A238535, A341642, A341673.
Cf. A000203, A000929, A001248, A006530, A018819, A020639, A169594, A337105, A342098.

ceo[n_]:=Prepend[Prepend[#,n]&/@Join@@ceo/@Select[Most[Divisors[n]],#>n/#&],{n}];
Table[Length[ceo[n]],{n,100}]

a(2^n) = A045690(n).

A093371 Start with any initial string of n numbers s(1), ..., s(n), with s(1) = 2, other s(i)'s = 2 or 3 (so there are 2^(n-1) starting strings). The rule for extending the string is this as follows: To get s(n+1), write the string s(1)s(2)...s(n) as xy^k for words x and y (where y has positive length) and k is maximized, i.e., k = the maximal number of repeating blocks at the end of the sequence. Then a(n) = number of starting strings for which k = 1.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 74, 143, 286, 562, 1124, 2230, 4460, 8884, 17768, 35465, 70930, 141720, 283440, 566600, 1133200, 2265843, 4531686, 9062261, 18124522, 36246826, 72493652, 144982872

Offset: 1

N. J. A. Sloane, Apr 28 2004

nonn

See A122536 for many more terms. - N. J. A. Sloane, Oct 25 2012

F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence, J. Integer Sequences, Vol. 10 (2007), #07.1.2.
F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane and Allan Wilks, A Slow-Growing Sequence Defined by an Unusual Recurrence [pdf, ps].
Index entries for sequences related to curling numbers

Cf. A093370, A093369, A090822, A216955, A216956.
Equals A122536/2. - N. J. A. Sloane, Sep 25 2012
Different from, but easily confused with, A007148 and A045690.

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

More terms from N. J. A. Sloane, Sep 26 2012

A224957 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) <= 2p(j-1) and p(j-1) <= 2p(j).

Original entry on oeis.org

1, 1, 2, 4, 6, 11, 19, 31, 54, 92, 154, 266, 454, 771, 1319, 2249, 3834, 6550, 11176, 19069, 32558, 55567, 94838, 161891, 276325, 471659, 805102, 1374234, 2345724, 4004031, 6834605, 11666260, 19913668, 33991462, 58021534, 99039592, 169055094, 288567886, 492569833, 840790082

Offset: 0

Joerg Arndt, Apr 21 2013

nonn

			There are a(6) = 19 such compositions of 6:
01:  [ 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 2 ]
03:  [ 1 1 1 2 1 ]
04:  [ 1 1 2 1 1 ]
05:  [ 1 1 2 2 ]
06:  [ 1 2 1 1 1 ]
07:  [ 1 2 1 2 ]
08:  [ 1 2 2 1 ]
09:  [ 1 2 3 ]
10:  [ 2 1 1 1 1 ]
11:  [ 2 1 1 2 ]
12:  [ 2 1 2 1 ]
13:  [ 2 2 1 1 ]
14:  [ 2 2 2 ]
15:  [ 2 4 ]
16:  [ 3 2 1 ]
17:  [ 3 3 ]
18:  [ 4 2 ]
19:  [ 6 ]

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

The case of strict relations is A342330, with strict case A342341.
The strict case is A342342.
A000929 counts partitions with adjacent parts x >= 2y.
A002843 counts compositions with adjacent parts x <= 2y.
A045690 counts sets with maximum n with adjacent elements y < 2x.
A154402 counts partitions with adjacent parts x = 2y.
A274199 counts compositions with adjacent parts x < 2y.
A342094 counts partitions with adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with adjacent parts x > 2y.
A342331 counts compositions with adjacent parts x = 2y or y = 2x.
A342332 counts compositions with adjacent parts x > 2y or y > 2x.
A342333 counts compositions with adjacent parts x >= 2y or y >= 2x.
A342334 counts compositions with adjacent parts x >= 2y or y > 2x.
A342335 counts compositions with adjacent parts x >= 2y or y = 2x.
A342336 counts compositions with adjacent parts x > 2y or y = 2x.
A342337 counts partitions with adjacent parts x = y or x = 2y.
A342338 counts compositions with adjacent parts x < 2y and y <= 2x.
A342340 counts compositions with adjacent x = y or x = 2y or y = 2x.
Cf. A003114, A003242, A034296, A167606, A342191, A342339.

b:= proc(n, i) option remember; `if`(n=0, 1, add(
      b(n-j, j), j=`if`(i=0, 1..n, ceil(i/2)..min(n, 2*i))))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Mar 15 2021

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],And@@Table[#[[i]]<=2*#[[i-1]]&&#[[i-1]]<=2*#[[i]],{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Mar 12 2021 *)
b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n - j, j], {j, If[i == 0, Range[n], Range[Ceiling[i/2], Min[n, 2*i]]]}]];
a[n_] := b[n, 0];
a /@ Range[0, 42] (* Jean-François Alcover, May 24 2021, after Alois P. Heinz *)

Name corrected by Gus Wiseman, Mar 11 2021

A337135 a(1) = 1; for n > 1, a(n) = Sum_{d|n, d <= sqrt(n)} a(d).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 4, 2, 2, 1, 5, 2, 2, 2, 4, 1, 4, 1, 4, 2, 2, 2, 7, 1, 2, 2, 5, 1, 5, 1, 4, 3, 2, 1, 7, 2, 3, 2, 4, 1, 5, 2, 5, 2, 2, 1, 8, 1, 2, 3, 6, 2, 5, 1, 4, 2, 4, 1, 9, 1, 2, 3, 4, 2, 5, 1, 7, 4, 2, 1, 8, 2, 2, 2, 6, 1, 8, 2, 4, 2, 2, 2

Offset: 1

Ilya Gutkovskiy, Nov 21 2020

nonn

From Gus Wiseman, Mar 05 2021: (Start)
This sequence counts all of the following essentially equivalent things:
1. Chains of distinct inferior divisors from n to 1, where a divisor d|n is inferior if d <= n/d. Inferior divisors are counted by A038548 and listed by A161906.
2. Chains of divisors from n to 1 whose first-quotients (in analogy with first-differences) are term-wise greater than or equal to their decapitation (maximum element removed). For example, the divisor chain q = 60/4/2/1 has first-quotients (15,2,2), which are >= (4,2,1), so q is counted under a(60).
3. Chains of divisors from n to 1 such that x >= y^2 for all adjacent x, y.
4. Factorizations of n where each factor is greater than or equal to the product of all previous factors.
(End)

			From _Gus Wiseman_, Mar 05 2021: (Start)
The a(n) chains for n = 1, 2, 4, 12, 16, 24, 36, 60:
  1  2/1  4/1    12/1    16/1      24/1      36/1      60/1
          4/2/1  12/2/1  16/2/1    24/2/1    36/2/1    60/2/1
                 12/3/1  16/4/1    24/3/1    36/3/1    60/3/1
                         16/4/2/1  24/4/1    36/4/1    60/4/1
                                   24/4/2/1  36/6/1    60/5/1
                                             36/4/2/1  60/6/1
                                             36/6/2/1  60/4/2/1
                                                       60/6/2/1
The a(n) factorizations for n = 2, 4, 12, 16, 24, 36, 60:
    2  4    12   16     24     36     60
       2*2  2*6  2*8    3*8    4*9    2*30
            3*4  4*4    4*6    6*6    3*20
                 2*2*4  2*12   2*18   4*15
                        2*2*6  3*12   5*12
                               2*2*9  6*10
                               2*3*6  2*2*15
                                      2*3*10
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..65536

Cf. A002033, A008578 (positions of 1's), A068108.
The restriction to powers of 2 is A018819.
Not requiring inferiority gives A074206 (ordered factorizations).
The strictly inferior version is A342083.
The strictly superior version is A342084.
The weakly superior version is A342085.
The additive version is A000929, or A342098 forbidding equality.
A000005 counts divisors, with sum A000203.
A001055 counts factorizations.
A003238 counts chains of divisors summing to n-1, with strict case A122651.
A038548 counts inferior (or superior) divisors.
A056924 counts strictly inferior (or strictly superior) divisors.
A067824 counts strict chains of divisors starting with n.
A167865 counts strict chains of divisors > 1 summing to n.
A207375 lists central divisors.
A253249 counts strict chains of divisors.
A334996 counts ordered factorizations by product and length.
A334997 counts chains of divisors of n by length.
A342086 counts strict factorizations of divisors.
- Inferior: A033676, A066839, A072499, A161906.
- Superior: A033677, A070038, A161908.
- Strictly Inferior: A060775, A070039, A333806, A341674.
- Strictly Superior: A048098, A064052, A140271, A238535, A341673.
Cf. A001248, A006530, A020639, A040039, A045690, A337105, A342087, A342094, A342095, A342096, A342097.

a:= proc(n) option remember; `if`(n=1, 1, add(
      `if`(d<=n/d, a(d), 0), d=numtheory[divisors](n)))
    end:
seq(a(n), n=1..128);  # Alois P. Heinz, Jun 24 2021

a[1] = 1; a[n_] := a[n] = DivisorSum[n, a[#] &, # <= Sqrt[n] &]; Table[a[n], {n, 95}]
(* second program *)
asc[n_]:=Prepend[#,n]&/@Prepend[Join@@Table[asc[d],{d,Select[Divisors[n],#Gus Wiseman, Mar 05 2021 *)

G.f.: Sum_{k>=1} a(k) * x^(k^2) / (1 - x^k).

a(2^n) = A018819(n). - Gus Wiseman, Mar 08 2021

A350844 Number of strict integer partitions of n with no difference -2.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 3, 4, 4, 7, 7, 8, 11, 12, 15, 18, 21, 23, 31, 32, 40, 45, 54, 59, 73, 78, 94, 106, 122, 136, 161, 177, 203, 231, 259, 293, 334, 372, 417, 476, 525, 592, 663, 742, 821, 931, 1020, 1147, 1271, 1416, 1558, 1752, 1916, 2137, 2357, 2613, 2867

Offset: 0

Gus Wiseman, Jan 21 2022

nonn

			The a(1) = 1 through a(12) = 11 partitions (A..C = 10..12):
  1   2   3    4   5    6     7    8     9     A      B     C
          21       32   51    43   62    54    73     65    84
                   41   321   52   71    63    82     74    93
                              61   521   72    91     83    A2
                                         81    541    92    B1
                                         432   721    A1    543
                                         621   4321   632   651
                                                      821   732
                                                            741
                                                            921
                                                            6321

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for no difference 0 is A000009.
The version for no difference > -2 is A001227, non-strict A034296.
The version for no difference -1 is A003114 (A325160).
The version for subsets of prescribed maximum is A005314.
The version for all differences < -2 is A025157, non-strict A116932.
The opposite version is A072670.
The multiplicative version is A350840, non-strict A350837 (A350838).
The non-strict version is A350842.
A000041 counts integer partitions.
A027187 counts partitions of even length.
A027193 counts partitions of odd length (A026424).
A116931 counts partitions with no difference -1 (A319630).
A323092 counts double-free integer partitions (A320340) strict A120641.
A325534 counts separable partitions (A335433).
A325535 counts inseparable partitions (A335448).
Cf. A000929, A003000, A018819, A040039, A045690, A045691, A154402, A303362, A323094, A342095, A342097.

Table[Length[Select[IntegerPartitions[n],FreeQ[Differences[#],0|-2]&]],{n,0,30}]

cp's OEIS Frontend

A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A040039 First differences of A033485; also A033485 with terms repeated.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Python

Formula

A350842 Number of integer partitions of n with no difference -2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A002083 Narayana-Zidek-Capell numbers: a(n) = 1 for n <= 2. Otherwise a(2n) = 2a(2n-1), a(2n+1) = 2a(2n) - a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A342083 Number of chains of strictly inferior divisors from n to 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A342084 Number of chains of distinct strictly superior divisors starting with n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Views

A224957 Number of compositions [p(1), p(2), ..., p(k)] of n such that p(j) <= 2p(j-1) and p(j-1) <= 2p(j).