Wikipedia:Reference desk/Archives/Mathematics/2016 July 17

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.

July 17

How many 4-color-combinations are possible if I have a total of 8 colors?

I have 8 colors. How many 4-color combinations are possible? It is OK to re-use colors. Bus stop (talk) 01:48, 17 July 2016 (UTC)

See Multiset#Counting_multisets. --JBL (talk) 02:30, 17 July 2016 (UTC)

I can't understand that (Multiset#Counting_multisets), but is the answer 20? I do thank you for providing the link. Bus stop (talk) 03:04, 17 July 2016 (UTC)

The formula in the articles gives ${\frac {(8+4-1)!}{4!(8-1)!}}={\frac {11!}{4!7!}}={\frac {11\cdot 10\cdot 9\cdot 8}{24}}=330$.--Jasper Deng (talk) 04:48, 17 July 2016 (UTC)

The order doesn't matter. How many different groupings of four can be found out of a total of eight values? Bus stop (talk) 05:01, 17 July 2016 (UTC)

@Bus stop: Please read the article. A multiset does not care about the order of the appearance of its elements: {blue, blue, yellow, red} is the same multiset as {blue, yellow, blue, red}.--Jasper Deng (talk) 05:04, 17 July 2016 (UTC)

OK, I forgot to mention—no color can be use more than once in a 4-color group. Sorry—I was not clear. Bus stop (talk) 05:10, 17 July 2016 (UTC)

@Bus stop: Then you should not be saying "It is OK to re-use colors". Instead you would use a binomial coefficient and obtain ${\frac {8!}{4!4!}}={\frac {8\cdot 7\cdot 6\cdot 5}{24}}=70$.--Jasper Deng (talk) 05:22, 17 July 2016 (UTC)

Is there any way I could get a list of those 70 four-digit numbers? Is there some program that would spit out those 70 four-digit numbers? Could it arrange the numbers in numerical order? I believe the lowest number would be 1,234 and the highest number would be 5,678. I am specifying that the digits in the four-digit numbers should be numerically arranged from lowest to the left and highest to the right, and that the four-digit numbers should be arranged from lowest to the left and highest to the right. As an example, the beginning of the sequence would look like this: 1234, 1235, 1236, 1237, 1238, 1245, 1246, 1247, 1248, 1256, 1257, 1258, 1267, 1268, 1278, 1345, 1346, 1347, 1348, 1356, 1357, 1358, 1367, 1368, 1378, 1456, 1457, 1458, 1467, 1468, 1478, 1567, 1568, 1578, 1678. Bus stop (talk) 13:28, 17 July 2016 (UTC)

The relevant section would be Combination#Enumerating k-combinations I think —  crh ₂₃  (Talk) 14:39, 17 July 2016 (UTC)

I don't get 70 as the answer. I get 66. Here are my results:

1234, 1235, 1236, 1237, 1238, 1245, 1246, 1247, 1248, 1256,
1257, 1258, 1267, 1268, 1278, 1345, 1346, 1347, 1348, 1356,
1357, 1358, 1367, 1368, 1378, 1456, 1457, 1458, 1467, 1468,
1478, 1567, 1568, 1578, 1678, 2345, 2346, 2347, 2348, 2356,
2357, 2358, 2367, 2368, 2378, 2456, 2457, 2458, 2467, 2468,
2478, 2567, 2568, 2678, 3456, 3457, 3458, 3567, 3568, 3578,
3678, 4567, 4568, 4578, 4678, 5678.

To make it easier to count, there are ten per line, except for the last line, which contains six. Bus stop (talk) 17:09, 17 July 2016 (UTC)

You missed 2578, 3467, 3468, and 3478. -- BenRG (talk) 17:27, 17 July 2016 (UTC)

(I found that with the Python code {int(''.join(x)) for x in itertools.combinations('12345678', 4)} - {your list of numbers}. If you just want Python to produce all 70 combinations, leave out the - {...} part.) -- BenRG (talk) 17:36, 17 July 2016 (UTC)

