Wikipedia:Reference desk/Archives/Mathematics/2014 May 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 1

Number of possible configurations of squares

I am working on some interesting problem I thought about:

Take an n x n square grid where the squares are colored black and white in an alternating fashion, i.e. like

I want to determine the number of all possible large squares which can be constructed by rearranging the small black and white squares that remain incongruent under rotations and reflections for each n. For example, it is easy to see that for n = 2 there are only 2 possible configurations, namely

and the same configuration where one black and one white square switched places.

For n = 3 I discovered that there are 22 possible configurations. My question is, is there a method for determining the number of possible configuration for arbitrary n? The number appears to be growing quickly for increasing n. For example, for n = 4, I already found over 100 configurations by rearranging the squares 'by hand' (I don't know how many there will be), but this method seems to become practically infeasible for larger n. Is there perhaps a known formula for computing those values? -- Toshio Yamaguchi 10:18, 1 May 2014 (UTC)

Here is an illustration depicting the 22 possible configurations for n = 3.

-- Toshio Yamaguchi 11:30, 1 May 2014 (UTC)

Also as a note: I just realized you could get more rotationally and reflectionally incongruent squares by 'inverting' the colors. I wouldn't count a configuration and it's inverse as two separate configurations because they are combinatorially identical. Therefore, the correct number for n = 3 remains 22 for my purposes. -- Toshio Yamaguchi 12:19, 1 May 2014 (UTC)

There are k black fields. If n is even then k=n²/2. If n is odd then k=(n²+1)/2. The number of ways to choose k fields is the binomial coefficient ${\tbinom {n^{2}}{k}}$. There are 8 rotations and reflections, so the number of configurations S_n satisfies the inequality ${\tbinom {n^{2}}{k}}/8\leq S_{n}\leq {\tbinom {n^{2}}{k}}$. So 16 ≤ S₃ ≤ 126 and 1609 ≤ S₄ ≤ 12870, in agreement with your result S₃ =22 and S₄ > 100. This is hopefully a step in the right direction. Bo Jacoby (talk) 13:16, 1 May 2014 (UTC).

Mhm, thanks. I hope to find a way to determine the exact solutions for each n (or a number of them, there are obviously infinitely many). Do you think it might make sense to represent this as a tree or something similar? One can always switch positions of squares, two at a times. If this is repeated, this seems to lead to a tree-like structure where 'branches' always split into two 'sub-branches'. Just some intuition. -- Toshio Yamaguchi 15:33, 1 May 2014 (UTC)

I've written a program in Mathematica that finds these configurations.

For 3x3 There are 23 configurations, I think the one you're missing is a plus sign.

For 4x4 there are 1674 configurations. Putting these numbers in OEIS gives http://oeis.org/A082963. Apparently there's no known simple formula, but values are known up to 11x11. -- Meni Rosenfeld (talk) 16:39, 1 May 2014 (UTC)

Well done Meni! Summary: S₀=1, S₁=1, S₂=2, S₃=23, S₄=1674. For n>4 the formula $S_{n}\approx {\tbinom {n^{2}}{k}}/8$ is an excellent approximation. Symmetric configurations are rare, so the 8 rotated or reflected pictures are almost certainly different. Bo Jacoby (talk) 21:55, 1 May 2014 (UTC).

PS Actually, it should be possible to find a fairly simple formula using Burnside's lemma. It will require a summation that might be reducible to a simpler form. I'll try working it out later. -- Meni Rosenfeld (talk) 08:59, 2 May 2014 (UTC)

One more thing... I didn't give much thought about the additional stipulation that the patterns should also be incongruent under color inversion, because for the given odd example it doesn't matter. My results above are correct if it is disregarded.

However, for even n it does matter. And the result I get with this added is 887 for $n=4$. I can't seem to find that sequence in OEIS, but the derivation should be similar. -- Meni Rosenfeld (talk) 15:05, 2 May 2014 (UTC)

I think it's easier to solve using the Pólya enumeration theorem (this is a more powerful method than Burnside's lemma). You just allow arbitrary numbers of white squares and give them a weight of x. The theorem gives you the generating function taking into account the symmetry, and you then extract coefficient of the power of x^(n^2/2) from the polynomial. Count Iblis (talk) 01:59, 4 May 2014 (UTC)

Example for n = 3.

