login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A249643 Number of strings of length n over a 10-letter alphabet that begin with a nontrivial palindrome. 9
0, 0, 10, 190, 1990, 20710, 207910, 2087110, 20879110, 208870390, 2088783190, 20888623990, 208887031990, 2088878232790, 20888790240790, 208887981528790, 2088879894408790, 20888799735217510, 208887998143304710, 2088879989344263910, 20888799901353855910 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A nontrivial palindrome is a palindrome of length 2 or greater. (E.g., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)

For example, 0092 is a is a base-10 string of length 4 that begins with a nontrivial palindrome (00).

10 divides a(n) for all n.

a(n) is the number of distinct walks of n steps that begin with a palindromic sequence on the complete graph K_10 with loops. (E.g., 0, 1, 1, 0, 1, 1, 9 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)

lim n -> infinity a(n)/10^n ~ 0.20888799911023023 is the probability that a random, infinite base-9 string begins with a nontrivial palindrome.

LINKS

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

FORMULA

a(0) = 0; a(1) = 0; a(n+1) = 10*a(n) + 10^ceiling((n + 1)/2) - a(ceiling((n + 1)/2)).

EXAMPLE

For n=3 the a(3) = 190 valid strings are: 000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 010, 020, 030, 040, 050, 060, 070, 080, 090, 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 343, 353, 363, 373, 383, 393, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 454, 464, 474, 484, 494, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 565, 575, 585, 595, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666, 667, 668, 669, 676, 686, 696, 707, 717, 727, 737, 747, 757, 767, 770, 771, 772, 773, 774, 775, 776, 777, 778, 779, 787, 797, 808, 818, 828, 838, 848, 858, 868, 878, 880, 881, 882, 883, 884, 885, 886, 887, 888, 889, 898, 909, 919, 929, 939, 949, 959, 969, 979, 989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999

MATHEMATICA

a249643[n_] := Block[{f},

  f[0] = f[1] = 0;

  f[x_] := 10*f[x - 1] + 10^Ceiling[x/2] - f[Ceiling[x/2]];

  Table[f[i], {i, 0, n}]

]; a249643[20] (* Michael De Vlieger, Dec 27 2014 *)

PROG

(Ruby) seq = [0, 0]; (2..N).each{ |i| seq << 10 * seq[i-1] + 10**((i+1)/2) - seq[(i+1)/2] }

CROSSREFS

Analogous sequences for k-letter alphabets: A248122 (k=3), A249629 (k=4), A249638 (k=5), A249639 (k=6), A249640 (k=7), A249641 (k=8), A249642 (k=9).

Sequence in context: A239765 A006409 A173813 * A056174 A033714 A169959

Adjacent sequences:  A249640 A249641 A249642 * A249644 A249645 A249646

KEYWORD

easy,nonn,walk

AUTHOR

Peter Kagey, Nov 02 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 19 17:59 EST 2020. Contains 331051 sequences. (Running on oeis4.)