(edit conflict)Don't forget 3467, 3468, 3478. I'm still looking. This is combinations, which football and racing punters call "permutations". They use a simple rule to work out their stake. You evaluate [x] x [x-1] x [x-2] ... where [x] is the total number of colours and the number of terms in the series equals the number of colours selected, and divide by 1 x 2 x 3 ... where again the number of terms in the series equals the number of colours selected. So if out of six teams you think are equally matched you wanted to pick any three teams to draw your outlay would be (6 x 5 x 4)/(1 x 2 x 3) = 20 bets. When you mark your x's and hand your coupon in to the agent the pools company runs it through their computer. It checks full perms and plans (e.g. if you can't afford to cover all 20 possibilities you might do a plan, which might guarantee a win if 4 of the teams draw). So all those sequences are stored in the computer and can be printed out on request. The football pools have been eclipsed by the National Lottery - I don't know if they offer this facility. 82.18.244.238 (talk) 17:56, 17 July 2016 (UTC)

I find this explanation to be a poor one - none of the OP's original question had anything to do with football bets. Also, a combination should not be confused with a permutation.--Jasper Deng (talk) 18:39, 17 July 2016 (UTC)

Wow, you are all right. Here's the full list:

1234, 1235, 1236, 1237, 1238, 1245, 1246, 1247, 1248, 1256,
1257, 1258, 1267, 1268, 1278, 1345, 1346, 1347, 1348, 1356,
1357, 1358, 1367, 1368, 1378, 1456, 1457, 1458, 1467, 1468,
1478, 1567, 1568, 1578, 1678, 2345, 2346, 2347, 2348, 2356,
2357, 2358, 2367, 2368, 2378, 2456, 2457, 2458, 2467, 2468,
2478, 2567, 2568, 2578, 2678, 3456, 3457, 3458, 3467, 3468,
3478, 3567, 3568, 3578, 3678, 4567, 4568, 4578, 4678, 5678.

Here is my next problem. I want to pick eight out of the above 70 numbers. The other 62 I don't care about. These are 4-digit numbers, so multiplying eight by four I know that I am dealing with thirty-two digits. I want equal representation for the digits one through eight. Therefore I want "1" to occur 8 times; I want "2" to occur 8 times; I want "3" to occur 8 times; I want "4" to occur 8 times; I want "5" to occur 8 times; I want "6" to occur 8 times; I want "7" to occur 8 times; and I want "8" to occur 8 times. How can I pick eight out of the above 70 numbers such that each individual digit has equal representation in my entire group? (Each digit represents a distinct color.) Bus stop (talk) 18:53, 17 July 2016 (UTC)

For instance, 1234 represents a color combination. And 5678 represents a color combination. If I only needed two such color combinations, those two would fit the bill. That is because the individual digits have equal representation. But I need a total of eight such "color combinations". Bus stop (talk) 19:10, 17 July 2016 (UTC)

It's not possible to have all eight digits occur exactly once each, since that would require 8 times 8 or 64 digits when we only have 32. Instead you probably should settle for each color occurring four times, which is 32/8. If we do that, then we can obtain 1234, 5678, 1357, 2468, 1457, 2368, 1578, 2346. I'm not sure this solution is unique.--Jasper Deng (talk) 19:28, 17 July 2016 (UTC)

Yes, each color can occur 4 times. That would be great. Did you just peruse the 70 possibilities to find those 8 color combinations? That answers my question entirely. Thank you for the help. Bus stop (talk) 19:47, 17 July 2016 (UTC)

It's easy to choose three orthogonal dichotomies by considering the binary representation. (This means using 01234567; you can add 1 to each number, or replace 0 with 8, to taste.) The low bit separates 0246 from 1357; the middle bit separates 0145 from 2367; the high bit separates 0123 from 4567. For a fourth dichotomy, we can look at whether the number of 1 bits is even or odd: thus 0356 and 1247. Each digit occurs once in each of these pairs of tetrads, so four times in all.

Another way to go is cyclic: 0123, 1234, 2345, 3456, 4567, 5670, 6701, 7012. Maybe all such sets are equivalent under substitution? —Tamfang (talk) 22:06, 17 July 2016 (UTC)

No, in the first series – 0123, 0145, 0246, 0356, 1247, 1357, 2367, 4567 – each subset shares zero or two digits with each other subset, but in the cyclic series they share zero, one, two or three. —Tamfang (talk) 06:36, 20 July 2016 (UTC)

The "cyclic" solution seems like a good idea, in my opinion, but why avoid using the digit "8", as in 1234, 2345, 3456, 4567, 5678, 6781, 7812, 8123? Bus stop (talk) 02:57, 18 July 2016 (UTC)