1) Identity. All the squares stay where they are, so we get 9 orbits of lenght one. Contribution to the cycle index polynomial is T1^9.

2) 90 degree rotation: Two orbits of length four and one of length 1. The four squares at the corners of the grid from one orbit, and the four suqares inbetween them also form one orbit. The square in the middle stays where it is, so this is an orbit of length one. Contribution to cycle index polynomial is thus T1 T4^2.

3) 180 degree rotation: Four orbits of length 2 and one of length 1. Contribution to cycle index polynomial is T1 T2^4 .

4) Reflection through line through the middle squares: 3 orbits of length 2 and 3 of length 1, so we get a contribution of T1^3 T2^3.

5) Reflection through the diagonal line: 3 orbits of length 2 and 3 of length 1, so we get a contribution of T1^3 T2^3.

We have two rotations over 90 degrees, and for the two types of reflections there are two different ones. The cycle index polynomial is thus given by:

Z = 1/8 [T1^9 + 2 T1 T4^2 + T1 T2^4 + 4 T1^3 T2^3]

Then Polya's theorem says that to obtain the generating function we must substitute:

Ti = 1 + x^i

This gives:

1/8 [(1+x)^9 + 2 (1+x)(1+x^4)^2 + (1+x)(1+x^2)^4 + 4 (1+x)^3 (1+x^2)^3]

Coefficient of x^4 is:

1/8 [Binomial(9,4) + 2*2 + Binomial(4,2) + 4*Binomial(3,2) + 4*Binomial(3,2)*Binomial(3,1)] =

1/8 [126 + 4 + 6 + 12 + 36] = 23

What about general n? It's easy to see that this is just a product of cycle index polynomials of the group acting on just the boundaries of the squares up to and including size n (with step size 2) when you omit the prefactor of 1/(number of elements in the group) = 1/8. Count Iblis (talk) 02:41, 4 May 2014 (UTC)

Stupid mistake here, you obviously need to multiply the terms from each element of the group only. I'm going to correct what was written below this line. Count Iblis (talk) 13:41, 4 May 2014 (UTC)

So, for odd n we have:

$Z_{n}={\frac {1}{8}}\left[T_{1}^{n^{2}}+2T_{1}T_{4}^{\frac {n^{2}-1}{4}}+T_{1}T_{2}^{n^{2}-1}+4T_{1}^{n}T_{2}^{\frac {\left(n-1\right)\left(2n-1\right)}{2}}\right]$

Count Iblis (talk) 13:55, 4 May 2014 (UTC)

The generating function then becomes:

${\frac {1}{8}}\left[(1+x)^{n^{2}}+2(1+x)\left(1+x^{4}\right)^{\frac {n^{2}-1}{4}}+(1+x)\left(1+x^{2}\right)^{n^{2}-1}+4(1+x)^{n}\left(1+x^{2}\right)^{\frac {\left(n-1\right)\left(2n-1\right)}{2}}\right]$

Count Iblis (talk) 14:03, 4 May 2014 (UTC)

Elementary counting for n=8, the 8x8 chessboard.

The number of fields on a chessboard is 64 and the number of black fields is 32. The total number of configurations is ${\tbinom {64}{32}}$ = 1832624140942590534.

The number of configurations which are mirror symmetric about the horizontal line (called [-]), is ${\tbinom {32}{16}}$ = 601080390. This is the number of configurations on the lower half of the board.

The number of configurations which are mirror symmetric about the vertical line [|] is also 601080390.

The number of configurations which are symmetric with respect to 180 degree rotation is also 601080390.

The number of configurations which are mirror symmetric about both [-] and [|], that is [+], is ${\tbinom {16}{8}}$ = 12870.

The number of configurations which are symmetric with respect to 90 degree rotations is also 12870.

The number of configurations which are symmetric with respect to 180 degree rotation, but not 90 degree rotations, is 601080390 - 12870 = 601067520.

The number of configurations which are mirror symmetric about [-] but not [+] is also 601067520.

The number of configurations which are mirror symmetric about [|] but not [+] is also 601067520.

The number of configurations which are mirror symmetric about the rising diagonal [/] is $\sum _{i=0}^{4}{\tbinom {8}{2i}}{\tbinom {28}{16-i}}$ = 4965766470. (Note that 8+2⋅28=64 and 2i+2(16-i)=32).

