A165137 -id:A165137 - cp's OEIS frontend

A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.

1, 2, 1, 3, 4, 1, 4, 9, 8, 1, 5, 16, 21, 16, 1, 6, 25, 40, 57, 32, 1, 7, 36, 65, 136, 123, 52, 1, 8, 49, 96, 265, 304, 279, 100, 1, 9, 64, 133, 456, 605, 880, 549, 160, 1, 10, 81, 176, 721, 1056, 2125, 1768, 1209, 260, 1, 11, 100, 225, 1072, 1687, 4356, 4345, 4936, 2127, 424, 1

Offset: 1

Andrew Howroyd, Apr 04 2017

A double palindrome is a concatenation of two palindromes.
Also, number of words of length n using a maximum of k different symbols that are rotations of their reversals.
The sequence A165135 (number of n-digit positive papaya numbers) is 9/10 of the value of column 10.
All rows are polynomials of degree 1 + floor(n/2). - Andrew Howroyd, Oct 10 2017
From Petros Hadjicostas, Oct 27 2017: (Start)
Following Kemp (1982), we note that the formula by A. Howroyd below is equivalent to r(n,k) = Sum_{d|n} phi(d)*T(n/d,k), where r(2d, k) = d*(k+1)*k^d and r(2d+1, k) = (2d+1)*k^(d+1). Inverting (according to the theory of Dirichlet convolutions) we get T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.
We can easily prove that Sum_{n>=1} r(n,k)*x^n = R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2 (for each k>=1). We also have Sum_{n>=1} T(n,k)*x^n = Sum_{n>=1} Sum_{d|n} phi^{(-1)}(d)*r(n/d,k)*x^n. Letting m = n/d and noting that x^n = (x^d)^m, we can easily get the g.f. given in the formula section.
Note that r(n,1) = n, r(n,2) = A187272(n), r(n,3) = A187273(n), r(n,4) = A187274(n), and r(n,5) = A187275(n).
(End)

			Table starts:
  1   2    3     4     5      6      7       8       9      10 ...
  1   4    9    16    25     36     49      64      81     100 ...
  1   8   21    40    65     96    133     176     225     280 ...
  1  16   57   136   265    456    721    1072    1521    2080 ...
  1  32  123   304   605   1056   1687    2528    3609    4960 ...
  1  52  279   880  2125   4356   7987   13504   21465   32500 ...
  1 100  549  1768  4345   9036  16765   28624   45873   69940 ...
  1 160 1209  4936 14665  35736  75985  146224  260721  437680 ...
  1 260 2127  9112 27965  69756 150955  294512  530937  899380 ...
  1 424 4689 25216 93025 270936 670369 1471744 2948481 5494600 ...
From _Petros Hadjicostas_, Oct 27 2017: (Start)
We explain how to use the above formulae to find general expressions for some rows.
If p is an odd prime, then phi^{(-1)}(p) = 1-p. Since, also, phi^{(-1)}(1) = 1, we get T(p,k) = (1-p)*k+p*k^{(p+1)/2} for the p-th row above.
If m is a positive integer, then phi^{(-1)}(2^m) = -1, and so T(2^m,k) = 1+(k+1)*(2^{m-1}*k^{2^{m-1}}-1-Sum_{0<=s<=m-2} 2^s*k^{2^s}).
For example, if m=1, then T(2,k) = 1+(k+1)*(1*k-1-0) = k^2.
If m=2, then T(4,k) = 1+(k+1)*(2*k^2-1-k) = k*(2*k^2+k-2), which is the formula conjectured by C. Barker for sequence A187277 and verified by A. Howroyd.
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Chuan Guo, J. Shallit, and A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.

Columns 2-5 are A007055, A007056, A007057, A007058.
Rows 3-4 are A000567, A187277.
Cf. A023900, A165137, A165135.

