CINXE.COM
A054252 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A054252 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A054252" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA054252">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A054252 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A054252 </div> <div class=seqname> Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones under action of dihedral group of the square D_4. </div> </div> <div class=scorerefs> 25 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 8, 16, 23, 23, 16, 8, 3, 1, 1, 3, 21, 77, 252, 567, 1051, 1465, 1674, 1465, 1051, 567, 252, 77, 21, 3, 1, 1, 6, 49, 319, 1666, 6814, 22475, 60645, 136080, 256585, 410170, 559014, 652048, 652048, 559014, 410170, 256585, 136080</div> <div class=seqdatalinks> (<a href="/A054252/list">list</a>; <a href="/A054252/graph">graph</a>; <a href="/search?q=A054252+-id:A054252">refs</a>; <a href="/A054252/listen">listen</a>; <a href="/history?seq=A054252">history</a>; <a href="/search?q=id:A054252&fmt=text">text</a>; <a href="/A054252/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,6</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Feb 19 2013: (Start)</div> <div class=sectline>Cycle indices for n=2,3,4,5 respectively are:</div> <div class=sectline>(1/8)(s[1]^4 + 2*s[1]^2*s[2] + 3*s[2]^2 + 2*s[4]).</div> <div class=sectline>(1/8)(s[1]^9 + 4*s[1]^3*s[2]^3 + s[1]s[2]^4 + 2*s[1]*s[4]^2).</div> <div class=sectline>(1/8)(s[1]^16 + 2*s[1]^4*s[2]^6 + 2*s[4]^4 + 3*s[2]^8).</div> <div class=sectline>(1/8)(s[1]^25 + 4*s[1]^5*s[2]^10 + 2*s[1]*s[4]^6 + s[1]*s[2]^12).</div> <div class=sectline>(End)</div> <div class=sectline>Also the number of equivalence classes of ways of placing k 1 X 1 tiles in an n X n square under all symmetry operations of the square. - <a href="/wiki/User:Christopher_Hunt_Gribble">Christopher Hunt Gribble</a>, Feb 17 2014</div> <div class=sectline>From <a href="/wiki/User:Wolfdieter_Lang">Wolfdieter Lang</a>, Oct 03 2016: (Start)</div> <div class=sectline>The cycle index G(n) for a square n X n grid with squares coming in two colors with k squares of one color is for the D_4 group (with 8 elements R(90)^j, S R(90)^j, j=0..3)</div> <div class=sectline> (s[1]^(n^2) + s[2]^(n^2/2) +2*s[4]^(n^2/4))/8 + (s[2]^(n^2/2) + s[1]^n*s[2]^((n^2-n)/2))/4 if n is even,</div> <div class=sectline> s[1]*((s[1]^(n^2-1) + s[2]^((n^2-1)/2) + 2*s[4]^((n^2-1)/4))/8) + s[1]^n*s[2]^(n*(n-1)/2)/2 if n is odd.</div> <div class=sectline>See the above comment by <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a> for n=2..5.</div> <div class=sectline>The figure counting series is c(x) = 1 + x for coloring, say black and white.</div> <div class=sectline>Therefore the counting series is C(n,x) = G(n) with substitution s[2^j] = c(x^(2*j)) = 1 + x^(2^j) for j=0,1,2. Row n gives the coefficients of C(n,x) in rising (or falling) order. This follows from P贸lya's counting theorem. See the Harary-Palmer reference, p. 42, eq. (2.4.6), and eq. (2.2.11) with n=4 on p. 37 for the cycle index of D_4.</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 42, (2.4.6), p. 37, (2.2.11).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Heinrich Ludwig, <a href="/A054252/b054252.txt">Rows n = 0..16, flattened</a></div> <div class=sectline><a href="/index/Gre#groups">Index entries for sequences related to groups</a></div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>T(3,2) = 8 because there are 8 nonisomorphic 3 X 3 binary matrices with two ones under action of D_4:</div> <div class=sectline> [0 0 0] [0 0 0] [0 0 0] [0 0 0]</div> <div class=sectline> [0 0 0] [0 0 0] [0 0 1] [0 0 1]</div> <div class=sectline> [0 1 1] [1 0 1] [0 1 0] [1 0 0]</div> <div class=sectline>---------------------------------</div> <div class=sectline> [0 0 0] [0 0 0] [0 0 0] [0 0 1]</div> <div class=sectline> [0 1 0] [0 1 0] [1 0 1] [0 0 0]</div> <div class=sectline> [0 0 1] [0 1 0] [0 0 0] [1 0 0]</div> <div class=sectline>Triangle T(n,k) begins:</div> <div class=sectline>1;</div> <div class=sectline>1, 1;</div> <div class=sectline>1, 1, 2, 1, 1;</div> <div class=sectline>1, 3, 8, 16, 23, 23, 16, 8, 3, 1;</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>(* As a triangle *) Prepend[Prepend[Table[CoefficientList[CycleIndexPolynomial[</div> <div class=sectline>GraphData[{"Grid", {n, n}}, "AutomorphismGroup"], Table[Subscript[s, i], {i, 1, 4}]] /. Table[Subscript[s, i] -> 1 + x^i, {i, 1, 4}], x], {n, 2, 10}], {1, 1}], {1}] // Grid (* <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Aug 09 2016 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(Sage)</div> <div class=sectline>def T(n, k):</div> <div class=sectline> if n == 0 or k == 0 or k == n*n:</div> <div class=sectline> return 1</div> <div class=sectline> grid = graphs.Grid2dGraph(n, n)</div> <div class=sectline> m = grid.automorphism_group().cycle_index().expand(2, 'b, w')</div> <div class=sectline> b, w = m.variables()</div> <div class=sectline> return m.coefficient({b: k, w: n*n-k})</div> <div class=sectline>[T(n, k) for n in range(6) for k in range(n*n + 1)] # <a href="/wiki/User:Freddy_Barrera">Freddy Barrera</a>, Nov 23 2018</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Cf. <a href="/A014409" title="Number of inequivalent ways (mod D_4) a pair of checkers can be placed on an n X n board.">A014409</a>, <a href="/A019318" title="Number of inequivalent ways of choosing n squares from an n X n board, considering rotations and reflections to be the same.">A019318</a>, <a href="/A054247" title="Number of n X n binary matrices under action of dihedral group of the square D_4.">A054247</a> (row sums), <a href="/A054772" title="Triangle T(n,k) of n X n binary matrices with k=0..n^2 ones, up to rotational symmetry.">A054772</a>.</div> <div class=sectline>Sequence in context: <a href="/A343555" title="a(n) = numerator(max_{k=2..n}(A191898(n, k)/k)), n>=2.">A343555</a> <a href="/A251660" title="Table of coefficients in functions R(n,x) defined by R(n,x) = exp( n*x*G(n,x)^(n-1) ) / G(n,x)^(n-1) where G(n,x) = 1 + x*G(...">A251660</a> <a href="/A279453" title="Triangle read by rows: T(n, k) is the number of nonequivalent ways to place k points on an n X n square grid so that no more...">A279453</a> * <a href="/A240472" title="Primorial expansion of e.">A240472</a> <a href="/A366836" title="a(1) = 1 and a(n) = prime(a(n-1)+n) mod (a(n-1)+n).">A366836</a> <a href="/A007442" title="Inverse binomial transform of primes.">A007442</a></div> <div class=sectline>Adjacent sequences: <a href="/A054249" title="Alternately subtract and add 1 to digits in decimal expansion of Pi.">A054249</a> <a href="/A054250" title="Triangular array T(n,0)= 1, T(n,k) = sum_{j=1..min(n,k)} (n-j+1)*T(j,k-j) if k>0.">A054250</a> <a href="/A054251" title="a(0) = 1; a(n) = Sum_{0 <= k < n and gcd(k, n) != 1} a(k).">A054251</a> * <a href="/A054253" title="a(n) = n + max{ a(i)*a(n-i) ; 1 <= i <= n-1 }, a(n) = n for n <= 2.">A054253</a> <a href="/A054254" title="a(n) is n plus the minimum of the a(i)*a(n-i) of the previous i = 1..n-1.">A054254</a> <a href="/A054255" title="Triangle T(n,k) (n >= 1, 0<=k<=n) giving number of preferential arrangements of n things beginning with k (transposed, then ...">A054255</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="it is very easy to produce terms of sequence">easy</span>,<span title="a sequence of nonnegative numbers">nonn</span>,<span title="an irregular (or funny-shaped) array of numbers made into a sequence by reading it row by row">tabf</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, May 04 2000</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified November 28 19:48 EST 2024. Contains 378206 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>