Displaying 1-10 of 15 results found.
Irregular triangle read by rows: T(n,k) is the number of periodic palindromic structures of length n using exactly k different symbols, 1 <= k <= n/2 + 1.
+10
14
1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 1, 1, 6, 5, 1, 1, 7, 6, 1, 1, 13, 19, 7, 1, 1, 15, 25, 10, 1, 1, 25, 64, 43, 10, 1, 1, 31, 90, 65, 15, 1, 1, 50, 208, 220, 85, 13, 1, 1, 63, 301, 350, 140, 21, 1, 1, 99, 656, 1059, 618, 154, 17, 1, 1, 127, 966, 1701, 1050, 266, 28, 1
COMMENTS
For example, aaabbb is not a (finite) palindrome but it is a periodic palindrome. Permuting the symbols will not change the structure.
Equivalently, the number of necklaces, up to permutation of the symbols, which when turned over are unchanged. When comparing with the turned over necklace a rotation is allowed but a permutation of the symbols is not.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
EXAMPLE
Triangle starts:
1
1 1
1 1
1 3 1
1 3 1
1 6 5 1
1 7 6 1
1 13 19 7 1
1 15 25 10 1
1 25 64 43 10 1
1 31 90 65 15 1
1 50 208 220 85 13 1
1 63 301 350 140 21 1
1 99 656 1059 618 154 17 1
1 127 966 1701 1050 266 28 1
1 197 2035 4803 4065 1488 258 21 1
1 255 3025 7770 6951 2646 462 36 1
1 391 6250 21105 24915 12857 3222 410 26 1
1 511 9330 34105 42525 22827 5880 750 45 1
...
Example for n=6, k=2:
Periodic symmetry means results are either in the form abccba or abcdcb.
There are 3 binary words in the form abccba that start with 0 and contain a 1 which are 001100, 010010, 011110. Of these, 011110 is equivalent to 001100 after rotation.
There are 7 binary words in the form abcdcb that start with 0 and contain a 1 which are 000100, 001010, 001110, 010001, 010101, 011011, 011111. Of these, 011111 is equivalent to 000100, 010001 is equivalent to 001010 and 011011 is equivalent to 010010 from the first set.
There are therefore a total of 7 + 3 - 4 = 6 equivalence classes so T(6,2) = 6.
PROG
Ach(n, k=n) = {my(M=matrix(n, k, n, k, n>=k)); for(n=3, n, for(k=2, k, M[n, k]=k*M[n-2, k] + M[n-2, k-1] + if(k>2, M[n-2, k-2]))); M}
Prim(n, k=n\2+1) = {my(A=Ach(n\2+1, k), S=matrix(n\2+1, k, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
T(n, k=n\2+1) = {my(A=Prim(n, k)); Mat(vectorv(n, n, sumdiv(n, d, A[d, ])))}
{ my(A=T(20)); for(n=1, matsize(A)[1], print(A[n, 1..n\2+1])) } \\ Andrew Howroyd, Oct 02 2019 (PARI) \\ column sequence using above code.
Irregular triangle read by rows: T(n,k) is the number of primitive (period n) periodic palindromic structures using exactly k different symbols, 1 <= k <= n/2 + 1.
+10
14
1, 0, 1, 0, 1, 0, 2, 1, 0, 3, 1, 0, 4, 5, 1, 0, 7, 6, 1, 0, 10, 18, 7, 1, 0, 14, 25, 10, 1, 0, 21, 63, 43, 10, 1, 0, 31, 90, 65, 15, 1, 0, 42, 202, 219, 85, 13, 1, 0, 63, 301, 350, 140, 21, 1, 0, 91, 650, 1058, 618, 154, 17, 1, 0, 123, 965, 1701, 1050, 266, 28, 1
COMMENTS
Permuting the symbols will not change the structure.
Equivalently, the number of n-bead aperiodic necklaces (Lyndon words) with exactly k symbols, up to permutation of the symbols, which when turned over are unchanged. When comparing with the turned over necklace a rotation is allowed but a permutation of the symbols is not.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
T(n, k) = Sum_{d | n} mu(n/d) * A285012(d, k).
EXAMPLE
Triangle starts:
1
0 1
0 1
0 2 1
0 3 1
0 4 5 1
0 7 6 1
0 10 18 7 1
0 14 25 10 1
0 21 63 43 10 1
0 31 90 65 15 1
0 42 202 219 85 13 1
0 63 301 350 140 21 1
0 91 650 1058 618 154 17 1
0 123 965 1701 1050 266 28 1
0 184 2016 4796 4064 1488 258 21 1
0 255 3025 7770 6951 2646 462 36 1
0 371 6220 21094 24914 12857 3222 410 26 1
0 511 9330 34105 42525 22827 5880 750 45 1
...
Example for n=6, k=2:
There are 6 inequivalent solutions to A285012(6,2) which are 001100, 010010, 000100, 001010, 001110, 010101. Of these, 010010 and 010101 have a period less than 6, so T(6,2) = 6-2 = 4.
PROG
Ach(n, k=n) = {my(M=matrix(n, k, n, k, n>=k)); for(n=3, n, for(k=2, k, M[n, k]=k*M[n-2, k] + M[n-2, k-1] + if(k>2, M[n-2, k-2]))); M}
T(n, k=n\2+1) = {my(A=Ach(n\2+1, k), S=matrix(n\2+1, k, n, k, stirling(n, k, 2))); Mat(vectorv(n, n, sumdiv(n, d, moebius(d)*(S[(n/d+1)\2, ] + S[n/d\2+1, ] + if((n-d)%2, A[(n/d+1)\2, ] + A[n/d\2+1, ]))/if(d%2, 2, 1) )))}
{ my(A=T(20)); for(n=1, matsize(A)[1], print(A[n, 1..n\2+1])) } \\ Andrew Howroyd, Oct 01 2019 (PARI) \\ column sequence using above code.
Array read by antidiagonals: T(n,k) = number of primitive (aperiodic) palindromes of length n using a maximum of k different symbols (n >= 1, k >= 1).
+10
10
1, 2, 0, 3, 0, 0, 4, 0, 2, 0, 5, 0, 6, 2, 0, 6, 0, 12, 6, 6, 0, 7, 0, 20, 12, 24, 4, 0, 8, 0, 30, 20, 60, 18, 14, 0, 9, 0, 42, 30, 120, 48, 78, 12, 0, 10, 0, 56, 42, 210, 100, 252, 72, 28, 0, 11, 0, 72, 56, 336, 180, 620, 240, 234, 24, 0, 12, 0, 90, 72, 504, 294, 1290, 600, 1008, 216, 62
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
T(n,k) = Sum_{d | n} mu(n/d) * k^(ceiling(d/2)).
EXAMPLE
Table starts:
1 2 3 4 5 6 7 8 9 10 ...
0 0 0 0 0 0 0 0 0 0 ...
0 2 6 12 20 30 42 56 72 90 ...
0 2 6 12 20 30 42 56 72 90 ...
0 6 24 60 120 210 336 504 720 990 ...
0 4 18 48 100 180 294 448 648 900 ...
0 14 78 252 620 1290 2394 4088 6552 9990 ...
0 12 72 240 600 1260 2352 4032 6480 9900 ...
0 28 234 1008 3100 7740 16758 32704 58968 99900 ...
0 24 216 960 3000 7560 16464 32256 58320 99000 ...
...
Row 4 includes palindromes of the form abba but excludes those of the form aaaa, so T(4,k) is k*(k-1).
Row 6 includes palindromes of the forms aabbaa, abbbba, abccba but excludes those of the forms aaaaaa, abaaba, so T(6,k) is 2*k*(k-1) + k*(k-1)*(k-2).
MATHEMATICA
T[n_, k_] := DivisorSum[n, MoebiusMu[n/#]*k^Ceiling[#/2]&]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 05 2017 *)
PROG
(PARI)
a(n, k) = sumdiv(n, d, moebius(n/d) * k^(ceil(d/2)));
for(n=1, 10, for(k=1, 10, print1( a(n, k), ", "); ); print(); )
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.
+10
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
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.
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
Number of primitive (aperiodic) palindromic structures of length n using a maximum of two different symbols.
+10
5
1, 1, 0, 1, 1, 3, 2, 7, 6, 14, 12, 31, 27, 63, 56, 123, 120, 255, 238, 511, 495, 1015, 992, 2047, 2010, 4092, 4032, 8176, 8127, 16383, 16242, 32767, 32640, 65503, 65280, 131061, 130788, 262143, 261632, 524223, 523770, 1048575, 1047494, 2097151, 2096127, 4194162
COMMENTS
Permuting the symbols will not change the structure.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
a(n) = Sum_{d|n} mu(d)* A016116(n/d-1) for n > 0.
EXAMPLE
The a(9)=14 lexicographically earliest equivalence class members in the alphabet {0,1} are:
000010000
000101000
000111000
001000100
001010100
001101100
001111100
010000010
010101010
010111010
011000110
011010110
011101110
011111110
(End)
MATHEMATICA
Table[DivisorSum[n, MoebiusMu[#]*2^Floor[(n/# - 1)/2] &], {n, 46}] (* Michael De Vlieger, May 21 2021 *)
PROG
(PARI) a(n) = if(n==0, 1, sumdiv(n, d, moebius(d)*2^((n/d-1)\2))) \\ Andrew Howroyd, May 21 2021 (Python)
from sympy import mobius, divisors
def A056476(n): return sum(mobius(n//d)<<(d-1>>1) for d in divisors(n, generator=True)) if n else 1 # Chai Wah Wu, Feb 18 2024
Number of primitive (aperiodic) palindromic structures using a maximum of three different symbols.
+10
5
1, 1, 0, 1, 1, 4, 3, 13, 12, 39, 36, 121, 116, 364, 351, 1088, 1080, 3280, 3237, 9841, 9800, 29510, 29403, 88573, 88440, 265716, 265356, 797121, 796796, 2391484, 2390352, 7174453, 7173360, 21523238, 21520080, 64570064, 64566684, 193710244, 193700403, 581130368, 581120880
COMMENTS
Permuting the symbols will not change the structure.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
a(n) = Sum_{d|n} mu(d)* A124302(ceiling(n/(2*d))) for n > 0.
EXTENSIONS
a(0)=1 prepended and terms a(32) and beyond from Andrew Howroyd, Oct 02 2019
Number of primitive (aperiodic) palindromic structures using a maximum of four different symbols.
+10
5
1, 1, 0, 1, 1, 4, 3, 14, 13, 49, 46, 186, 181, 714, 700, 2789, 2780, 11050, 10997, 43946, 43895, 175259, 175088, 700074, 699875, 2798246, 2797536, 11188856, 11188191, 44747434, 44744591, 178973354, 178970560, 715860463, 715849600, 2863377048, 2863365834
COMMENTS
Permuting the symbols will not change the structure.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
a(n) = Sum_{d|n} mu(d)* A124303(ceiling(n/(2*d))) for n > 0.
EXTENSIONS
a(0)=1 prepended and terms a(32) and beyond from Andrew Howroyd, Oct 02 2019
Number of primitive (aperiodic) palindromic structures using a maximum of five different symbols.
+10
5
1, 1, 0, 1, 1, 4, 3, 14, 13, 50, 47, 201, 196, 854, 840, 3839, 3830, 18001, 17947, 86471, 86419, 421989, 421803, 2079474, 2079260, 10306747, 10305897, 51263890, 51263086, 255514354, 255510460, 1275163904, 1275160060, 6368612099, 6368594300, 31821472593, 31821454413
COMMENTS
Permuting the symbols will not change the structure.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
a(n) = Sum_{d|n} mu(d)* A056470(n/d) for n > 0.
EXTENSIONS
a(0)=1 prepended and terms a(32) and beyond from Andrew Howroyd, Oct 02 2019
Number of primitive (aperiodic) palindromic structures using a maximum of six different symbols.
+10
4
1, 1, 0, 1, 1, 4, 3, 14, 13, 50, 47, 202, 197, 875, 861, 4105, 4096, 20647, 20593, 109298, 109246, 601476, 601289, 3403126, 3402911, 19628059, 19627188, 114700263, 114699438, 676207627, 676203467, 4010090462, 4010086352, 23874361996, 23874341552, 142508723632
COMMENTS
Permuting the symbols will not change the structure.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
FORMULA
a(n) = Sum_{d|n} mu(d)* A056471(n/d) for n > 0.
EXTENSIONS
a(0)=1 prepended and terms a(32) and beyond from Andrew Howroyd, Oct 02 2019
Number of primitive (aperiodic) palindromic structures using exactly two different symbols.
+10
4
0, 0, 0, 1, 1, 3, 2, 7, 6, 14, 12, 31, 27, 63, 56, 123, 120, 255, 238, 511, 495, 1015, 992, 2047, 2010, 4092, 4032, 8176, 8127, 16383, 16242, 32767, 32640, 65503, 65280, 131061, 130788, 262143, 261632, 524223, 523770, 1048575, 1047494, 2097151, 2096127, 4194162
COMMENTS
Permuting the symbols will not change the structure. Identical to A056476 for n>1.
REFERENCES
M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
PROG
(Python)
from sympy import mobius, divisors
def A056481(n): return sum(mobius(n//d)<<(d-1>>1) for d in divisors(n, generator=True)) if n>1 else 0 # Chai Wah Wu, Feb 18 2024
Search completed in 0.008 seconds
| 