r[d_, k_]:=If[OddQ[d], d*k^((d + 1)/2), (d/2)*(k + 1)*k^(d/2)]; a[n_, k_]:= r[n, k] - Sum[If[dIndranil Ghosh, Apr 07 2017 *)

r(d,k)=if (d % 2 == 0, (d/2)*(k+1)*k^(d/2), d*k^((d+1)/2));
a(n,k) = r(n,k) - sumdiv(n,d, if (d

from sympy import totient, divisors
def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if dIndranil Ghosh, Apr 07 2017

T(n, k) = r(n, k) - Sum_{d|n, d

From Petros Hadjicostas, Oct 27 2017: (Start)

T(n,k) = Sum_{d|n} phi^{(-1)}(d)*r(n/d,k), where r(n,k) is given above and phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function.

G.f.: For each k>=1, Sum_{n>=1} T(n,k)*x^n = Sum_{d>=1} phi^{(-1)}(d)*R(k,x^d), where R(k,x) = k*x*(x+1)*(k*x+1)/(1-k*x^2)^2.

(End)

From Richard L. Ollerton, May 07 2021: (Start)

T(n,k) = Sum_{i=1..n} phi^{(-1)}(n/gcd(n,i))*r(gcd(n,i),k)/phi(n/gcd(n,i)).

T(n,k) = Sum_{i=1..n} phi^{(-1)}(gcd(n,i))*r(n/gcd(n,i),k)/phi(n/gcd(n,i)).

r(n,k) = Sum_{i=1..n} T(gcd(n,i),k). (End)

A284877 Irregular triangle T(n,k) for 1 <= k <= n/2 + 1: T(n,k) = number of double palindrome structures of length n using exactly k different symbols.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 7, 2, 1, 15, 5, 1, 25, 21, 3, 1, 49, 42, 7, 1, 79, 122, 44, 4, 1, 129, 225, 90, 9, 1, 211, 570, 375, 80, 5, 1, 341, 990, 715, 165, 11, 1, 517, 2321, 2487, 930, 132, 6, 1, 819, 3913, 4550, 1820, 273, 13, 1, 1275, 8827, 14350, 8330, 2009, 203, 7

Offset: 1

Andrew Howroyd, Apr 04 2017

A double palindrome is the concatenation of two palindromes. Permuting the symbols will not change the structure. For the purposed of this sequence, valid palindromes include both the empty word and a singleton symbol.

			Triangle starts:
1
1     1
1     3
1     7      2
1    15      5
1    25     21       3
1    49     42       7
1    79    122      44       4
1   129    225      90       9
1   211    570     375      80       5
1   341    990     715     165      11
1   517   2321    2487     930     132      6
1   819   3913    4550    1820     273     13
1  1275   8827   14350    8330    2009    203      7
1  1863  14480   25515   15750    3990    420     15
1  2959  31802   75724   64004   23296   3920    296     8
1  4335  51425  132090  118167   44982   7854    612    17
1  6703 110928  376779  445275  229257  57078   7074   414   9
1  9709 177270  647995  807975  433713 111720  14250   855  19
1 15067 377722 1798175 2892470 2023135 698670 126300 12000 560 10
....
The first few structures are:
n = 1: a => 1
n = 2: aa; ab => 1 + 1
n = 3: aaa; aab, aba, abb => 1 + 3
n = 4: aaaa; aaab, aaba, aabb, abaa, abab, abba, abbb; abac, abcb => 1 + 7 + 2

Andrew Howroyd, Table of n, a(n) for n = 1..960

Columns k=2..4 are A328688, A328689, A328690.
Row sums are A165137.
Partial row sums include A180249, A328692, A328693.
Cf. A284873, A284826.

r[d_, k_]:=If[OddQ[d], d*k^((d + 1)/2), (d/2)*(k + 1)*k^(d/2)]; a[n_, k_]:= r[n, k] - Sum[If[dIndranil Ghosh, Apr 07 2017 *)

r(d,k)=if (d % 2 == 0, (d/2)*(stirling(d/2,k,2)+stirling(d/2+1,k,2)), d*stirling((d+1)/2, k,2));
a(n,k) = r(n,k) - sumdiv(n,d, if (d

from sympy import totient, divisors, binomial, factorial
def r(d, k): return (d//2)*(k + 1)*k**(d//2) if d%2 == 0 else d*k**((d + 1)//2)
def a(n, k): return r(n, k) - sum([totient(n//d)*a(d, k) for d in divisors(n) if dIndranil Ghosh, Apr 07 2017

T(n, k) = (Sum_{j=0..k} (-1)^j * binomial(k, j) * A284873(n, k-j)) / k!.

T(n, k) = r(n, k) - Sum_{d|n, d

A165610 The number of patterns of non-papaya words.

Original entry on oeis.org

0, 0, 1, 5, 31, 153, 778, 3890, 20693, 114733, 676347, 4207203, 27633048, 190864320, 1382896511, 10479940137, 82864510321, 682075572641, 5832740001550, 51724150291262, 474869801907015, 4506715684635739, 44152005758171637, 445958868912515927, 4638590331538888532

Offset: 1

Tanya Khovanova, Sep 22 2009

nonn

Papaya words are defined as palindromes or concatenations of two palindromes.

			The only three-character non-papaya pattern is abc - words with all distinct letters. Four-character non-papaya patterns are: aabc, abbc, abcc, abca, abcd.

Tanya Khovanova, Papaya Words and Numbers

Cf. A165137, A165135, A165136, A165137, A165611.

R[k_?EvenQ] := (1/2)*k*(BellB[1 + k/2] + BellB[k/2]);
R[k_?OddQ] := k*BellB[1 + (k - 1)/2];
b[0] = 1; b[n_] := b[n] = R[n] - Sum[EulerPhi[n/d]*b[d], {d, Most[ Divisors[n]]}];
a[n_] := BellB[n] - b[n];
Array[a, 25] (* Jean-François Alcover, Jul 02 2018, after Andrew Howroyd *)

a(n) = A000110(n) - A165137(n).

a(7)-a(25) from Andrew Howroyd, Mar 29 2016

A165611 The number of n-digit non-papaya numbers.

Original entry on oeis.org

0, 0, 648, 7128, 85536, 870750, 8937054, 89606088, 899190558, 8995054860, 89990100090, 899940633714, 8999883000108, 89999307063540, 899998650010008, 8999992080398088, 89999984700000144, 899999910900869040, 8999999829000000162, 89999999010004961988

Offset: 1

Tanya Khovanova, Sep 22 2009

These are numbers that are neither palindromes nor concatenations of two palindromes. Three digit numbers that are non-papaya are numbers with all distinct digits. There are 9*9*8 of them: 648.

Tanya Khovanova, Papaya Words and Numbers

Cf. A165135, A165136, A165137, A165610.

a(n) = A052268(n) - A165135(n).

a(6)-a(20) from Andrew Howroyd, Mar 29 2016

A165136 a(n) is the number of patterns for n-digit papaya numbers.

Original entry on oeis.org

1, 2, 4, 10, 21, 50, 99, 250, 454, 1242, 2223, 6394, 11389, 35002, 62034, 202010, 359483, 1233518, 2203507, 7944100, 14249715, 53810836, 96911168, 382258438, 691048071, 2840120987, 5152403569, 22010733048, 40059670261, 177444599715

Offset: 1

Sergei Bernstein and Tanya Khovanova, Sep 04 2009

Papaya numbers are concatenations of two palindromes or palindromes themselves (think of "papaya" as the concatenation of the palindromes "pap" and "aya").
The actual number of n-digit papaya numbers is A165135. If the pattern is "aa", for example, inserting digits 1 to 9 for "a" gives 9 positive 2-digit numbers, 11, 22, ..., 99. The pattern "ab" inserting a<>b gives 10, 12, ..., 98, that is 9*9 = 81 positive 2-digit numbers. (9 different choices for "a" because leading 0's are not allowed, and for each "a" 9 different choices of "b".) So the a(2) = 2 different patterns represent 9+81 = A165135(2) different 2-digit numbers.
The first 19 terms of this sequence are the same as in A165137. Then the sequences start to differ, because the number of patterns in an infinite alphabet can be larger than patterns in the 10-digits-alphabet of ordinary numbers: A165137(20) = a(20)+10. - Tanya Khovanova, Oct 01 2009 (Since at most 2 symbols in a papaya number can be present only once, to require 11 symbols takes a length of 2 + (11-2)*2 = 20. The 10 strings for A165137(20) not counted here are abcdefghijkjihgfedbc, abacdefghijkjihgfedc, abcbadefghijkjihgfed, ..., abcdefghijihgfedcbak. - Franklin T. Adams-Watters, Apr 10 2011)

			There are two types of two-digit papaya numbers: aa, or ab. Hence a(2) = 2.
There are four types of three-digit papaya numbers: aaa, aab, aba, abb. Hence a(3) = 4.
There is no pattern of the form "abcdefghijkl" contributing to a(12), because this requires 12 different letters in the alphabet, and the standard numbers alphabet provides only ten different digits 0-9.

Tanya Khovanova, Papaya Words and Numbers

Cf. A165135, A165137, A165610, A165611.

a(n) = R(n) - Sum_{d|n,dAndrew Howroyd, Mar 29 2016

Three more terms from R. J. Mathar, Sep 25 2009
Keyword:base added, comment expanded - R. J. Mathar, Aug 29 2010
a(10)-a(14) from Franklin T. Adams-Watters, Apr 10 2011
a(15)-a(30) from Andrew Howroyd, Mar 29 2016

A285013 Number of periodic palindromic structures of length n using an infinite alphabet.

Original entry on oeis.org

1, 1, 2, 2, 5, 5, 13, 15, 41, 52, 144, 203, 578, 877, 2605, 4140, 12869, 21147, 69178, 115975, 398766, 678570, 2450406, 4213597, 15939952, 27644437, 109304914, 190899322, 787016238, 1382958545, 5931824093, 10480142147, 46673259309, 82864869804, 382473282504

Offset: 0

Andrew Howroyd, Apr 07 2017

nonn

See A285012 for additional information. Permuting the symbols will not change the structure.

Andrew Howroyd, Table of n, a(n) for n = 0..500

Row sums of A285012.

Cf. A165137, A284841, A285042.

\\ Requires T from A285012.
seq(n)={my(A=T(n)); concat([1], vector(n, i, vecsum(A[i,])))} \\ Andrew Howroyd, Oct 02 2019

a(0)=1 prepended and terms a(28) and beyond from Andrew Howroyd, Oct 02 2019

A188792 Table with T(n,k) the number of word structures of length n which can be decomposed into k palindromes but not fewer.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 8, 3, 2, 5, 16, 18, 8, 5, 5, 45, 57, 56, 25, 15, 15, 84, 220, 213, 203, 90, 52, 15, 235, 583, 1005, 909, 826, 364, 203, 52, 402, 1965, 3358, 4914, 4247, 3708, 1624, 877, 52, 1190, 4737, 13250, 19340, 25735, 21511, 18127, 7893, 4140, 203, 2020

Offset: 1

Franklin T. Adams-Watters, Apr 10 2011

Every singleton string is a palindrome, so decomposition into n strings is always possible.

T(n,n) = B(n-2), where B = A000110 is the Bell numbers. A string has no nontrivial decomposition into palindromes iff each symbol is different from the two preceding symbols. Processing from right to left, decrease each symbol by the number of smaller symbols of the two preceding it, and dropping the first two symbols; this yields an arbitrary string of length n-2. E.g., [1,2,3,1,4] => [1,1,2], [1,2,3,4,2] => [1,2,2]. Similarly, T(n,n-1) counts strings contributing to T(n-1,n-1) with one symbol repeated, so T(n,n-1) = B(n-3)*(n-1).

			T(4,3) = 3; the 3 strings are 1,1,2,3; 1,2,2,3; and 1,2,3,3. Greedy parsing of 1,1,2,1 gives 1,1|2|1 into 3 parts, but 1|1,2,1 is better.
The table starts:
  1
  1  1
  2  2  1
  2  8  3  2
  5 16 18  8  5

Franklin T. Adams-Watters, Rows n = 1..14, flattened

Cf. row sums etc. A000110, 1st column A188164, sum 1st 2 columns A165137.

numpal(v)={local(w,n);w=vector((n=#v)+1,i,i-1);
for(t=2,2*n,forstep(i=t\2,max(1,t-n),-1,if(v[i]!=v[j=t-i],break);w[j+1]=min(w[j+1],w[i]+1)));
w[n+1]}
nextsetpart(v)={local(w,n);w=vector(n=#v);w[1]=1;for(k=2,n,w[k]=max(w[k-1],v[k]));
while(n>1,if(v[n]<=w[n-1],v[n]++;return(v));v[n]=1;n--);vector(#v+1,i,1)}
al(n)=local(v,r);v=vector(n,i,1);r=vector(n);while(#v==n,r[numpal(v)]++;v=nextsetpart(v));r

Showing 1-7 of 7 results.

cp's OEIS Frontend

A284873 Array read by antidiagonals: T(n,k) = number of double palindromes of length n using a maximum of k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A284877 Irregular triangle T(n,k) for 1 <= k <= n/2 + 1: T(n,k) = number of double palindrome structures of length n using exactly k different symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A165610 The number of patterns of non-papaya words.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165611 The number of n-digit non-papaya numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A165136 a(n) is the number of patterns for n-digit papaya numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A285013 Number of periodic palindromic structures of length n using an infinite alphabet.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A188792 Table with T(n,k) the number of word structures of length n which can be decomposed into k palindromes but not fewer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI