Mathematics desk
< September 23	<< Aug \| September \| Oct >>	September 25 >

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.

September 24

Number of rows with at least one unique element

I'm looking for a way to calculate the number of rows with n elements, of which each element is chosen from the range 1..r, and in which there is at least one unique element. Order matters. So, if n = 3, and r = 2, we would have 2³= 8 rows, of which 211, 121, 112, 122, 212, 221 all have a unique element, only 111 and 222 do not have a unique element.

I tried to find a more or less direct formula, thinking along the lines: "if we stipulate the first element should be unique, we have r choices for this element, which leaves (r-1)^n-1 choices for the other elements, i.e. r*(r-1)^n-1 in total." But, this leaves out some of the rows in which the second element is the only unique element. But, on the other hand, it does include some of the rows in which the second element is a unique element too. For example, if n = 3, and r = 3, we would have 123 in which every element is a unique element -- I don't want to count those rows twice. (For n = 3, r = 3, there are 27 rows in total, 24 of which have at least one unique element, only 111, 222 and 333 do not have a unique element).

I can't come up with an exact formula, nor can I find a recursive equation. --Berteun 08:14, 24 September 2007 (UTC)[reply]

The basic problem that you're describing (if I'm reading you right) is how many distinct ways there are to choose n elements from a set R {1, ..., r} with repetitions, without counting the options that choose the same elements n times. According to the article on the binomial coefficient the first part is described by C(r+n-1, n), and the second part is just r, meaning the formula comes out as C(r+n-1, n) - r.

Of course, as I'm typing this I realise that you mean that a sequence like '3311' needs to be discounted as well, since it doesn't have any unique elements. I'll keep thinking on that one, but maybe this will be of some help.

risk 16:01, 24 September 2007 (UTC)[reply]

So your question is how many words there exist of length n with an alphabet of r letters where one of the letters appears exactly once. One way to get to the solution is: 1. Choose the letter that must appear once. 2. Choose the position for this letter. 3. Insert the letter in a word of length n-1 (where only the remaining r-1 letters may be used). Aenar 16:20, 24 September 2007 (UTC)[reply]

Problem with that is, though every word you create will have a unique letter, some words (such as 12, for instance) will be double-counted, as it contains 2 unique elements. Gscshoyru 16:21, 24 September 2007 (UTC)[reply]

Yeah, right, sorry. Aenar 16:25, 24 September 2007 (UTC)[reply]

I've calculated this for small numbers, and got this table.

         n= 0      1      2      3      4      5      6      7
                                                              
   r=0      0      0      0      0      0      0      0      0
     1      0      1      2      3      4      5      6      7
     2      0      0      2      6     12     20     30     42
     3      0      0      6     24     60    120    210    336
     4      0      0      8     60    216    560   1200   2268
     5      0      0     10    180    900   2920   7470  16380
     6      0      0     12    486   3432  14220  44100 113442
     7      0      0     14   1218  13188  70700 265650 799134

It's apparently not in Sloane's. – b_jonas 16:52, 24 September 2007 (UTC)[reply]

I would switch n and r, but the results are along the lines I got too. I mean, if the number of objects n = 1, there are exactly r solutions, whereas if r = 1, there is no solution except if n = 1. At least I'm relieved someone didn't find a solution rather easily, and the fact it's not the Sloane's surprises me. --Berteun 18:37, 24 September 2007 (UTC)[reply]

I did some manual calculations, and I found that for n > 3 and r = 2 the outcome is always 8. I may be wrong though, I'll check. risk 17:00, 24 September 2007 (UTC)[reply]

And wrong I was. I get the exact same table. risk 17:43, 24 September 2007 (UTC)[reply]

Sorry, it is in sloane, you just have to search for the complement: A131103 it is. – b_jonas 19:03, 24 September 2007 (UTC)[reply]

(See also the same in square array format). – b_jonas 19:05, 24 September 2007 (UTC)[reply]

Thank you! And also the other people who have thought about it! --Berteun 19:24, 24 September 2007 (UTC)[reply]

I think it might be possible to write a recurrence for this one. Let a(n,r) is the number of n long words from r letters that don't have any letter exactly once. Then you can write a(n,r) from a(n,r-1); a(n-2,r-1), a(n-3,r-1), ..., a(1,r-1), a(0,r-1); because you get all the words by inserting 0, 2, 3, ..., n-1, or n copies of the r-th letter somewhere in words that only have the first r-1 letters. I haven't actually written this formula nor verified it, so I could be wrong. – b_jonas 21:15, 24 September 2007 (UTC)[reply]

