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
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
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[d
-
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 d
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
A180171 Triangle read by rows: R(n,k) is the number of k-reverses of n.
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 4, 10, 5, 1, 1, 6, 9, 12, 15, 6, 1, 1, 7, 9, 19, 15, 21, 7, 1, 1, 8, 10, 24, 30, 20, 28, 8, 1, 1, 9, 12, 36, 26, 54, 28, 36, 9, 1, 1, 10, 15, 40, 50, 60, 70, 40, 45, 10, 1, 1, 11, 13, 53, 50, 108, 70, 106, 39, 55, 11, 1, 1, 12, 18, 60, 75, 120
Offset: 1
Comments
A k-composition of n is an ordered collection of k positive integers (parts) which sum to n.
Two k-compositions are cyclically equivalent if one can be obtained from the other by a cyclic permutation of its parts.
The reverse of a k-composition is the k-composition obtained by writing its parts in reverse.
For example the reverse of 123 is 321.
A k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.
For example 114 is a 3-reverse of 6 since its set of cyclic equivalents {114,411,141} contains its reverse 411. But 123 is not a 3-reverse of 6 since its set of cyclic equivalents {123,312,231} does not contain its reverse 321.
Examples
The triangle begins
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 4 10 5 1
1 6 9 12 15 6 1
1 7 9 19 15 21 7 1
1 8 10 24 30 20 28 8 1
1 9 12 36 26 54 28 36 9 1
For example row 8 is 1 7 9 19 15 21 7 1
We have R(8,3)=9 because there are 9 3-reverses of 8. In classes: {116,611,161} {224,422,242}, and {233,323,332}.
We have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8.
References
- John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
Links
- Robert G. Wilson v, Table of n, a(n) for n = 1..500.
- Petros Hadjicostas, Proofs of two formulae on the number of k-inverses of n
Programs
-
Mathematica
f[n_Integer, k_Integer] := Block[{c = 0, j = 1, ip = IntegerPartitions[n, {k}]}, lmt = 1 + Length@ ip; While[j < lmt, c += g[ ip[[j]]]; j++ ]; c]; g[lst_List] := Block[{c = 0, len = Length@ lst, per = Permutations@ lst}, While[ Length@ per > 0, rl = Union[ RotateLeft[ per[[1]], # ] & /@ Range@ len]; If[ MemberQ[rl, Reverse@ per[[1]]], c += Length@ rl]; per = Complement[ per, rl]]; c]; Table[ f[n, k], {n, 13}, {k, n}] // Flatten (* Robert G. Wilson v, Aug 25 2010 *) -
PARI
\\ here p(n,k) is A119963, AR(n,k) is A180279. p(n,k) = binomial((n-k%2)\2, k\2); AR(n,k) = k*sumdiv(gcd(n,k), d, moebius(d) * p(n/d, k/d)); T(n,k) = sumdiv(gcd(n,k), d, AR(n/d,k/d)); for(n=1, 10, for(k=1, n, print1(T(n,k), ", ")); print) \\ Andrew Howroyd, Oct 08 2017
Formula
R(n,k) = Sum_{d|gcd(n,k)} A180279(n/d, k/d). - Andrew Howroyd, Oct 08 2017
From Petros Hadjicostas, Oct 21 2017: (Start)
For proofs of these formulae, see the links.
R(n,k) = Sum_{d|gcd(n,k)} phi^{(-1)}(d)*(k/d)*A119963(n/d, k/d), where phi^{(-1)}(d) = A023900(d) is the Dirichlet inverse function of Euler's totient function.
G.f.: Sum_{s >= 1} phi^{(-1)}(s)*g(x^s, y^s), where phi^{(-1)}(s) = A023900(s) and g(x,y) = (x*y+x+1)*(x*y-x+1)*(x+1)*x*y/(x^2*y^2+x^2-1)^2.
(End)
Extensions
a(56) onwards from Robert G. Wilson v, Aug 25 2010
A180750 a(n) = DP(n) is the total number of k-double-palindromes of n, where 2 <= k <= n.
0, 1, 3, 6, 13, 21, 43, 68, 116, 185, 311, 464, 757, 1157, 1741, 2720, 4081, 6214, 9199, 14078, 20353, 31405, 45035, 68930, 98224, 150761, 212706, 326362, 458725, 702209, 983011, 1504400, 2096441, 3207137, 4456139, 6808172, 9437149, 14408669, 19921297, 30393800
Offset: 1
Comments
A k-composition of n is an ordered collection of k positive integers (parts) which sum to n. A palindrome is a word which is the same when written backwards. A k-double-palindrome of n (see sequence A180653) is a k-composition of n which is the concatenation of two palindromes, PP' = P|P', where both |P|, |P'| >= 1.
For example, 1123532 = 11|23532 is a 7-double-palindrome of 17 since both 11 and 23532 are palindromes.
The n-th term of this sequence is DP(n), the total number of k-double-palindromes of n, where 2 <= k <= n.
For example, DP(6)=21 because there are 21 k-double-palindromes of 6 for k=2,3,4,5, or 6. They are:
(with k=2) 15=1|5, 51=5|1, 24=2|4, 42=4|2, 33=3|3,
(with k=3) 114=11|4, 411=4|11, 222=2|22,
(with k=4) 1113=111|3, 3111=3|111, 1311=131|1, 1131=1|131, and 1122=11|22, 2211=22|11, 1212=121|2, 2121=2|121,
(with k=5) 11112=1111|2, 21111=2|1111, 12111=121|11, 11121=11|121,
(with k=6) 111111=1|11111.
References
- John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010.
Crossrefs
Formula
G.f.: Sum_{n>=1} phi^{(-1)}(n)*f(x^n) - Sum_{n>=1} mu(n)*g(x^n), where phi^{(-1)}(n) = A023900(n) is the Dirichlet inverse of Euler's totient function, mu(n) = A008683(n) is the Mobius function, f(x) = x*(x+1)*(2*x+1)/(1-2*x^2)^2, and g(x) = x*(1+2*x)/(1-2*x^2). - Petros Hadjicostas, Nov 06 2017
Extensions
a(11)-a(18) from Donovan Johnson, Oct 22 2010
a(11)-a(18) corrected by and a(19)-a(40) from Petros Hadjicostas and Andrew Howroyd, Nov 03 2017
Comments