@Bus stop: Because computer scientists like to count from 0.--Jasper Deng (talk) 06:52, 18 July 2016 (UTC)

Thanks. Thanks to everyone for all your help. Bus stop (talk) 18:24, 18 July 2016 (UTC)

Because (for my first paragraph) I was using properties of the binary representation: {000, 001, 010, 011, 100, 101, 110, 111}. These are all the possible values of three bits. If I instead used {001, 010, 011, 100, 101, 110, 111, 1000}, the fourth split wouldn't work. —Tamfang (talk) 06:29, 20 July 2016 (UTC)

So would computer scientists regard the first ten numbers as 0 - 9, whereas everyone else regards them as 1 - 10? 92.8.220.116 (talk) 17:33, 18 July 2016 (UTC)

It can be useful for certain things, and useful in some parts of mathematics as well.Naraht (talk) 18:38, 18 July 2016 (UTC)

In particular, A mod B can be zero but not B. —Tamfang (talk) 08:03, 21 July 2016 (UTC)

To generate a list of the combinations if you don't have Python's itertools library:

• Let N be the lowest forbidden number, in your case 9
• Let K be the size of the string sought, in your case 4
• Initialize MYLIST with the first combination, in your case [1,2,3,4]
• print MYLIST
• J = K-1
• while J ≥ 0:
  • If MYLIST[J] < N-K+J:
    • MYLIST[J] = 1+MYLIST[J]
    • For JJ in J+1 through K-1:
      • MYLIST[JJ] = 1+MYLIST[JJ-1]
    • print MYLIST
    • J = K-1
  • else:
    • J = J-1

There's probably an obvious bug here, but the essential step is: increment the rightmost element that you can increment, and set the elements to its right to the lowest values they can now have. —Tamfang (talk) 22:03, 17 July 2016 (UTC)

Squaring a matrix

I went to one of the external links of the matrix multiplication article and it says that to square a 2x2 matrix whose terms are n, you get a 2x2 matrix whose terms are all 2n^2. Is there any similar rule you can use to square any palindromic matrix"?? That is, a 3x3 matrix qualifies if its elements are (where identical letters must be replaced by the same number):

A B A
B C B
A B A

For a 4x4 matrix to be palindromic, it must have the elements:

A B B A
B C C B
B C C B
A B B A

For a 5x5 matrix, the elements must be:

A B C B A
B D E D B
C E F E C
B D E D B
A B C B A

And so on. Is there any general rule you can use to square any nxn palindromic matrix?? Georgia guy (talk) 18:43, 17 July 2016 (UTC)

First, could you be more specific about the link you mentioned? There are number of links at the end of the article. Second, I think the phenomenon you're talking isn't so much to do with matrix squaring as with matrix multiplication in general, and not so much to do with palindromic matrices as with matrices with patterns of repeated rows and columns. To generalize your 2x2 example a bit, given a 2x2 matrix A consisting of all a's, and a 2x2 matrix B consisting of all b's, then the product is the 2x2 matrix with 2ab as every entry. More generally, start with a pattern of repetitions, say 1=4=5, 2=6 for 6x6 matrices. Consider the set of matrices which follow this pattern in both rows and columns. In this case it would be matrices of the form:

A B C A A B
D E F D D E
G H I G G H
A B C A A B
A B C A A B
D E F D D E

This forms a sub-algebra (in fact it's an ideal) of the set of all 6x6 matrices. If there are k distinct rows or columns allowed by the pattern, then this subring is isomorphic to the ring of kxk matrices. In the example the isomorphism is given by

A B C A A B
D E F D D E
G H I G G H    3A  √6B  √3C
A B C A A B  → √6D 2E   √2F
A B C A A B    √3G √2H  I
D E F D D E

and the general rule follows the same pattern. In other words we can get the product of two 6x6 matrices following the pattern by multiplying two 3x3 matrices. Going back to the original 2x2 matrices following the pattern 1=2, we can get their product just by multiplying numbers. This is assuming we're working over the reals; if the matrices are over a different field it appears things get more interesting.

Slightly more generally, you could consider matrices that follow one repetition pattern for rows and a different pattern for columns. For example matrices of the form

A A B
C C D
A A B

Again these form a sub-algebra but it's not as clear what its structure is. --RDBury (talk) 05:59, 18 July 2016 (UTC)