The number of configurations which are mirror symmetric around the falling diagonal, [\] is also 4965766470.

The number of configurations which are mirror symmetric about boths diagonals [X] is $\sum _{i=0}^{4}{\tbinom {8}{2i}}{\tbinom {12}{8-i}}$ = 110022.

The number of configurations which are mirror symmetric about [/] but not [X], is 4965766470 − 110022 = 4965656448.

The number of configurations which are mirror symmetric about [\] but not [X], is also 4965656448.

The number of configurations which have 2-fold symmetry but no higher symmetry is 601067520 + 601067520 + 601067520 + 4965656448 + 4965656448 = 11734515456

The number of 8-fold symmetric configurations is $\sum _{i=0}^{2}{\tbinom {4}{2i}}{\tbinom {6}{4-i}}$ = 150.

The number of configurations which are mirror symmetric about [+] but not [X] is 12870-150 = 12720.

The number of configurations which are symmetric with respect to 90 degree rotations but not [X] nor [+] is also 12720.

The number of configurations which are mirror symmetric about [X] but not [+] is 11612-150 = 11462.

The number of configurations which have 4-fold symmetry but no higher symmetry is 12720+12720+11462 = 36902.

The number of unsymmetrical configurations is 1832624140942590534 - (11734515456 + 36902 + 150) = 1832624129208037888

So the number of configurations modulo symmetry is 1832624129208037888/8 + 11734515456/4 + 36902/2 + 150 = 229078019084652192.

The Sloan value is 229078019084673798.

My error = 21600. (To be continued). Bo Jacoby (talk) 06:21, 4 May 2014 (UTC). 16:01, 4 May 2014 (UTC). 22:32, 4 May 2014 (UTC). Bo Jacoby (talk) 23:15, 7 May 2014 (UTC).

FPE in curved space

If I have an Fokker-Planck Equation for diffusion on a curved manifold I feel like the metric tensor should be appearing somewhere, but I'm not sure where. Is this correct?

I would like some input to the following work on Trisecting an arbitrary angle

Trisecting an arbitrary angle is one of 3 classic problems that the Greek mathemations were never able to solve. As of this date it is considered impossible to trisect an angle using only a compass and unmarked straight edge. Thus this is an unsolved problem for about the past 2000 + years. Any method that claims to effectively trisect an angle must have some foundation in math in order to be considered. It is of course impossible to trisect an arbitrary angle α using only a compass and unmarked straight to an exact degree of accuracy. It is however possible to divide any angle α into n equal segments using a compass and unmarked straight edge to an acceptable desired degree of accuracy with the following procedure. It is essentially a modeling issue, where you need to approximate the length of the arc at radius r. In order to determine the accuracy of the division of an arbitrary angle into n equal segments we need to be able to define what the divided angle would be. Trisecting an angle is part of the larger issue of dividing an angle into n equal angles. This can be Accomplished through the following method: To address this problem consider these preliminary points.

1) π is defined as the ratio of the circumference of a circle divided by the diameter of the circle. Thus c= π . D. Or c = 2 . π . r

2) For a given circle of radius r the circumference is 2π.r and there exists a circle of radius 3r such that the circumference is2π.3.r. The circumference of the circle 3r is 3 times the radius of circle r. Also, any Segment of angle α of the two circles are like wise of the ratio 3:1. (See Figure 1 in Appendix) i.e. a segment of 1/360 would give a circumference of (2.π . r)/360 or (π. r)/180 and for radius 3r, (π. 3r)/180 giving the same ratio of 3:1 and for the general case a ratio of n :1 This relationship holds for any n. See Figure 2 in Appendix

4) The difficulty in taking advantage of this relationship is that the two circles have different curvatures, so it isn’t directly helpful to use this relationship directly. See Figure 3 in Appendix.

5) The following relationship is true for all r and for all α greater than 0 and less than or equal to 360 degrees.

R is all real numbers

N is natural numbers

Let α belong to R greater than 0

Let r belong to R greater than 0

Let ℓ = length of the chord, belonging to R greater than 0

And let n belong to N greater than 1

For r, ℓ1 = 2 sin (α/2).r

For 3r, ℓ3 = 2 sin ((1/3)α/2).3r

Or ℓ3 = 6 sin (α/6).r

