The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

1
vote
1answer
77 views

Sequence corresponding to the generating function

Find the sequence corresponding to the generating function $$G(x) = \frac{2x^4}{2x^3-x^2-2x+1}$$ First of all, I wrote this equation like that; $\sum\limits_{n=0}^\infty(a_n)x^n = \frac{2x^4}{2x^3-...
7
votes
2answers
89 views

Prime Exponent Polynomials

This was a problem that my friend had on his final for a discrete math class that he mentioned he couldn't figure out. I tried, but I don't really know how to get started. Let $f(x)\neq 0$ be a ...
0
votes
1answer
40 views

How many paths in an NFA

Suppose there is a simple NFA, with 3 states (p,r,q) where p is the start and r is the final. Such that $\delta$ = (p,a,q), (p,b,q), (p,a,r), (p,b,r), (q,a,p), (q,b,p), (q,a,r), (q,b,r), (...
1
vote
1answer
50 views

Generating function of the sequence

Find the generating function of the sequence with $$a_n = \frac{(6^n+1)^2}{2^n}.$$ First of all I writed it like that $\displaystyle G(x) =\sum\limits_{n=0}^\infty\left(\frac{(6^n+1)^2}{2^n}\...
1
vote
1answer
42 views

Compute $\sum_{k=1}^{22}\binom{21}{k-2}3^k$

I just got to a new material in discrete math and I still cant get a good grasp of the material, if anyone can solve this, it'd be much appreciated. $$\sum_{k=1}^{22}\binom{21}{k-2}3^k$$
2
votes
1answer
28 views

create a word series with defined hamming distance among elements

I want to obtain all words of specific length/alphabet which have a minimal hamming distance among themselves. I'm not a mathematician so I try to show an example to make it clear what I need. ...
3
votes
3answers
75 views

Combinatorics - throwing colored dice

We throw 5 colored dice in the colors: blue, red, yellow, green, orange. How many results are they for: 1) In total 2) At least one die has the number '3' 3) Exactly one die has the number '2' and ...
1
vote
1answer
33 views

Combinatorics: Is this utilizing the pidgeon-hole principle?

How many ways can we assign four different jobs to five different employees, assuming it is possible to assign more than one job to any employee? Or is this as simple as doing $5^4$?
0
votes
2answers
20 views

Permutations and Combinations - Disc101

In how many ways can 32 people walk through 7 doors? My attempt :- C(32,7) But on the test I got this answer incorrect so can anybody help me figure out the actual answer?
2
votes
2answers
66 views

How many solutions are there for the equation?

Good night, question is this; $$x_1 + x_2 + x_3 + x_4 + x_5 = 67$$ when each odd indexed variable $(x_1,x_3,x_5)$ is a positive odd integer and each even indexed variable $(x_2,x_4)$ is a positive ...
0
votes
1answer
24 views

Can somebody explain the steps in this recurrence back substitution problem?