I looked at Sloane's. The sequence you gave was linked to the associated Stirling numbers of the second kind. The 'normal' Stirling numbers of the second kind give the number of ways to partition a set of n values into exactly k subsets. The associated ones give the number of ways to partition a set of n values into exactly k subsets where every subset has at least two elements. A direct expression for this is provided at Sloane's (A008299). This is easily combined with the formula given at A131103. The associated numbers can be thought of as putting n labelled objects into k unlabelled boxes. For this problem we would like to put them in labelled boxes. The idea is to calculate the number of each j = 1..k (where k cannot be greater than floor(n/2) of course), multiply this by k! (because the boxes are labelled) and then divide by (k - j)! because switching empty boxes does not give a new solution. (At least, that's how I read the formula). The rows of letters from an alphabet can be seen as putting each element of the row into a box which represents a letter of the alphabet. This way the number of sequences with only non-unique elements is obtained. --Berteun 08:21, 25 September 2007 (UTC)[reply]

Looking for job to support my study at Rostock University

→ —Preceding unsigned comment added by 82.116.148.238 (talk) 08:57, 24 September 2007 (UTC)[reply]

Try local newspapers and employment agencies. Also, the university may have a college work-study or coop program you could look into. StuRat 16:47, 24 September 2007 (UTC)[reply]

Do you have a work permit? Without one, it may be difficult to find a job, unless you have some really scarce talent. Anyway, this doesn't seem to be a mathematical topic. --Lambiam 18:25, 24 September 2007 (UTC)[reply]

Contour lines for 3 fixed points

This all applies to a plane. For 2 fixed points, the contours of equal total distance from them are concentric ellipses with the fixed points as foci. What happens for 3 fixed points? To remove any obvious symmetry, take the triangle to be scalene, but it can be acute or obtuse. As the distance away gets larger, the contours will tend towards circles centred on a point somewhere within the triangle, but what is the pattern for smaller distances?→81.159.11.163 20:36, 24 September 2007 (UTC)[reply]

Very curious, its not a problem I've seen addressed before. I'm not sure if there is an easy answer to this, experiments suggest some you get close curves, which might not always be smooth. There will be a critical value of the distance where the curve forms a single point, and I think this will be a point on the Voronoi diagram of the three point.--Salix alba (talk) 21:48, 24 September 2007 (UTC)[reply]

Re. the curve forming a single point, this will be the Fermat point of the triangle, where the total distance to the vertices is least. So the contours will be non-overlapping closed curves containing this point. To take a simpler case to begin with, if the triangle is equilateral, there must be a corresponding symmetry in the curves - surely not circles, but like "bulgy" equilateral triangles?→81.159.11.163 22:02, 24 September 2007 (UTC)[reply]

Ah yes, looks like the same thing.

Some questions arise. Is it always convex? is it always smooth? Brief experiments (see image) suggest yes to the first and possibly no to the second. In which case you will get quite an interesting singularity arising. It might be interesting to find where the vertices of the curve are. --Salix alba (talk) 22:27, 24 September 2007 (UTC)[reply]

The sum of distances to three or more points is a sum of convex functions, and therefore itself convex, so it has convex level sets. The distance to a single point is a smooth function except at that point, so the sum of distances is smooth except at the given points, and has smooth level sets except when the level set passes through one of the given points. See also geometric median for more than three points. —David Eppstein 17:57, 25 September 2007 (UTC)[reply]

Thanks for that. It looks like the distance function has simple A1 singularities (cones) at the given points and the contours are just what you expect from slicing through the cones (locally at least). Mystery solved. --Salix alba (talk) 20:35, 25 September 2007 (UTC)[reply]

conversion of centimeters to inches

Please tell me how do I convert centimeters to inches. All I need are the basics, then I can complete my homework. Thank you Samuelalexander 20:50, 24 September 2007 (UTC)[reply]

1 inch is exactly equal to 2.54 cm. To convert from inches to centimetres, you simply multiply by the conversion factor (2.54). The other way round is just division by the conversion factor. Richard B 20:55, 24 September 2007 (UTC)[reply]

Conversion of units—Cronholm¹⁴⁴ 23:51, 24 September 2007 (UTC)[reply]