A003000 -id:A003000 - cp's OEIS frontend

A350840 Number of strict integer partitions of n with no adjacent parts of quotient 2.

1, 1, 1, 1, 2, 3, 2, 4, 5, 6, 7, 8, 10, 13, 17, 19, 22, 25, 30, 35, 43, 52, 60, 70, 81, 93, 106, 122, 142, 166, 190, 216, 249, 287, 325, 371, 420, 479, 543, 617, 695, 784, 888, 1000, 1126, 1266, 1420, 1594, 1792, 2008, 2247, 2514, 2809, 3135, 3496, 3891, 4332

Offset: 0

Gus Wiseman, Jan 20 2022

nonn

			The a(1) = 1 through a(13) = 13 partitions (A..D = 10..13):
  1   2   3   4    5    6    7    8     9     A     B     C     D
              31   32   51   43   53    54    64    65    75    76
                   41        52   62    72    73    74    93    85
                             61   71    81    82    83    A2    94
                                  431   432   91    92    B1    A3
                                        531   532   A1    543   B2
                                              541   641   651   C1
                                                    731   732   643
                                                          741   652
                                                          831   751
                                                                832
                                                                931
                                                                5431

The version for subsets of prescribed maximum is A045691.
The double-free case is A120641.
The non-strict case is A350837, ranked by A350838.
An additive version (differences) is A350844, non-strict A350842.
The non-strict complement is counted by A350846, ranked by A350845.
Versions for prescribed quotients:
  = 2:  A154402, sets A001511.
  != 2: A350840 (this sequence), sets A045691.
  >= 2: A000929, sets A018819.
  <= 2: A342095, non-strict A342094.
  < 2:  A342097, non-strict A342096, sets A045690.
  > 2:  A342098, sets A040039.