For the general case n,

ℓ (n) =2 . n sin ((α/2n) . r Note that the above value for ℓ(n) = 2 . n Sin(α/2n) . r defines the n- section of α for all n. (See Figure 4 in appendix)

6) The next issue is; at what angle α is the ratio of (2.sin (α/2).r) /(6.sin(α/6).r), within the range of error of a compass and unmarked straight edge?

7) The following table addresses this issue. For reference, common lead diameters are as listed below:

.9 mm = .0354″
.7 mm = .0276″
.5 mm = .0197″

α   2sin(α/2)      6sin(α/6)       ratio       error @10 inch

30  .51763809	   .52293416	   .989872     .101
24  .41582338	   .4185389	   .993512     .065
20  .34729636	   .34886894	   .995492     .045
15  .26105638	   .26171632	   .99746313   .025
10  .174314855	   .1745083055	   .9989       .011
6   .1046719125	   .1047144386	   .99959      .0041
5   .087238775	   .0872263351	   .99972      .00284
4   .06979899	   .06980461396	   .9998205    .0018
3   .0523538966	   .052359213	   .9998985    .0013
2   .0349048128	   .034906353	   .99996      .00008
1   .0174530709967 .017453198093   .999993     .00007

The error in degrees is:

30 °	.304
24°	.156
20°	.090
15°	.038
10°	.0111
6°	.0025
5°	.0014
4°	.0007
3°	.0003
2 °	 .00008
1°	.000007

1 minute = .01666667°, 1 second = .000277777°

8) The line segment ℓ can be considered as the face of a polygon of n sides. As the number of sides (n) increases the polygon approaches the form of a circle as n approaches infinity. See Figures 5 to 9 in Appendix.

9) To take advantage of the accuracy of small angles, angles can be bisected to better approximate the circle. Each time you bisect the angle you double the number of segments to divide the angle.

10) To divide the angle α into any other number of segments the same process is followed: i.e. for dividing into 5 equal segments:

ℓ=2 sin (α/2)r

