A155092 -id:A155092 - cp's OEIS frontend

A045690 Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.

1, 1, 2, 3, 6, 10, 20, 37, 74, 142, 284, 558, 1116, 2212, 4424, 8811, 17622, 35170, 70340, 140538, 281076, 561868, 1123736, 2246914, 4493828, 8986540, 17973080, 35943948, 71887896, 143771368, 287542736, 575076661, 1150153322, 2300289022, 4600578044, 9201120918

Offset: 1

Torsten.Sillke(AT)uni-bielefeld.de

The number of binary strings sharing the same autocorrelations.
Appears to be row sums of A155092, beginning from a(2). - Mats Granvik, Jan 20 2009
The number of binary words of length n (beginning with 0) which do not start with an even palindrome (i.e. which are not of the form ss*t where s is a (nonempty) word, s* is its reverse, and t is any (possibly empty) word). - Mamuka Jibladze, Sep 30 2014
From Gus Wiseman, Mar 08 2021: (Start)
This sequence counts each of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n in which all adjacent elements have quotients > 1/2. For example, the a(1) = 1 through a(6) = 10 sets are:
  {1}  {2}  {3}    {4}      {5}        {6}
            {2,3}  {3,4}    {3,5}      {4,6}
                   {2,3,4}  {4,5}      {5,6}
                            {2,3,5}    {3,4,6}
                            {3,4,5}    {3,5,6}
                            {2,3,4,5}  {4,5,6}
                                       {2,3,4,6}
                                       {2,3,5,6}
                                       {3,4,5,6}
                                       {2,3,4,5,6}
2. For n > 1, sets of distinct positive integers with maximum n - 1 whose first-differences are term-wise less than their decapitation (remove the maximum). For example, the set q = {2,4,5} has first-differences (2,1), which are not less than (2,4), so q is not counted under a(5). On the other hand, r = {2,3,5,6} has first-differences {1,2,1}, which are less than {2,3,5}, so r is counted under a(6).
3. Compositions of n where each part after the first is less than the sum of all preceding parts. For example, the a(1) = 1 through a(6) = 10 compositions are:
  (1)  (2)  (3)   (4)    (5)     (6)
            (21)  (31)   (41)    (51)
                  (211)  (32)    (42)
                         (311)   (411)
                         (212)   (321)
                         (2111)  (312)
                                 (3111)
                                 (2121)
                                 (2112)
                                 (21111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..3324 (first 500 terms from T. D. Noe)
E. H. Rivals, Autocorrelation of Strings.
E. H. Rivals, S. Rahmann Combinatorics of Periods in Strings
E. H. Rivals, S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.
T. Sillke, How many words have the same autocorrelation value?

Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.
Different from, but easily confused with, A007148 and A093371.
The version with quotients <= 1/2 is A018819.
The version with quotients < 1/2 is A040039.
Multiplicative versions are A337135, A342083, A342084, A342085.
A000045 counts sets containing n with all differences > 2.
A000929 counts partitions with no adjacent parts having quotient < 2.
A342094 counts partitions with no adjacent parts having quotient > 2.
Cf. A003242, A038548, A056924, A154402, A167606, A342096, A342097, A342098, A342191.

a:= proc(n) option remember; `if`(n=0, 1/2,
       2*a(n-1)-`if`(n::odd, 0, a(n/2)))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 24 2021

a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2*a[n-1] - a[n/2], 2*a[n-1]]; Array[a, 40] (* Jean-François Alcover, Jul 17 2015 *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Min@@Divide@@@Partition[#,2,1]>1/2&]],{n,8}] (* Gus Wiseman, Mar 08 2021 *)

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

a(2n) = 2*a(2n-1) - a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.

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

More terms from James Sellers.

Additional comments from Michael Somos, Jun 09 2000

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

cp's OEIS Frontend

A155099 Third column of A155092.

Views

Author

Keywords

Extensions

A045690 Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A155091 Triangle read by rows. Signed version of A145362. Main diagonal positive, rest of the nonzero terms negative.

Views

Author

Keywords

Comments

Examples

Crossrefs