A000041 = integer partitions.
A000045 = sets containing n with all differences > 2.
A003114 = strict partitions with no successions, ranked by A325160.
A116931 = partitions with no successions, ranked by A319630.
A116932 = partitions with differences != 1 or 2, strict A025157.
A323092 = double-free integer partitions, ranked by A320340.
A350839 = partitions with gaps and conjugate gaps, ranked by A350841.
Cf. A003000, A018819, A303362, A323093, A323094, A337135, A342191.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&And@@Table[#[[i-1]]/#[[i]]!=2,{i,2,Length[#]}]&]],{n,0,30}]

A019309 Number of "bifix-free" words of length n over a four-letter alphabet.

Original entry on oeis.org

1, 4, 12, 48, 180, 720, 2832, 11328, 45132, 180528, 721392, 2885568, 11539440, 46157760, 184619712, 738478848, 2953870260, 11815481040, 47261743632, 189046974528, 756187176720, 3024748706880, 12098991941952

Offset: 0

Jeffrey Shallit

E. Barcucci, A. Bernini, S. Bilotta, 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.
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.

Cf. A003000, A019308, A094547, A094559, A094578.

a[0]=1; a[n_]:=a[n]=4*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

a(2n+1) = 4a(2n); a(2n) = 4a(2n-1) - a(n).

A045691 Number of binary words of length n with autocorrelation function 2^(n-1)+1.

Original entry on oeis.org

0, 1, 1, 3, 5, 11, 19, 41, 77, 159, 307, 625, 1231, 2481, 4921, 9883, 19689, 39455, 78751, 157661, 315015, 630337, 1260049, 2520723, 5040215, 10081661, 20160841, 40324163, 80643405, 161291731, 322573579, 645157041, 1290294393, 2580608475, 5161177495

Offset: 0

Torsten Sillke (torsten.sillke(AT)lhsystems.com)

nonn

From Gus Wiseman, Jan 22 2022: (Start)
Also the number of subsets of {1..n} containing n but without adjacent elements of quotient 1/2. The Heinz numbers of these sets are a subset of the squarefree terms of A320340. For example, the a(1) = 1 through a(6) = 19 subsets are:
  {1}  {2}  {3}    {4}      {5}        {6}
            {1,3}  {1,4}    {1,5}      {1,6}
            {2,3}  {3,4}    {2,5}      {2,6}
                   {1,3,4}  {3,5}      {4,6}
                   {2,3,4}  {4,5}      {5,6}
                            {1,3,5}    {1,4,6}
                            {1,4,5}    {1,5,6}
                            {2,3,5}    {2,5,6}
                            {3,4,5}    {3,4,6}
                            {1,3,4,5}  {3,5,6}
                            {2,3,4,5}  {4,5,6}
                                       {1,3,4,6}
                                       {1,3,5,6}
                                       {1,4,5,6}
                                       {2,3,4,6}
                                       {2,3,5,6}
                                       {3,4,5,6}
                                       {1,3,4,5,6}
                                       {2,3,4,5,6}
(End)

If a(n) counts subsets of {1..n} with n and without adjacent quotients 1/2:
- The version with quotients <= 1/2 is A018819, partitions A000929.
- The version with quotients < 1/2 is A040039, partitions A342098.
- The version with quotients >= 1/2 is A045690(n+1), partitions A342094.
- The version with quotients > 1/2 is A045690, partitions A342096.
- Partitions of this type are counted by A350837, ranked by A350838.
- Strict partitions of this type are counted by A350840.
- For differences instead of quotients we have A350842, strict A350844.
- Partitions not of this type are counted by A350846, ranked by A350845.
A000740 = relatively prime subsets of {1..n} containing n.
A002843 = compositions with all adjacent quotients >= 1/2.
A050291 = double-free subsets of {1..n}.
A154402 = partitions with all adjacent quotients 2.
A308546 = double-closed subsets of {1..n}, with maximum: shifted right.
A323092 = double-free integer partitions, ranked by A320340, strict A120641.
A326115 = maximal double-free subsets of {1..n}.
Cf. A000009, A001511, A003000, A003114, A116932, A274199, A323093, A342095, A342191, A342331, A342332, A342333, A342337.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]!=1/2,{i,2,Length[#]}]&]],{n,0,15}] (* Gus Wiseman, Jan 22 2022 *)

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

More terms from Sean A. Irvine, Mar 18 2021

A350846 Number of integer partitions of n with at least two adjacent parts of quotient 2.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 4, 5, 8, 12, 18, 25, 36, 48, 65, 89, 119, 157, 207, 269, 350, 448, 574, 729, 927, 1166, 1465, 1830, 2282, 2827, 3501, 4309, 5300, 6483, 7923, 9641, 11718, 14187, 17155, 20674, 24885, 29860, 35787, 42772, 51054, 60791, 72289, 85772, 101641

Offset: 0

Gus Wiseman, Jan 20 2022

nonn

			The a(3) = 1 through a(9) = 12 partitions:
  (21)  (211)  (221)   (42)     (421)     (422)      (63)
               (2111)  (321)    (2221)    (521)      (621)
                       (2211)   (3211)    (3221)     (3321)
                       (21111)  (22111)   (4211)     (4221)
                                (211111)  (22211)    (5211)
                                          (32111)    (22221)
                                          (221111)   (32211)
                                          (2111111)  (42111)
                                                     (222111)
                                                     (321111)
                                                     (2211111)
                                                     (21111111)

The complement is counted by A350837, strict A350840.
The complimentary additive version is A350842, strict A350844.
These partitions are ranked by A350845, complement A350838.
A000041 = integer partitions.
A323092 = double-free integer partitions, ranked by A320340.
Cf. A000929, A003000, A003114, A018819, A045690, A045691, A116931, A120641, A154402, A323093, A342094, A342095, A342096, A342098.

Table[Length[Select[IntegerPartitions[n], MemberQ[Divide@@@Partition[#,2,1],2]&]],{n,0,30}]

A094537 A094536/2.

Original entry on oeis.org

0, 0, 1, 2, 5, 10, 22, 44, 91, 182, 370, 740, 1490, 2980, 5980, 11960, 23957, 47914, 95902, 191804, 383750, 767500, 1535284, 3070568, 6141694, 12283388, 24567892, 49135784, 98273780, 196547560, 393099544, 786199088, 1572406987, 3144813974

Offset: 0

N. J. A. Sloane, Jun 06 2004

Cf. A003000, A094536.

b[0]=1;b[n_]:=b[n]=2*b[n-1]-(1+(-1)^n)/2*b[Floor[n/2]]; a[n_]:=2^(n-1)-b[n]/2;Table[a[n], {n, 0, 35}]

Let b(0)=1; b(n)=2*b(n-1)-1/2*(1+(-1)^n)*b([n/2]); a(n)=2^(n-1)-b(n)/2 - Farideh Firoozbakht, Jun 10 2004

More terms from Farideh Firoozbakht, Jun 10 2004

A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.

Original entry on oeis.org

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

Offset: 0

Danny Rorabaugh, Sep 17 2015

Word W over alphabet L is an instance of "aba" provided there exists a nonerasing monoid homomorphism f:{a,b}*->L* such that f(W)=aba. For example "oompaloompa" is an instance of "aba" via the homomorphism defined by f(a)=oompa, f(b)=l. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
The second definition comes from a Comment in A094536: "The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - Peter Kagey, Jan 26 2015"
Also, the limit, as word-length approaches infinity, of the probability that a random binary word has a bifix; that is, 1-x where x is the constant from A242430. - Danny Rorabaugh, Feb 13 2016

			0.7322131597821108876233285964156974474449401020065154679236881114887...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.17, p. 369.

Danny Rorabaugh, Table of n, a(n) for n = 0..1000
Danny Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv:1509.04372 [math.CO], 2015, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.1.

Cf. A003000, A094536, A123121, A242430, A262313 (abacaba).

N(sum([2*(1/4)^(2^j)*(-1)^j/prod([1-2*(1/4)^(2^k) for k in range(j+1)]) for j in range(8)]),digits=81) #For more than 152 digits of accuracy, increase the j-range.

The constant is Sum_{n>=0} A003000(n)*(1/4)^n.
Using the recursive definition of A003000, one can derive the series Sum_{j>=0} 2*(-1)^j*(1/4)^(2^j)/(Product_{k=0..j} 1-2*(1/4)^(2^k)), which converges more quickly to the same limit and without having to calculate terms of A003000.
For ternary words, the constant is Sum_{n>=0} A019308(n)*(1/9)^n.
For quaternary words, the constant is Sum_{n>=0} A019309(n)*(1/16)^n.

A019310 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-1.

Original entry on oeis.org

0, 2, 2, 6, 10, 22, 38, 82, 154, 318, 614, 1250, 2462, 4962, 9842, 19766, 39378, 78910, 157502, 315322, 630030, 1260674, 2520098, 5041446, 10080430, 20163322, 40321682, 80648326, 161286810, 322583462, 645147158, 1290314082, 2580588786, 5161216950

Offset: 1

Jeffrey Shallit

nonn

			G.f. = 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + 38*x^7 + 82*x^8 + ...
a(4) = 6 because we have: {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}.  These are precisely the binary words of length 4 with autocorrelation polynomial equal to 1 + z^3. - _Geoffrey Critzer_, Apr 13 2022

Robert Israel, Table of n, a(n) for n = 1..3320
H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, Journal für Mathematik, 271 (1974) 139-154.

Cf. A003000, A019311.

f:= proc(n) option remember;
    2*procname(n-1)+(-1)^n*procname(ceil(n/2))
end proc:
f(1):= 0: f(2):= 2:
map(f, [$1..100]); # Robert Israel, Jul 15 2018

a(n) = if (n==1, 0, if (n==2, 2, 2*a(n-1) + (-1)^n*a(ceil(n/2)))) \\ Michel Marcus, May 25 2013

a(n) = 2*a(n-1) + (-1)^n * a(ceiling(n/2)) for n >= 3.

a(n) = a(n-1) + 2*a(n-2) if n >= 4 even. a(n) = a(n-1) + 2*a(n-2) + 2*a((n-1)/2) if n>=7 == 3 (mod 4). - Michael Somos, Jan 23 2014

A019311 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-2.

Original entry on oeis.org

0, 0, 2, 2, 6, 12, 28, 48, 106, 198, 414, 800, 1644, 3236, 6546, 12982, 26130, 52048, 104404, 208372, 417390, 833930, 1669102, 3336476, 6675512, 13347600, 26700226, 53393562, 106797302, 213580904, 427181968, 854336432, 1708713470, 3417372070, 6834824970

Offset: 1

Jeffrey Shallit

nonn

			a(5) = 6 because we have: {0, 0, 1, 0, 0}, {1, 1, 0, 1, 1}, {0, 1, 0, 0, 1},
{0, 1, 1, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 1, 1, 0}. The first two words have autocorrelation polynomial equal to 1 + z^3 + z^4, the last four words have autocorrelation polynomial equal to 1 + z^4. - _Geoffrey Critzer_, Apr 13 2022

H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, Journal für Mathematik, 271 (1974) 139-154.
Sean A. Irvine, Java program (github)

Cf. A003000, A019310.

More terms from Jeffrey Shallit, Feb 20 2013

More terms from Sean A. Irvine, Jun 20 2021

A094559 Number of words of length n over an alphabet of size 4 that are not "bifix-free".

Original entry on oeis.org

0, 0, 4, 16, 76, 304, 1264, 5056, 20404, 81616, 327184, 1308736, 5237776, 20951104, 83815744, 335262976, 1341097036, 5364388144, 21457733104, 85830932416, 343324451056, 1373297804224, 5493194102464, 21972776409856, 87891117178864

Offset: 0

N. J. A. Sloane, Jun 06 2004

See A019308, A019309 and A003000 for much more information. Cf. A094578.

a:=proc(n) if n=0 or n=1 then 0 elif n mod 2 = 0 then 4*a(n-1)-a(n/2)+4^(n/2) else 4*a(n-1) fi end: seq(a(n),n=0..28); # Emeric Deutsch, Feb 04 2006

Equals 4^n - A019309(n).

a(0)=a(1)=0, a(2n)=4^n + 4a(2n-1) - a(n), a(2n+1)=4a(2n). - Emeric Deutsch, Feb 04 2006

More terms from Emeric Deutsch, Feb 04 2006

A254128 Number of binary strings of length n that begin with an odd-length palindrome.

Original entry on oeis.org

0, 0, 0, 4, 8, 20, 40, 88, 176, 364, 728, 1480, 2960, 5960, 11920, 23920, 47840, 95828, 191656, 383608, 767216, 1535000, 3070000, 6141136, 12282272, 24566776, 49133552, 98271568, 196543136, 393095120, 786190240, 1572398176, 3144796352, 6289627948, 12579255896

Offset: 0

Peter Kagey, Jan 25 2015

This sequence gives the number of binary strings of length n that begin with an odd-length palindrome (not including the trivial palindrome of length one).
'1011' is an example of a string that begins with an odd-length palindrome: the palindrome '101', which is of length 3.
'1101' is an example of a string that does not begin with an odd-length palindrome. (It does begin with the even-length palindrome '11'.)
The probability of a random infinite binary string beginning with an odd-length palindrome is given by: limit n -> infinity a(n)/(2^n), which is approximately 0.7322131597821109.

			For n = 4 the a(3) = 8 solutions are: 0000 0001 0100 0101 1010 1011 1110 1111.

Peter Kagey, Table of n, a(n) for n = 0..1000

Cf. A003000. A094536 is the analogous sequence for even-length palindromes.

s = [0, 0]
(2..N).each { |n| s << 2 * s[-1] + (n.even? ? 0 : 2**(n/2+1) - s[n/2+1]) }

a(2*n) = 2*a(2*n-1) = A094536(2*n) - A003000(n) for all n > 0.

a(2*n+1) = 2*a(2*n) + 2^(n+1) - a(n+1) = A094536(2*n+1) for all n.

cp's OEIS Frontend

A350840 Number of strict integer partitions of n with no adjacent parts of quotient 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A019309 Number of "bifix-free" words of length n over a four-letter alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A045691 Number of binary words of length n with autocorrelation function 2^(n-1)+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A350846 Number of integer partitions of n with at least two adjacent parts of quotient 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A094537 A094536/2.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

Extensions

A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

Formula

A019310 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A019311 Number of words of length n (n >= 1) over a two-letter alphabet having a minimal period of size n-2.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A094559 Number of words of length n over an alphabet of size 4 that are not "bifix-free".

Views

Author

Keywords