|
| |
|
|
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.
|
|
7
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
