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.

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,5

Comments

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.

Links

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

Formula

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<n} phi(n/d) * T(d,k) where r(2d, k) = d *(stirling2(d,k)+stirling2(d,k+1)), r(2d+1, k) = (2d+1)*stirling2(d+1,k).

Example

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

Mathematica

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[d<n, EulerPhi[n/d] a[d, k], 0], {d, Divisors[n]}]; T[n_, k_]:=(Sum[(-1)^j * Binomial[k, j] * a[n, k - j], {j, 0, k}]) / k!; Table[T[n, k], {n, 25}, {k, n/2 + 1}] // Flatten (* Indranil Ghosh, Apr 07 2017 *)

Prog

(PARI)
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<n, eulerphi(n/d)*a(d, k), 0));
for(n=1, 15, for(k=1, n/2+1, print1( a(n, k), ", "); ); print(); );
(Python)
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 d<n])
def T(n, k): return (sum([(-1)**j * binomial(k, j) * a(n, k - j) for j in range(k + 1)]))//factorial(k)
for n in range(1, 21): print([T(n, k) for k in range(1, n//2 + 2)]) # Indranil Ghosh, Apr 07 2017

Crossrefs

Columns k=2..4 are A328688, A328689, A328690.

Row sums are A165137.

Partial row sums include A180249, A328692, A328693.

Cf. A284873, A284826.

Sequence in context: A146007 A061782 A074625 * A169659 A091724 A016576

Adjacent sequences: A284874 A284875 A284876 * A284878 A284879 A284880

Keyword

nonn,tabf

Author

Andrew Howroyd, Apr 04 2017

Status

approved