5ℓ= 5(2 sin (α / (5x2))r

Ratio is (2 sin (α/2) r) / (10 sin (α/10) r)

Havent been able to enter the figures from the appendix yet but they are very simple Smithcgrover (talk) 18:29, 1 May 2014 (UTC)

(Fixed some formatting in an attempt to make the above slightly more readable.) I'm not at all clear what you're asking here. As you say, arbitrary angle trisection by straight edge and compass is not possible in Euclidean geometry. It is not an "unsolved problem". There are various methods by which one can do an approximate trisection, or an exact one if the "straight edge and compass" rules are slightly relaxed, but these are of no great practical interest. AndrewWTaylor (talk) 19:55, 1 May 2014 (UTC)

Because compass-and-straightedge constructions are of practical interest? --Trovatore (talk) 20:09, 1 May 2014 (UTC)

You may mock, but in my first (proper) job I impressed a senior person by knowing the compass-and-straightedge construction of a regular pentagon, which he went on to use (for the company logo) in preparing a presentation (which in those days was often done by hand on sheets of flip-chart paper). Rather an over-engineered solution, I grant you. AndrewWTaylor (talk) 20:22, 1 May 2014 (UTC)

I think what the questioner is asking is not about a general method for perfectly trisecting any angle, but about a method that will provide an approximate trisection that will be indistinguishable from an exact one because of real-world considerations such as the precision of his available drawing implements. This is why he talks about "common lead diameters" - he's using a pencil, and wants to get close enough to perfect trisection that the error is less than the width of his pencil lines. The general answer to this question is that there certainly exist purely compass-and-straightedge constructions that will get you to within any specified level of accuracy of perfect trisection in a finite (though possibly very large) number of steps. With regard to the specific method proposed here, I think I can see what the questioner is getting at, but I haven't followed his reasoning through step by step. RomanSpa (talk) 19:19, 2 May 2014 (UTC)

bi-Taylor?

Is there a construction, analogous to Taylor series, to build up approximations to a function using derivatives given at two points? Obviously for a given number of derivatives one can find a polynomial, but I'm curious about methods that do not require choosing the degree in advance. —Tamfang (talk) 22:09, 1 May 2014 (UTC)

Sounds a bit like a spline_(mathematics). Cubic spline, Cubic Hermite spline, and a I think bicubic spline is a term used in some literature. SemanticMantis (talk) 03:27, 2 May 2014 (UTC)

Obviously for a given number of derivatives one can find a polynomial, but I'm curious about methods that do not require choosing the degree in advance. —Tamfang (talk) 07:21, 2 May 2014 (UTC)

I'm confused by what you're asking. To clarify: you want an approximation scheme that works on general (continuously) differentiable functions f. It should take as input two points {x1, x2}. It should return an approximating function g, that uses derivatives of f at x1, x2, and also some n, k, that are the highest degrees of differentiation? E.g. such a scheme would produce {ai, bj}, {n,k}, such that $g=\sum _{0}^{n}a_{i}f^{(i)}(x-x_{1})+\sum _{0}^{k}b_{j}f^{(j)}(x-x_{2})$, for x in (x1,x2)?

If that's what you mean, then at the least you'll have to specify a tolerance of some sort in advance, e.g. |f-g|(x)<\epsilon, for all x in (x1, x2). Otherwise no algorithm can know in advance how close of an approximation is good enough for your purposes. Well, I suppose you could have the algorithm make a choice based on certain properties of f in the domain, but that's still a choice, you're just pushing it into the algorithm. SemanticMantis (talk) 13:29, 2 May 2014 (UTC)

The function g is unlikely to be linear in x as you have it ... —Tamfang (talk) 08:58, 3 May 2014 (UTC)

You can create a polynomial interpolating any number of given derivatives at a pair of points. The interpolating polynomial should approximate the given function. It might not be easy to come up with useful error estimates like you have in Taylor's theorem. Sławomir Biały (talk) 13:46, 2 May 2014 (UTC)

Yes, obviously you can construct a polynomial of degree $2k+1$ that matches $f(x_{0})$ and $f(x_{1})$ and the first k derivatives; but if you then decide that k needs to increase, you have to start over, either with a new series of Hermite-like basis functions or with a new family of simultaneous linear equations — whereas with Taylor series you'd add another term without having to recompute anything else. This incremental quality is what I'm asking about. —Tamfang (talk) 08:58, 3 May 2014 (UTC)

It might be pretty horrible otherwise, but that property would be had by a linear inter/extrapolation between two Taylor series: $f(x)=(1-\xi )f_{1}(x-x_{1})+\xi f_{2}(x-x_{2})$ where $\xi ={\frac {x-x_{1}}{x_{2}-x_{1}}},f_{i}(t)=\sum _{j=0}^{n_{i}}{\frac {t^{j}}{j!}}\left.{\frac {d^{j}f}{dx^{j}}}\right|_{x=x_{i}}$. --Tardis (talk) 17:26, 3 May 2014 (UTC)

I haven't done the algebra, but I wouldn't expect the derivatives to match. —Tamfang (talk) 07:17, 4 May 2014 (UTC)

Oh, sorry; you're right of course. You could use a high-order interpolating function in $\xi$ with enough zero derivatives at $x_{i}$ to overcome that, but the simplicity (and the "natural" quality) would then suffer. Hm. --Tardis (talk) 04:14, 5 May 2014 (UTC)

Note that for rational functions it does work this way. The partial fraction expansion is the sum of the principal parts of the Laurent expansions around each pole (including the pole at infinity if the degree of the numerator is equal or larger than that of the numerator). So, perhaps it can be made to work if you recast the problems into one involving expanding in negative powers. Count Iblis (talk) 13:40, 5 May 2014 (UTC)

This is how you can do it. Suppose we want to expand f(x) at x1, x2, x3,...,xn at orders s1, s2,...,sk respectively such that you can always increase the order at some xk without having to modify the previously computed terms. You can do that by using the functions Q(x;y1,y2,y3,...) = exp[- sum over r 1/(x-yr)^2] which is zero and all its derivatives are zero at the yr that are summed over. You write f(x) as:

f(x) = Q(x;x2,x3,x4,...xn) p1(x-x1) + Q(x;x1,x3,x4,...xn) p2(x-x2) + ....Q(x;x1,x2,x3,x4...xn-1) pn(x-xn)

To compute pr one only needs to expand f(x)/Q(x;x1,x2,...xr-1, xr+1,...xn) to the desired order order. Count Iblis (talk) 21:42, 5 May 2014 (UTC)