|
%I #104 Sep 29 2023 05:02:56
%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,3,2,3,1,1,1,1,3,3,3,3,
%T 1,1,1,1,4,3,6,3,4,1,1,1,1,4,4,6,6,4,4,1,1,1,1,5,4,10,6,10,4,5,1,1,1,
%U 1,5,5,10,10,10,10,5,5,1,1,1,1,6,5,15,10,20,10,15,5,6,1,1,1,1,6,6,15,15,20,20,15,15,6,6,1,1,1,1,7,6,21,15,35,20,35,15,21,6,7,1,1
%N Triangle T(n,k), 0 <= k <= n, read by rows, with T(2n,2k) = T(2n+1,2k) = T(2n+1,2k+1) = T(2n+2,2k+1) = binomial(n,k).
%C From _John P. McSorley_, Aug 24 2010: (Start)
%C A combinatorial interpretation of this triangle is as follows:
%C Ignore the first column of 1's of the above triangle and the call the (n,k) entry of the new triangle formed RE(n,k).
%C Hence row 8 of the 'RE(n,k)' triangle is 1 4 3 6 3 4 1 1.
%C Now see sequence A180171 for the definition of a k-reverse of n.
%C Briefly, a k-reverse of n is a k-composition of n which is cyclically equivalent to its reverse.
%C Sequence A180171 is the 'R(n,k)' triangle read by rows where R(n,k) is the total number of k-reverses of n.
%C Then RE(n,k) is the number of k-reverses of n up to cyclic equivalence.
%C In sequence A180171 we have R(8,3)=9 because there are 9 3-reverses of 8.
%C In cyclically equivalent classes: {116,611,161} {224,422,242}, and {233,323,332}; since there are 3 such classes we have RE(8,3)=3.
%C Similarly, in A180171, we have R(8,6)=21 because all 21 6-compositions of 8 are 6-reverses of 8, but they come in 4 cyclically equivalent classes (with representatives 111113, 111122, 111212, and 112112) hence RE(8,6)=4.
%C There is another (equivalent) interpretation for RE(n,k) involving k-subsets of Z_n, the integers modulo n, and the multiplier -1. See the McSorley/Schoen paper below for more details.
%C In this case it is convenient to count k-subsets up to dihedral equivalence, rather than cyclic equivalence.
%C The counts are the same. The row sums of the 'RE(n,k)' triangle give sequence A052955.
%C (End)
%C From _Petros Hadjicostas_, Oct 12 2017: (Start)
%C When 1 <= k <= n, each cyclically equivalence class of k-reverses of n is a "Sommerville symmetrical cyclic composition," which was introduced by Sommerville (1909). On pp. 301-304 of his paper, he proves that the number of such (equivalence classes of) compositions of n with length k is exactly T(n,k) = RE(n,k).
%C The equivalence class of a Sommerville symmetrical cyclic composition contains at least one palindromic composition (type I) or a composition that becomes a palindromic composition if we remove the first part (type II). A composition with only one part is a palindromic composition of both types. Hadjicostas and Zhang (2017) have proved that each equivalence class of k-reverses of n contains exactly two compositions that are either of type I or type II (except in the case when k | n and all the parts are the same).
%C For example, consider the case with n=8 and k=3, where RE(8,3)=3. As pointed above by J. P. McSorley, in cyclically equivalent classes we have {116,611,161} {224,422,242}, and {233,323,332}. The first class contains one composition of type I (161) and one of type II (611); the second class contains one composition of type I (242) and one of type II (422); and the last class contains one composition of type I (323) and one of type II (233).
%C When n = 6 and k = 4, the class of 4-reverses {1221, 2211, 2112, 1122} contains two compositions of type I (1221 and 2112).
%C If A is a set of positive integers and 1 <= k <= n, let RE_A(n,k) be the total number of Sommerville symmetrical cyclic compositions of n with length k and parts only in A (= number of cyclically equivalence classes of k-reverses of n with parts only in A). Then the g.f. of RE_A(n,k) is Sum_{n,k >= 1} RE_A(n,k) * x^n * y^k = (-1/2) + (1 + y * f_A(x))^2/(2 * (1 - y^2 * f_A(x^2)), where f_A(x) = Sum_{m in A} x^m. (For this sequence, A = all positive integers.)
%C Sequence A292200 contains the total number of Sommerville symmetrical cyclic compositions of n that are Carlitz (compositions that have length one, or have length >= 1 and adjacent parts of the composition on a circle are distinct).
%C (End)
%D John P. McSorley, Counting k-compositions of n with palindromic and related structures, preprint, 2010. [From _John P. McSorley_, Aug 24 2010]
%H Andrew Howroyd, <a href="/A119963/b119963.txt">Table of n, a(n) for n = 0..1274</a>
%H P. Hadjicostas and L. Zhang, <a href="https://www.fq.math.ca/Papers1/55-1/HadjicostasZhang10252016.pdf">Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer</a>, Fibonacci Quarterly 55 (2017), 54-73.
%H John P. McSorley and Alan H. Schoen, <a href="http://dx.doi.org/10.1016/j.disc.2012.08.021">Rhombic tilings of (n,k)-Ovals, (n, k, lambda)-Cyclic Difference Sets, and Related Topics</a>, Discrete Math., 313 (2013), 129-154. - From _N. J. A. Sloane_, Nov 26 2012
%H D. M. Y. Sommerville, <a href="https://doi.org/10.1112/plms/s2-7.1.263">On certain periodic properties of cyclic compositions of numbers</a>, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
%F G.f.: Sum_{n,k >= 1} RE(n,k)*x^n*y^k = (1+x*y-x^2)*x*y/((1-x)*(1-x^2-x^2*y^2)). - _Petros Hadjicostas_, Oct 12 2017
%F G.f.: Sum_{n,k >= 0} T(n,k)*x^n*y^k = (1+x*y)*(1+x)/(1-x^2-x^2*y^2) as above, but adding 1/(1-x) to include n,k = 0 terms. - _Paul Sampson_, Nov 22 2017
%F T(n, k) = binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) for 0 <= k <= n. - _Petros Hadjicostas_, May 29 2019
%e Triangle begins (with rows for n >= 0 and columns for k >= 0) as follows:
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 1, 1, 1, 1;
%e 1, 1, 2, 1, 1;
%e 1, 1, 2, 2, 1, 1;
%e 1, 1, 3, 2, 3, 1, 1;
%e 1, 1, 3, 3, 3, 3, 1, 1;
%e 1, 1, 4, 3, 6, 3, 4, 1, 1;
%e 1, 1, 4, 4, 6, 6, 4, 4, 1, 1;
%e ...
%t Table[Binomial[Floor[(n - Boole[OddQ@ k])/2], Floor[k/2]], {n, 0, 10}, {k, 0, n}] (* _Michael De Vlieger_, Oct 11 2017, after PARI by _Andrew Howroyd_ *)
%o (PARI) T(n,k) = binomial((n-k%2)\2, k\2); \\ _Andrew Howroyd_, Oct 08 2017
%Y Cf. A007318, A292200, A051159.
%Y The row sums of the T(n,k) triangle give sequence A029744 whose terms are 1 more than the terms of sequence A052955 (row sums of RE(n,k) triangle). See sequence A029744 where there is a reference to necklaces relevant to the combinatorial interpretation and the McSorley and McSorley/Schoen papers given here. - _John P. McSorley_, Aug 31 2010
%K nonn,tabl
%O 0,13
%A _Philippe Deléham_, Aug 02 2006
%E Corrected by _Philippe Deléham_, Aug 20 2010
|
