0
$\begingroup$

Recently, I thought of the following question relating to "ordering colored balls according to some choice of constraints".

Suppose there are 5 balls:

  • Red
  • Blue
  • Green
  • Yellow
  • Orange

enter image description here

Normally, there are 5! = 120 ways these balls can be organized (n!).

However, I have the following question:

Suppose we have the following "constraints:

  • The "Red" Ball can either be in the first or second position (From Left to Right)
  • There must be at least 2 positions between the "Blue" Ball and the "Green" Ball
  • The "Yellow" Ball can not be in the last position

Given all these "constraints", is there a mathematical formula that can be used to determine how many ways these 5 balls can now be ordered? That is, out of the 120 ways determined earlier - how many of these 120 ways are now considered "valid" according to the above "constraints"?

Since there only a small number of balls in this question, it's possible to store all possible combinations into a computer and then filter out combinations that don't match the above constraints. For example, here is how this can be done using the R programming language:

# generate all possible combinations

library(combinat)
library(dplyr)
library(data.table)
library(tidyverse)

my_list = c("Red", "Blue", "Green", "Yellow", "Orange")

d = permn(my_list)

all_combinations  = as.data.frame(matrix(unlist(d), ncol = 120)) %>%
  setNames(paste0("col", 1:120))

# keep combinations that match constraints

 tpose = transpose(all_combinations)

tpose %>%
  mutate(blue_delete = case_when(V1 == "Blue" & V2 == "Green" ~ TRUE,
                                 V1 == "Blue" & V3 == "Green" ~ TRUE,
                                 V2 == "Blue" & V3 == "Green" ~ TRUE,
                                 V3 == "Blue" & V4 == "Green" ~ TRUE,
                                 V4 == "Blue" & V5 == "Green" ~ TRUE,
                                 TRUE ~ FALSE)) %>%
  filter(V3 != "Red" & V4 != "Red" & V5 != "Red",
         V5 != "Yellow",
         blue_delete == FALSE) %>%
  select(-blue_delete)

# preview answer

       V1     V2     V3     V4     V5
1  Orange    Red   Blue Yellow  Green
2     Red Orange   Blue Yellow  Green
3     Red   Blue Orange Yellow  Green
4     Red   Blue Yellow Orange  Green
5     Red   Blue Yellow  Green Orange
6     Red Yellow   Blue Orange  Green
7  Yellow    Red   Blue Orange  Green

Running the above code, we see that out of the 120 possible ways - only 28 of these ways satisfy the above constraints.

My Question: Are there any "analytical formulas" which can be used to calculate the above answer?

Does anyone know if there any mathematical formulas that can be used calculate that there are 28 combinations for the above problem? Can this be formulated into a linear set of equations that is later solved?

Thanks!

References:

$\endgroup$
3
  • $\begingroup$ I do not follow the logic of your code with the mutate function, but the 6th option Red Yellow Blue Orange Green is uncorrect because blue and green do not have two positions between them. $\endgroup$ Jan 5, 2022 at 21:46
  • 1
    $\begingroup$ related stats.stackexchange.com/questions/559265/… $\endgroup$
    – Henry
    Jan 5, 2022 at 21:48
  • $\begingroup$ Based on @Henry 's comment I see now where this question is coming from. You can not simplify it so rigourously like this. There is no general solution closed formula solution (not one that is easy) and these type of problems require a custom made solution. For a specific type of question there might be certain assumptions and simplifications possible that can approximate the solution. To answer in that way you would need to give information about the background such that the appropriate assumptions and simplifications can be used in the answer. $\endgroup$ Jan 5, 2022 at 21:57

1 Answer 1

2
$\begingroup$

There is not a straightforward formula and you would have to apply several logical arguments.

  • The blue and green need two places in between them at least so they have to take positions 15, 14, or 25. (Giving 6 options because they can switch order among these three positions)

  • The red ball takes the other position in the 1/2 spot that is not taken by the blue/green ball.

  • The orange and yellow take the other two remaining positions in any of the two orders.

    • Except for the 1&4 position for blue/green (occuring twice for the two different orders of blue and green) in which case the vacant 5th position can not be filled with the yellow ball.

So there is 6x2-2=10 possibilities.

$\endgroup$
4
  • $\begingroup$ @Henry yes I missed that. $\endgroup$ Jan 5, 2022 at 21:48
  • $\begingroup$ $10$ is clearly correct $\endgroup$
    – Henry
    Jan 5, 2022 at 22:11
  • $\begingroup$ @ Sextus Empiricus : Thank you so much for your answer! Are there any algorithms (e.g. optimization) that can be used to "estimate" the number of combinations (according to some constraints) .... when the "number of balls" becomes very big? Thank you so much! $\endgroup$
    – stats_noob
    Jan 6, 2022 at 1:42
  • $\begingroup$ @stats555 it might be possible but it depends on the specific rules. In statistical mechanics you come across such type of restricted combinatorial problems (it looks a bit like a lattice model) but that is an incredibly large field. $\endgroup$ Jan 6, 2022 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.