A225681 -id:A225681 - cp's OEIS frontend

A216264 Number of rich binary words of length n.

1, 2, 4, 8, 16, 32, 64, 128, 252, 488, 932, 1756, 3246, 5916, 10618, 18800, 32846, 56704, 96702, 163184, 272460, 450586, 738274, 1199376, 1932338, 3089518, 4903164, 7728120, 12099440, 18825066, 29112876, 44767202, 68461866, 104153666, 157657852, 237510110, 356158688

Offset: 0

Jeffrey Shallit, Mar 15 2013

nonn

A word of length n is "rich" if it contains, as subwords, exactly n + 1 distinct palindromes (including the empty word). Here "subword" means contiguous subsequence of the word.

			For n = 8 we have a(n) = 2^8 - 4 = 252 because the only non-rich words are 00101100, 00110100, and their complements.

Mikhail Rubinchik, Table of n, a(n) for n = 0..60
Amy Glen, Jacques Justin, Steve Widmer and Luca Q. Zamboni, Palindromic richness, European J. Combin. 30 (2009), no. 2, 510-531.
Chuan Guo, J. Shallit, A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
Chuan Guo, J. Shallit, and A. M. Shur, Palindromic Rich Words and Run-Length Encodings, Information Processing Letters Volume 116, Issue 12, December 2016, Pages 735-738.
M. Rubinchik and A. M. Shur, Eertree: An Efficient Data Structure for Processing Palindromes in Strings, arXiv preprint arXiv:1506.04862 [cs.DS], 2015.
Mikhail Rubinchik, C program.
Josef Rukavicka, On Number of Rich Words, arXiv:1701.07778 [math.CO], 2016.
Josef Rukavicka, An Upper Bound for Palindromic and Factor Complexity of Rich Words, arXiv:1810.03573 [math.CO], 2018.

Cf. A225681.

(* Program not suitable to compute a large number of terms *)
richQ[w_] := (w[[#[[1]] ;; #[[2]]]]& /@ SequencePosition[w, _?PalindromeQ] // Union // Length) == n+1;
a[n_] := a[n] = Select[PadLeft[IntegerDigits[#, 2], n]& /@ Range[0, 2^n-1], richQ] // Length; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Sep 22 2018 *)

ispal(v) = {for (i=1, #v\2, if (v[i] != v[#v-i+1], return(0)); ); return(1); };
isrich(vb, n) = {pals = Set(); for (i=1, #vb, for (len=1, #vb-i+1, subword = vector(len, x, vb[i+x-1]); if (ispal(subword), pals = setunion(pals, Set(Str(subword)) ); ); ); ); if (length(pals)==n, return(1)); return (0); }
a(n) = {nbr = 0; for (i=0, 2^n-1, vb = binary(i); while(length(vb) < n, vb = concat(0, vb); ); if (isrich(vb, n), nbr++); ); return (nbr); } \\ Michel Marcus, May 26 2013

from itertools import product
def pal(w): return w == w[::-1]
def rich(w):
    subs = (w[i:j] for i in range(len(w)) for j in range(i+1, len(w)+1))
    return len(w) == sum(pal(s) for s in set(subs))
def a(n):
    if n == 0: return 1
    return sum(2 for b in product("01", repeat=n-1) if rich("0"+"".join(b)))
print([a(n) for n in range(16)]) # Michael S. Branicky, Jul 07 2022

a(17) from Alois P. Heinz, Mar 15 2013
a(18)-a(25) from Jeffrey Shallit, Mar 19 2013
a(26)-a(60) from Mikhail Rubinchik, Mar 05 2015

A348664 Numbers whose binary expansion is not rich.

Original entry on oeis.org

203, 211, 300, 308, 333, 357, 395, 406, 407, 419, 422, 423, 459, 467, 556, 564, 600, 601, 604, 616, 617, 628, 653, 666, 667, 669, 690, 709, 714, 715, 723, 741, 779, 787, 790, 791, 803, 811, 812, 813, 814, 815, 820, 835, 838, 839, 844, 845, 846, 847, 851, 869

Offset: 1

Rémy Sigrist, Oct 28 2021

A word of length k is "rich" if it contains, as contiguous subsequences, exactly k + 1 distinct palindromes (including the empty word).

There are A225681(k)/2 terms with k binary digits.

			For n = 203:
- the binary expansion of 203 is "11001011" and has 8 binary digits,
- we have the following 8 palindromes: "", "0", "1", "00", "11", "010", "101", "1001"
- so 203 is not rich, and belongs to this sequence.
For n = 204:
- the binary expansion of 204 is "11001100" and has 8 binary digits,
- we have the following 9 palindromes: "", "0", "1", "00", "11", "0110", "1001", "001100", "110011"
- so 204 is rich, and does not belong to this sequence.

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Cf. A206926, A216264, A225681, A070939, A137397.

Select[Range@1000,Length@Select[Union[Subsequences[s=IntegerDigits[#,2]]],PalindromeQ]<=Length@s&] (* Giorgos Kalogeropoulos, Oct 29 2021 *)

is(n) = { my (b=binary(n), p=select(w->w==Vecrev(w), setbinop((i,j)->b[i..j],[1..#b]))); #b!=#p }

def ispal(s): return s == s[::-1]
def ok(n):
  s = bin(n)[2:]
  return len(s) >= 1 + len(set(s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1) if ispal(s[i:j])))
print([k for k in range(870) if ok(k)]) # Michael S. Branicky, Oct 29 2021

{k: A137397(k) <= A070939(k)}. - Michael S. Branicky, Oct 29 2021

cp's OEIS Frontend

A216264 Number of rich binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions