## finite groups – Combinatorics with dices

Let’s say that we play dice 30 times.

How many ways can I play the dice 30 times and the sum of all throws is 105.
I started by subtracting 30 to 105, since at least the result in every throw is ‘1’ and then I use the Bars and Stars Method to distribute the remaining 75 points in 30 boxes and I get (104,75). Now I need to subtract the cases whenever those boxes get more points than 5.

I am supposed to use the Principle Of Inclusion and Exclusion somewhere, but I don’t know how to use it. I am in my 1st year at college, so I would really appreciate if you could tell me how to think when faced with this kind of problems.

## combinatorics – \$2ntimes 4\$ \$(0,1)\$-matrix such that each row has two \$0\$’s and \$1\$’s and each column has \$n\$ \$0\$’s and \$1\$’s.

How many ways to fill a $$2ntimes 4$$ $$(0,1)$$-matrix such that each row has two $$0$$‘s and $$1$$‘s and each column has $$n$$ $$0$$‘s and $$1$$‘s.

Equivalently, how many ways to fill a $$2ntimes 4$$ $$(-1,1)$$-matrix such that each row and each column have zero sum.

By any chance, is there an asymptotic result for large $$n$$ ?

## python 3.x – Summing Sequence with Combinatorics

I am looking for help for two things.

1. proof of correctness (the tests have passed, but I do not now how to prove it correct)
2. Improvements on the Algorithm Efficiency.

The algorithm goes through 2 arrays arrays through permutations. The ordering is set up based on the array index, NOT the number inside the index. Noteably, if both parallel arrrays are set up diffrent, the algorithm should run fine.The algorithm then adds the function to the sum, which estimates computes the series.

Code is below.

``````
def f(x:float, y:float, a:float)->float:
"""
param x:float, x coordinate
param y:flaot, y coordinate
param a:float, paramter of the curve
"""
return x + (y * a)

def main():
"""
algorithm:
Suppouse arrays are orderd by thier index and NOT the element inside
Go through an ordering which meets that (one ordering is enough)
add on the function at that point to the sequence
"""
x = (1.0, 2.0, 3.0)
y = (2.0, 3.0, 4.0)
a = 2.0
seq = (0.0) * len(x)
for row in range(0, len(x) + 1):
for col in range(0, len(x) + 1):
for at in range(row, col):
seq(at) = seq(at) + f(x(at), y(at), a)
print(seq)

if __name__ == "__main__":
main()

``````

## combinatorics – Subset Question Dealing with Subsets With One element or Less

How many subsets of a set with $$100$$ elements have more than one element?

I know that a set, $$S$$, has $$100$$ elements, $$|S| = 100$$, and that all the subsets from $$S$$ is $$2^{100}$$, but how do I know how many subsets have one element? I know one is the empty set.

## combinatorics – Comparison required to encounter first different element in a group of elements

Suppose there are n (mostly) identical robots in a room, each of which is capable of
testing each other for speed. The testing equipment can test 2 robots at a time. During
the test each Robot will tell whether the other one is fast or slow. A fast robot always
reports correctly whether the other one is fast/slow. But the answer of a slow robot
cannot be trusted.

The possible outcomes are

``````R1 Reports |R2 reports |Comment

R2 is fast |R1 is fast |Both are fast, or both are slow

R2 is fast |R1 is slow |at least one is slow

R2 is slow |R1 is fast |at least one is slow

R2 is slow |R1 is slow |at least one is slow
``````

Consider the problem of finding one fast robot from among n robots

Assumption: More than half of the robots are fast.

a. Give and solve the recurrence that describes the number of tests T(n) needed
to find a single fast robot from n robots. Hint: Number of tests needed to
reduce the problem size to half=n/2 (robots tested in pairs)

b. Show that all Fast Robots can be identified with O(n) tests (tests done in
pairs).

This is part of one of sample assessment questions.

b. Show that all Fast Robots can be identified with O(n) tests (tests done in
pairs).

In case of fast robot I am able to understand that only 1 comparison is needed and that is why we are getting O(n) as order of test.

a. Give and solve the recurrence that describes the number of tests T(n) needed
to find a single fast robot from n robots. Hint: Number of tests needed to
reduce the problem size to half=n/2 (robots tested in pairs)

I think the worst case will appear when we will get fast robot after getting all the slow robots. Thing I am not able to determine is how I will decide that robot is slow or we have encountered a fast robot?

I am also not able to determine the type of the problem.

I am looking for some direction to solve this problem.

## probability – How do you define “independence” in combinatorics?

I feel like most definitions of “independence” are circular. Consider how we count the number of cards in a standard deck of cards: $$|S times R| = |S||R|$$, where $$S$$ is the set of suits, and $$R$$ is the set of ranks. That is, $$S = {text{Hearts, Diamonds, Spades, Clubs}}$$ and $$R = { 2,3,dots,text{King},text{Ace} }.$$ We know that $$|S| = 4$$ and $$|R| = 13$$, so $$|S times R| = |S||R| = 4 cdot 13 = 52.$$ In such an example, we define that they are independent, because they are disjoint subsets. But do we know that? In this example, it is “obvious.” What about examples where it is not obvious?

## combinatorics – Conditional combination – Mathematics Stack Exchange

I have 3 objects A, B and C

and 3 baskets 1, 2 and 3

A can go to any of the basket

But B can only go to the same basket with A or in the baskets that has higher number than what A chose.

C can only go to the same basket with A or B or in the baskets with higher number than what A and B chose

For example, if A is in basket 1, B can go to any of the 1,2,3. If B chose basket 2 then C can either go to 2 or 3. If A is in basket 3, B and C then have no choice and will have to go to basket 3.

I was struggling how to formulate it in a general way to find the total number of combination, so that I can do it for any number of objects and baskets.

## combinatorics – How to perform a reduced knapsack problem

I have a problem statement that seems to be a reduced version of the knapsack problem, but I don’t know how do it in Mathematica.

The problem is as follows:
Given a set, S, of integers (e.g {a,b,c,…}) and a specific integer T, find all the possible combinations of the elements of S that sum exactly to T. (e.g returns {a,d,e} and {e,f} because a+d+e=T and e+f=T).

## combinatorics – Pigeonhole Principle Proof Verification

Let $$a_1 different integers. Prove that $$n!Big|prod_{1leq ileq jleq n+1}{(a_j-a_i)}$$Here’s my proof:

Let $$kinbigl(nbigr)$$. $$k and using the Pigeonhole Principle, there are $$0leq i (or $$0leq i) such that $$a_i equiv a_jpmod{k}$$Thus, $$kbig|(a_j-a_i)$$Every $$kinbigl(nbigr)$$ satisfies this, and we are done.

Is the proof correct? I couldn’t find a mistake myself but it seemed weird that the use of the Pigeonhole Principle had $$n+1$$ pigeons and only $$k$$ holes (when $$k$$ can be as little as $$1,2,3$$). Am I missing something?

## combinatorics – Climbing/Descending the Integer Ladder

A fun combinatoric puzzle that’s popped up in my work that I think would be cute to have a Mathematica solution to, if anyone wants to give it a go. It’s basically a ladder climbing/descending problem so probably has a nice `Graph` solution.

Starting at $$0$$, over $$k$$ steps of $$pm1$$, what are the paths that will land on the integer $$n$$, assuming of course that $$k ge n$$.

I don’t mind if this question gets closed for lack of effort on my part (I’m currently working out an analytic solution) and would actually be very happy if this were closed as a duplicate/if someone could point me to the proper name for this problem. But I thought Mathematica.SE might enjoy a quick, easy problem to break the “solve my integro-differential equation for me” drudgery.