A249643 -id:A249643 - cp's OEIS frontend

A248122 Number of strings of length n over a three-letter alphabet that begin with a nontrivial palindrome.

0, 0, 3, 15, 51, 165, 507, 1551, 4683, 14127, 42459, 127599, 383019, 1149693, 3449715, 10351023, 31054947, 93170397, 279516747, 838566831, 2515717083, 7547200797, 22641651939, 67925104239, 203775461139, 611326828047, 1833980928771

Offset: 0

Peter Kagey, Oct 28 2014

A nontrivial palindrome is a palindrome of length two or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)
For example, 0012 is a string of length four over a three-letter alphabet that begins with a nontrivial palindrome (00).
3 divides a(n) for all n: 0, 0, 1, 5, 17, 55, 169, 517, 1561, 4709, 14153, ...
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_3 with loops. (E.g., 0, 1, 1, 0, 2, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
lim n -> infinity a(n)/3^n ~ 0.721510080117 is the probability that a random, infinite base-3 string begins with a nontrivial palindrome.

			For n = 3, the a(3) = 15 solutions are 000, 001, 002, 010, 020, 101, 110, 111, 112, 121, 202, 212, 220, 221, 222.

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

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

import Data.Ratio
a 0 = 0; a 1 = 0;
a n = 3 * a(n - 1) + 3^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015

a248122[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 3*f[x - 1] + 3^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a248122[26] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249629 Number of strings of length n over a 4-letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 4, 28, 124, 532, 2164, 8788, 35284, 141628, 567004, 2269948, 9081724, 36334492, 145345564, 581412508, 2325680284, 9302841652, 37211487124, 148846430068, 595386201844, 2381546731732, 9526188851284, 38104763100628, 152419060098004, 609676271166388, 2438705115439924, 9754820584849588

Offset: 0

Peter Kagey, Nov 02 2014

A nontrivial palindrome is a palindrome of length 2 or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)
For example, 0032 is a string of length 4 over a 4-letter alphabet that begins with a nontrivial palindrome (00).
4 divides a(n) for all n.
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_4 with loops. (E.g., 0, 1, 1, 0, 3, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
Limit_{n->oo} a(n)/4^n ~ 0.5415013252744246 is the probability that a random, infinite base-4 string begins with a nontrivial palindrome.

			for n=3 the a(3) = 28 solutions are: 000, 001, 002, 003, 010, 020, 030, 101, 110, 111, 112, 113, 121, 131, 202, 212, 220, 221, 222, 223, 232, 303, 313, 323, 330, 331, 332, 333.

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

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

import Data.Ratio
a 0 = 0; a 1 = 0;
a n = 4 * a(n - 1) + 4^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015

[0] cat  [n le 1 select 0 else 4*Self(n-1) + 4^Ceiling((n)/2) - Self(Ceiling((n)/2)): n in [1..40]]; // Vincenzo Librandi, Aug 20 2015

a249629[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 4*f[x - 1] + 4^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249629[27] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249638 Number of strings of length n over a 5-letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 5, 45, 245, 1305, 6605, 33405, 167405, 838845, 4196045, 20989245, 104955245, 524820945, 2624149445, 13120970445, 65605075445, 328026491505, 1640133571805, 8200673428605, 41003372712605, 205016891401905, 1025084484848405, 5125422563427405

Offset: 0

Peter Kagey, Nov 02 2014

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, 0042 is a string in a five letter alphabet of length 4 that begins with a nontrivial palindrome (00).
5 divides a(n) for all n.
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_5 with loops. (E.g., 0, 1, 1, 0, 4, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
Limit_{n->oo} a(n)/5^n ~ 0.429951613027098 is the probability that a random, infinite string in a five letter alphabet begins with a nontrivial palindrome.

			For n=3 the a(3) = 45 valid strings are: 000, 001, 002, 003, 004, 010, 020, 030, 040, 101, 110, 111, 112, 113, 114, 121, 131, 141, 202, 212, 220, 221, 222, 223, 224, 232, 242, 303, 313, 323, 330, 331, 332, 333, 334, 343, 404, 414, 424, 434, 440, 441, 442, 443, 444.

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

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

import Data.Ratio
a 0 = 0; a 1 = 0;
a n = 5 * a(n - 1) + 5^ceiling(n % 2) - a(ceiling(n % 2)) -- Peter Kagey, Aug 13 2015

a249638[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 5*f[x - 1] + 5^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249638[23] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249639 Number of strings of length n over a 6 letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 6, 66, 426, 2706, 16386, 99186, 595986, 3580986, 21490986, 128976186, 773887386, 4643505066, 27861211146, 167168350506, 1003011186666, 6018073616706, 36108448196946, 216650728156866, 1299904407916386, 7799426681319186, 46796560321735986

Offset: 0

Peter Kagey, Nov 02 2014

A nontrivial palindrome is a palindrome of length 2 or greater. (I.e., "1" is a trivial palindrome, but "11" and "121" are nontrivial palindromes.)
For example, 0052 is a string of length 4 over a six letter alphabet that begins with a nontrivial palindrome (00).
6 divides a(n) for all n.
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_6 with loops. (E.g., 0, 1, 1, 0, 4, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
Limit_{n->oo} a(n)/6^n ~ 0.35553832903695737 is the probability that a random, infinite base-6 string begins with a nontrivial palindrome.

			For n=3 the a(3) = 66 solutions are: 000, 001, 002, 003, 004, 005, 010, 020, 030, 040, 050, 101, 110, 111, 112, 113, 114, 115, 121, 131, 141, 151, 202, 212, 220, 221, 222, 223, 224, 225, 232, 242, 252, 303, 313, 323, 330, 331, 332, 333, 334, 335, 343, 353, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 454, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555

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

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

a249639[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 6*f[x - 1] + 6^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249639[22] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249640 Number of strings of length n over a 7-letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 7, 91, 679, 5005, 35287, 248731, 1742839, 12211675, 85493527, 598537051, 4189841719, 29329466845, 205306842727, 1437151921051, 10060067469319, 70420500427165, 492943531132087, 3450604914906331, 24154234601326039, 169079643588071965

Offset: 0

Peter Kagey, Nov 02 2014

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, 0062 is a string of length 4 over a seven letter alphabet that begins with a nontrivial palindrome (00).
7 divides a(n) for all n.
Number of walks of n steps that begin with a palindromic sequence on the complete graph K_7 with loops. (E.g., 0, 1, 1, 0, 4, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
lim n -> infinity a(n)/7^n ~ 0.30271398450898696 is the probability that a random, infinite base-7 string begins with a nontrivial palindrome.

			For n=3 the a(3) = 91 solutions are: 000, 001, 002, 003, 004, 005, 006, 010, 020, 030, 040, 050, 060, 101, 110, 111, 112, 113, 114, 115, 116, 121, 131, 141, 151, 161, 202, 212, 220, 221, 222, 223, 224, 225, 226, 232, 242, 252, 262, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 343, 353, 363, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 454, 464, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 565, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666

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

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

a249640[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 7*f[x - 1] + 7^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249640[21] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249641 Number of strings of length n over an 8-letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 8, 120, 1016, 8520, 68552, 551496, 4415048, 35344632, 282781304, 2262444024, 18099745784, 144799511928, 1158397641080, 9267193490808, 74137560288632, 593100581182152, 4744804748330312, 37958438777603016, 303667511011784648, 2429340094421767752

Offset: 0

Peter Kagey, Nov 02 2014

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, 0072 is a string of length 4 over an eight letter alphabet that begins with a nontrivial palindrome (00).
8 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_8 with loops. (E.g., 0, 1, 1, 0, 4, 1, 2 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
lim n -> infinity a(n)/8^n ~ 0.2633895810038296 is the probability that a random, infinite base-8 string begins with a nontrivial palindrome.

			For n=3 the a(3) = 120 valid strings are: 000, 001, 002, 003, 004, 005, 006, 007, 010, 020, 030, 040, 050, 060, 070, 101, 110, 111, 112, 113, 114, 115, 116, 117, 121, 131, 141, 151, 161, 171, 202, 212, 220, 221, 222, 223, 224, 225, 226, 227, 232, 242, 252, 262, 272, 303, 313, 323, 330, 331, 332, 333, 334, 335, 336, 337, 343, 353, 363, 373, 404, 414, 424, 434, 440, 441, 442, 443, 444, 445, 446, 447, 454, 464, 474, 505, 515, 525, 535, 545, 550, 551, 552, 553, 554, 555, 556, 557, 565, 575, 606, 616, 626, 636, 646, 656, 660, 661, 662, 663, 664, 665, 666, 667, 676, 707, 717, 727, 737, 747, 757, 767, 770, 771, 772, 773, 774, 775, 776, 777

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

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

a249641[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 8*f[x - 1] + 8^Ceiling[x/2] - f[Ceiling[x/2]];
Table[f[i], {i, 0, n}]]; a249641[20] (* Michael De Vlieger, Dec 27 2014 *)

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

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

A249642 Number of strings of length n over a 9-letter alphabet that begin with a nontrivial palindrome.

Original entry on oeis.org

0, 0, 9, 153, 1449, 13617, 123129, 1113273, 10024569, 90266553, 812444409, 7312407993, 65812080249, 592312391937, 5330815197129, 47977369796313, 431796361188969, 3886167547854657, 34975508227845849, 314779576724952633, 2833016193198913689, 25497145762858874817

Offset: 0

Peter Kagey, Nov 02 2014

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, 0082 is a string of length four over a nine-letter alphabet that begins with a nontrivial palindrome (00).
9 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_9 with loops. (E.g., 0, 1, 1, 0, 7, 2, 6 is a valid walk with 7 steps and begins with the palindromic sequence '0110'.)
lim n -> infinity a(n)/9^n ~ 0.23302304262956242 is the probability that a random, infinite base-9 string begins with a nontrivial palindrome.

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

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

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

A[0]:= 0: A[1]:= 0:
for n from 1 to 99 do
 A[n+1]:= 9*A[n] + 9^ceil((n+1)/2) - A[ceil((n+1)/2)]
od:
seq(A[n],n=0..100); # Robert Israel, Dec 30 2014

a249642[n_] := Block[{f}, f[0] = f[1] = 0; f[x_] := 9*f[x - 1] + 9^Ceiling[x/2] - f[Ceiling[x/2]]; Table[f[i], {i, 0, n}]];
a249642[21] (* Michael De Vlieger, Dec 26 2014 *)

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

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

G.f. g(x) satisfies g(x) = 9*x^2*(1+9*x)/((1-9*x)*(1-9*x^2)) - (1+x)*g(x^2)/(x-9*x^2). - Robert Israel, Dec 30 2014

A252703 Number of strings of length n over a 10-letter alphabet that do not begin with a palindrome.

Original entry on oeis.org

0, 10, 90, 810, 8010, 79290, 792090, 7912890, 79120890, 791129610, 7911216810, 79111376010, 791112968010, 7911121767210, 79111209759210, 791112018471210, 7911120105591210, 79111200264782490, 791112001856695290, 7911120010655736090, 79111200098646144090

Offset: 0

Peter Kagey, Dec 20 2014

10 divides a(n) for all n.
lim n -> infinity a(n)/10^n ~ 0.79111200088977 is the probability that a random, infinite string over a 10-letter alphabet does not begin with a palindrome.
This sequence gives the number of walks on K_10 with loops that do not begin with a palindromic sequence.

			For n = 3, the first 20 of the a(3) = 810 solutions are (in lexicographic order) 011, 012, 013, 014, 015, 016, 017, 018, 019, 021, 022, 023, 024, 025, 026, 027, 028, 029, 031, 032.

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

A249643 gives the number of strings of length n over a 10-letter alphabet that DO begin with a palindrome.

Analogous sequences for k-letter alphabets: A252696 (k=3), A252697 (k=4), A252698 (k=5), A252699 (k=6), A252700 (k=7), A252701 (k=8), A252702 (k=9).

a252703[n_] := Block[{f},
  f[0] = f[1] = 0;
  f[x_] := 10*f[x - 1] + 10^Ceiling[(x)/2] - f[Ceiling[(x)/2]];
Prepend[Rest@Table[10^i - f[i], {i, 0, n}],0]]; a252703[20] (* Michael De Vlieger, Dec 26 2014 *)

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

a(n) = 10^n - A249643(n) for n > 0.

A342237 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that begin with a palindrome of two or more letters; n, k >= 1.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 3, 6, 1, 0, 4, 15, 14, 1, 0, 5, 28, 51, 30, 1, 0, 6, 45, 124, 165, 62, 1, 0, 7, 66, 245, 532, 507, 126, 1, 0, 8, 91, 426, 1305, 2164, 1551, 254, 1, 0, 9, 120, 679, 2706, 6605, 8788, 4683, 510, 1, 0, 10, 153, 1016, 5005, 16386, 33405, 35284, 14127, 1022, 1

Offset: 1

Peter Kagey, Mar 06 2021

			Table begins:
n\k | 1  2   3    4      5       6        7         8
----+------------------------------------------------
  1 | 0  1   1    1      1       1        1         1
  2 | 0  2   6   14     30      62      126       254
  3 | 0  3  15   51    165     507     1551      4683
  4 | 0  4  28  124    532    2164     8788     35284
  5 | 0  5  45  245   1305    6605    33405    167405
  6 | 0  6  66  426   2706   16386    99186    595986
  7 | 0  7  91  679   5005   35287   248731   1742839
  8 | 0  8 120 1016   8520   68552   551496   4415048

Peter Kagey, Antidiagonals n = 1..100, flattened

Rows: A000918 (n=2), A248122 (n=3), A249629 (n=4), A249638 (n=5), A249639 (n=6), A249640 (n=7), A249641 (n=8), A249642 (n=9), A249643 (n=10).

Columns: A000384 (k=3), A007588 (k=4).

T(n,1)    = 0.
T(n,2k)   = n*T(n,2k-1) + n^k - T(n,k).
T(n,2k+1) = n*T(n,2k) + n^(k+1) - T(n,k+1).

cp's OEIS Frontend

A248122 Number of strings of length n over a three-letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Ruby

Formula

A249629 Number of strings of length n over a 4-letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Ruby

Formula

A249638 Number of strings of length n over a 5-letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Ruby

Formula

A249639 Number of strings of length n over a 6 letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Ruby

Formula

A249640 Number of strings of length n over a 7-letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Ruby

Formula

A249641 Number of strings of length n over an 8-letter alphabet that begin with a nontrivial palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Ruby

Formula

A249642 Number of strings of length n over a 9-letter alphabet that begin with a nontrivial palindrome.

Views

Author