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

Author

Andrew Howroyd, Apr 04 2017

Keywords

• nonn
• tabf

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.

Examples

			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
		

Links

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

Crossrefs

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

Row sums are A165137.

Partial row sums include A180249, A328692, A328693.

Cf. A284873, A284826.

Programs

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[dIndranil Ghosh, Apr 07 2017 *)

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
				

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 dIndranil Ghosh, Apr 07 2017

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.