Explore Discrete Math Examples

Recent questions in Discrete math
Discrete mathAnswered question
Nyasia Flowers Nyasia Flowers 2022-09-05

How many 5-digit numbers are there, so that 0,1 and 2 are NOT included, 3,4 and 5 have to be included
I have the following question. How many 5-digit numbers are there, so that the following conditions are satisfied:
- 0,1 and 2 are NOT included
- 3,4 and 5 have to be included
The list of possible numbers to choose from is (3,4,5,6,7,8,9). As we know, 3,4 and 5 have to be included in every number, for example 33475, 54339 etc.
I tried to do this as follows:
For the 1. digit, I can choose 3,4 or 5. So, I basically have ( 3 1 ) choices. For the 2. digit, I have 2 numbers to choose from, for example 4 or 5 if 3 is the 1. digit, 3 or 5 if 4 is the 1. digit etc. So, that's ( 2 1 ) . For the 3. digit there is 1 number to choose as per reasoning for choosing the 2. number. That's basically ( 1 1 ) . For the 4. and 5. digit, there are ( 7 1 ) possibilities respectively, because any number from the list can be chosen.
At the end I get ( 3 1 ) ( 2 1 ) ( 1 1 ) ( 7 1 ) ( 7 1 ) = 3 2 1 7 7 = 294 possible numbers. Now, you can permute those choices between the digit places. There are 5 digits, so it would be 5 ! = 120 possible permutations. In the end I got 294 120 = 35280 numbers. However, the problem is that there are not 120 such permutations, because for some cases one number is counted multiple times.
I know from my class that the answer is 1830. And I also got the hint from my professor to use the inclusion-exclusion principle. But with that I have problems to start.
So, could somebody help me either how to calculate this with the inclusion-exclusion principle OR with the way I tried to do this, i.e. how to NOT multiple count those numbers.

Discrete mathAnswered question
Addison Parker Addison Parker 2022-09-05

A multigraph G has even no of Hamiltonian paths
Definition (Stick) : A path s = e 1 , . . . , e m in G,where the end vertices of the edge e i are v i and v i + 1 and 1 i m. The path s is called a stick.
Corollary : Let G be a multigraph, let u , v V, and suppose that d(w) is odd for each vertex w V- {u,v} ϕ. Then number of Hamiltonian Paths in G from u to v is even.
Proof: We may assume that u and v are adjacent vertices (if they are not we may add an edge between them); let e be an edge between u and v. We choose the stick s to be the edge e with u = u 1 and v = v 2 ; if w V then ϵ ( w ) is the number of edges from u to w.Consequently a Hamiltonian path h beginning with s and ending in w gives rise to exactly ϵ ( w ) hamiltonian paths from u to v. But by Theorem 1.1 the number of such paths ending in the set W = { w V : ϵ ( w ) is odd} is even.
My understanding of proof :
- Since the graph is Hamiltonian if the edge uv is missing we add it.
- Now that stick s has to be the edge with u = v 1 does this mean u = v 1 is incident with last edge of stick.
- For Hamiltonian paths to be to be even it is obvious that after deletion of {u,v} we are left with vertices of odd degree and since its a multigraph loops are allowed which leads to set W being have paths of odd length i.e ϵ ( w ) is odd so we have even number of vertices and sum of odd degrees with even no of vertices is even.
But what I dont get from the proof is how there are ϵ(w) Hamiltonian paths?

Dealing with discrete Math is an interesting subject because discrete Math equations can be encountered basically anywhere from scheduling of sports games and live shows to education where each person is examined online. It is a reason why discrete math questions that we have collected for you are aimed at solutions that go beyond equations to provide you with the answers that will help you understand the concept. Still, discrete Math equations are explained as well by turning to problems in computer science, programming, software, and cryptography among other interesting subjects like software and mobile apps development.