I'm usually good until the first couple of steps, then once you add more and more things I get lost pretty easily. Can somebody give me a step-by-step analysis of this? I'd really appreciate it. $$T_{...
0
votes
1answer
33 views

How do you find a perfect bipartite graph using Hall's Theorem?

According to my notes; • Theorem (Hall's Theorem) – If G is a bipartite graph, and for any 𝐴 ⊆ 𝑋 and any 𝐵 ⊆ 𝑌, and we have |𝐴| ≤ |𝑁(𝐴)| and |𝐵| ≤ |𝑁(𝐵)| , then there is a perfect matching ...
1
vote
2answers
56 views

bound and free variables

I have a question that has been bothering me for quite some time. In second order logic sometimes there is an indication that a variable can be both bound and free. The simplest example I can give is ...
1
vote
1answer
18 views

How to know which of these sets are equivalent

Let $A, B, C$ be sets that are all contains in a universal group $U$. 3 out of 4 of 4 of these groups are equivalent. Which one isn't necessarily equivalent? A. $((A \cap B) \cup (B \cap C)) \cap (\...
2
votes
2answers
42 views

The precise definition of injective

I'm studying from a book and inside it I have this question: Let $f:A\to B$ be a total function, which of the following states the $f$ is not injective: A) For every $x,y \in A$ if $x=y$ then: $f(x) ...
2
votes
2answers
32 views

Combinatorics - Choosing a group of 10 out of 2 groups

We have 26 boys and 62 girls and we'd like to know in how many ways we can choose a group of 10 out of them where at least 2 boys are in this group. What I did is I took the total number of ...
0
votes
0answers
42 views

How can one show that a simply connected graph has a vertex with an odd degree?

I'm studying for a final and came across a theorem for Eulerian graphs which states that a graph is Eulerian iff every vertex has an even degree. I suppose if we wanted to prove that a graph is not ...
1
vote
1answer
83 views

What would be a linear program formulation of finding the maximum degree of a graph?

Also, what would be a possible interpretation of the dual of this linear program? My teacher mentioned that it'd be interesting to interpret the dual but neither can I formulate the problem as an LP ...
0
votes
1answer
138 views

In how many ways can we order a dozen two-scoop ice cream cones?

An ice cream store sells $30$ different flavours of ice cream and it offers a choice of $3$ different kinds of cones. In how many ways can we order a dozen two-scoop ice cream cones if any two of them ...
1
vote
2answers
40 views

How is this summation simplified?

I'm taking EdX's probability class and one question asked to find the expectation of a uniform random variable (problem described here: https://youtu.be/vB6EKsX12hc). There's one part of the ...
1
vote
0answers
45 views

Problem with $n$ balls are placed into $n$ boxes using the Indicator Method

There are $n$ balls are placed into $n$ boxes, let $N_2$ be the number of boxes with exactly $2$ balls. Find the probability that $N_2 = n$ and the probability that $N_2 = n-1$. Use the method of ...
3
votes
1answer
125 views

Number of Dyck paths with maximal odd sequence of $(1,-1)$ ending on the $x$-axis

A Dyck path from $(0,0)$ to $(2n+2,0)$ is a lattice path with steps $(1,1)$ and $(1,-1)$, never falling below the $x$-axis. Find the number of Dyck paths from $(0,0)$ to $(2n+2,0)$ such that ...
1
vote
1answer
33 views

Discrete Math Graph Theory Independent sets

An independent set is a set of vertices in a graph, no two of which are adjacent. Let G be a graph with n vertices and with the maximal degree equal to ∆. Show that, G contains an independent set of ...
2
votes
0answers
32 views

Modeling Objective function using mixed integer programming formulation

I have the following objective function max 2x1 -2f(x2), where f(x2) = 3 if x2 = 0 and f(x2) = 2-5x2 if x2 > 0; can anyone help me formulate it using binary ...
1
vote
3answers
51 views

Understanding Reflexive Relations

I'm reviewing some problems to try and get a better understanding of relations. I get how a reflexive relation works on a defined relation with numbers, but not so much when its done with a set ...
1
vote
2answers
40 views

Prove that $\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$

I have this math question that I'm kind of stuck on. Prove that for all integers $1 < k \le n$, $$\frac{\binom{n}{k}}{n^k} < \frac{\binom{n+1}{k}}{(n+1)^k}$$ I have to use mathematical ...
0
votes
0answers
18 views

Let $G$ be a graph. Let $k$ be the minimal degree of $G$. Show that $G$ contains a cycle of length $k + 1$. [duplicate]

Let $G$ be a graph. Let $k$ be the minimal degree of $G$. Show that $G$ contains a cycle of length $k + 1$.
0
votes
1answer
22 views

Prove that $\frac{n-a}{n} < \frac{n+1-a}{n+1}$?

I have this math question that I'm kind of stuck on. Prove that $\frac{n-a}{n} < \frac{n+1-a}{n+1}$ So far I have that: $\frac{n-a}{n} < \frac{n+1-a}{n+1} = n-a < \frac{n(n+1-a)}{n(n+1)}...
-1
votes
1answer
69 views

absorption laws don't understand it with Venn diagrams

Absorption Law states $A∪(A∩B)=A$ and $A∩(A∪B)=A$. I can't seem to picture these with Venn diagrams can someone help me out ? Thanks
0
votes
2answers
38 views

Number of distinct digits

How many integers from 10 through 99 have distinct digits? Solution using the Multiplication Rule: [# of ints w/ dist. digits] = [# ways to pick digit 1] * [# ways to pick digit 2]. Since there are 9 ...
4
votes
1answer
58 views

Combinatorics - how many possible solutions are there for: $|x_1| + x_2+x_3 = 16$

How many possible solutions are there for this equation: $|x_1| + x_2+x_3 = 16$ ; $x_1 \in Z$ $x_2,x_3 \in N$ I know it's a simple combinatorics question but I'm still having trouble figuring it out....
0
votes
0answers
47 views

proof of hamiltonian cycle

graph Note that the graph has been constructed so that there are no cycles of length three (triangles) or four (quadrilaterals). Note also that the gra ph has a total of fifteen edges and ten ...
0
votes
1answer
61 views

2-player game, putting coins on a round table [duplicate]

Two players place coins of identical size (say quarters) on a round table. Each player has to place exactly one coin on the table without overlap with the coins already on the table. The first player ...
2
votes
1answer
29 views

Arranging 20 men and 20 women in a circle while none of the men should be next to a men

I have a simple question in combinatorics: I want to arrange 20 men and 20 women in a circle while none of the men should stand next to another men. What I did is this: I'll stick the first men as ...
2
votes
1answer
29 views

Combinatorics - all the ways to paint 30 balls.

You have 30 white balls, each ball can be painted in red or yellow, yellow balls can be painted with a purple stripe but can also stay completely yellow. In how many ways can we paint the balls if no ...
0
votes
0answers
21 views

Multiple Choice Integer Program Special Ordered Set Naming

I have been given a problem, for which I have a hard time to find literature, since I'm unsure about the right name of the problem. The problem is defined as: We have given $k$ sets and we need to ...
-1
votes
3answers
50 views

How do you find the inverse of $17x + 2$, to decode? [closed]

Let's say I'm trying to encode "hi". "h" is $7$ and "i" is $8$. To encode it you do $17(7) + 2 = 119 \pmod {26} = 15$ which is "p", $17(8) + 2 = 138 \pmod {26} = 8$ which is "i". Thus "hi" becomes "...
0
votes
1answer
47 views

How to generate all possible SEC matrices for $n$-bit

I want to know if there is an algorithm with which man can generate all possible forms of single error correction matrices for n bits of data, both linear and non-linear. For example all possible $32$-...
0
votes
0answers
9 views

How to choose basis functions that contribute most efficiently per term?

GOAL: I would like to approximate some positive, scalar function, f(x,y) > 0, on a 2D field of finite size i.e. x=[a,b],y=[c,d] OBSTACLE: I am familiar with the set of basis functions used in the ...
0
votes
4answers
47 views

Finding the $S_n$ of a recursion

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$ In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but ...
1
vote
1answer
73 views

Combinatorics - counting number of functions and counting possible combinations

The following two questions are from Richard Stanley's Enumerative Combinatorics: A box is filled with three blue socks, three red socks, and four chartreuse socks. Eight socks are pulled out, ...
0
votes
0answers
45 views

Prove that $2^{n+100} = O(2^n)$

Having trouble proving this for Big Oh. just dont know where to start with this one. I learn the basics over big oh notation so for this one, would i have so if $s(n) = 2^{n+100}$ and $a(n) = 2^n$ , ...
0
votes
0answers
29 views

Clarification about Direct Proofs

I was wondering what exactly constitutes a direct proof in discrete mathematics. For example if I prove an equation for some number larger than $n$, with a formula given to be used such as Euler's ...
0
votes
0answers
35 views

Recurrence Relations:

I have this recurrence relation I'm supposed to do, and I can't seem to figure out the next step: $T_{n} = T_{n-1} + 2n^2, T_{1} = 1$ What I have so far is this: $T_{n} = T_{n-1} + 2n^2$ $T_{n-2} +...
1
vote
1answer
33 views

Can someone explain the division in this proof of the sum of harmonic sequence? $(n+1)*h(n) - n$

So... this is the explanation my instructor gives in his PDF, but I can't make heads or tails of it. Use mathematical induction to prove that for all positive integers n: H1 + H2 + . . . + Hn = (n +...
3
votes
2answers
48 views

Understanding mathematical notation for coding problems.

The majority of my questions revolve around code (thus my activity on stackoverflow), but I've been going over interview question that assume a good understanding of mathematical notation. I don't ...
0
votes
2answers
54 views

Pigeonhole Principle, find the total number [closed]

There are 15 different coffee flavours at the cafe. Oddly, each student in my 8 am class has a favourite flavour there. There are just enough students in the class so you can be absolutely sure that 4 ...
0
votes
2answers
35 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
0
votes
2answers
176 views

Fewest operations on an algorithm?

I'm very stumped on this problem I have and was wondering if anyone could lend me a hand here? Suppose that you have two different algorithms for solving a problem. To solve a problem of size $n$, ...
0
votes
1answer
61 views

How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$

So i was given this question How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$ So i looked at it and decided i have to use the inclusion exclusion ...