Explore Discrete Math Examples

Need help in proving using mathematical induction
I got lost when trying to attempt the following question:
The function $(\genfrac{}{}{0ex}{}{n}{r})$ is defined for positive integers n and r with $$1\le <!--\; \le \; -->r\le <!--\; \le \; -->n$$ by $(\genfrac{}{}{0ex}{}{n}{r})$ = $\frac{n!}{r!(n-<!--\; -\; -->r)!}$.
Use mathematical induction to prove that $(\genfrac{}{}{0ex}{}{2n}{r})$, for all positive integers $$n\ge <!--\; \ge \; -->5$$.
Would really appreciate if anyone could help in the explanation.

Need help with discrete math question
A Board of Directors panel consist of one president, one vice-president, one secretary, one treasurer, and a three-person party committee. The entire board consists of seven distinct directors. If there are applicants, how many ways are there to choose a Board of Directors? Justify your answer.

Minimizing combinatoric sum of piecewise-linear functions
A convex piecewise-linear function can be defined as $f_i(x)={\mathbf{\text{max}}}_{j=1,\cdots <!--\; \cdots \; -->,m}{a}_{j}x+b_j$ where $a_j,b_j,x\in <!--\; \in \; -->\mathbb{R}$.
To find its minimum, I can construct a linear program using auxiliary scalar variable t. Namely:
$$\begin{gathered} \mathbf{\text{minimize }}t \\ \mathbf{\text{ subject to }}{a}_{i}x+b_i\le <!--\; \le \; -->t,i=1,\cdots <!--\; \cdots \; -->m \end{gathered}$$
And i can use similar strategy when solving minum of $f_1(x)+f_2(x)$.
Suppose i have a set of piecewise-linear functions $F=\{f_1(x),\cdots <!--\; \cdots \; -->,f_i(x),\cdots <!--\; \cdots \; -->,f_n(x)\}$.
How can i efficiently find an optimal partition (L,R) of F such that the $\mathbf{\text{min}}\underset{l\in <!--\; \in \; -->L}{\sum <!--\; \sum \; -->}{f}_l(x)+\mathbf{\text{min}}\underset{k\in <!--\; \in \; -->R}{\sum <!--\; \sum \; -->}{f}_k(x)$ is minimized ?

Proving an identity relating to binomial coefficients
Show that if n is a positive integers $2C(2n,n+1)+2C(2n,n)=C(2n+2,n+1)$
I know how to prove this algebraically, applying the formula and this is how it is also given in hints. Since I want to understand counting arguments I am thinking to give a proof of this using combinatorial arguments (double counting).
The right side is the number of ways to select $n+1$ elements from $2n+2$ elements. But I am not able to get an argument for the left side. I'm not getting how can I argue that I need to choose n or $n+1$ elements from 2n elements twice.

Proof rules in discrete math
When you write that a element is arbitrary, for example, "Let z be an arbitrary animal", does that automatically implies that you are using generalization rule as a proof?

Discrete Math functions and sets
1. Let A and B be subsets of Z, and let $F=\{f:A\to <!--\; \to \; -->B\}$. Define a relation R on F by: for any $f,g\in <!--\; \in \; -->F$, fRg if and only if $f-<!--\; -\; -->g$ is a constant function; that is, there is a constant c so that $f(x)-<!--\; -\; -->g(x)=c$ for all $x\in <!--\; \in \; -->A$.
Assume that $A=\{1,2,3\}$ and $B=\{1,2,\dots <!--\; \dots \; -->,n\}$ where $n\ge <!--\; \ge \; -->2$ is a fixed integer
(a) Let $f_1\in <!--\; \in \; -->F$ be defined by: $f_1(1)=2$, $f_1(2)=n$, $f_1(3)=1$. (As a set of ordered pairs, $f_1=\{(1,2),(2,n),(3,1)\}$). Suppose that $g\in <!--\; \in \; -->F$ is arbitrary so that $gR{f}_1$. Prove that $g=f_1$, and thus the equivalence class $[f_1]$ is just $\{f_1\}$.
(b) Find the number of functions $f\in <!--\; \in \; -->F$ so that $[f]=\{f\}$
(c) Prove that for all $f\in <!--\; \in \; -->F$, there exists $g\in <!--\; \in \; -->[f]$ so that 1 is in the range of g.
(d) Prove that for all $g,h\in <!--\; \in \; -->F$ with gRh, if there exists $a,b\in <!--\; \in \; -->A$ such that $g(a)=1$ and $h(b)=1$, then $g=h$
(e) Find the number of distinct equivalence classes [f] of R

I have seen in other questions (Painting the faces of a cube with distinct colours) , and found for myself there are 30 colorings of the cube with exactly 6 colors. My issue is when I use Polya enumeration theory I take the number of colorings up to 6 to be $\frac{1}{24}(6^6+3\ast <!--\; \ast \; -->6^4+12\ast <!--\; \ast \; -->6^3+8\ast <!--\; \ast \; -->6^2)$ and subtract the number of colorings up to 5, $\frac{1}{24}(5^6+3\ast <!--\; \ast \; -->5^4+12\ast <!--\; \ast \; -->5^3+8\ast <!--\; \ast \; -->5^2)$ to get 1426. What is wrong with my application of Polya enumeration theory? How could I fix it?

Hasse diagram for complexity classes
You are given the following complexity classes : REC (recursive) ,RE(recursively enumerable) , P , NP , NPSPACE , PSPACE ,REG(regular) , CF(Context Free). Draw them in a hasse diagram with short explanation.
I tried ranking the classes Reg < CF < P <NP < PSPACE=NPSPACE < REC < R.E. but I don't know how to make the hasse diagram.

Asymptotic Estimates for recurrence
Let
$$y_{n+1}-<!--\; -\; -->y_n\sim <!--\; \sim \; -->(1-<!--\; -\; -->y_{n+1}{)}^k$$
where $y_n\to <!--\; \to \; -->1$ as $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$. I was able to show that for $k>1$, $y_n-<!--\; -\; -->1\sim <!--\; \sim \; -->\frac{1}{n^{\frac{1}{k-<!--\; -\; -->1}}}.$.
What will the asymptotic estimate for $0<k<1$ be please? It seems to me it will be
$$y_n-<!--\; -\; -->1\sim <!--\; \sim \; -->k^{-<!--\; -\; -->n}$$
but I cannot show it.
REMARK: $x_n\sim <!--\; \sim \; -->y_n$ if $\frac{x_n}{y_n}\to <!--\; \to \; -->1$ as $n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$.

I'm confused about how to solve big-oh notation problems using the definition and basic algebra. for example, a problem like this:
Prove that $(x\sin <!--\; \; -->x+x\log <!--\; \; -->(2x+4)+((x^3+1)/(x^2+1))$ is an element of big-oh(x log x).
hint:This will require both the algebraic properties of O and its formal definition.
I'm thinking I can separate it into 3 parts and show each part is big-oh using limits(though I'm not sure that counts as an algebraic property) and the definition (C,K)?

Discrete math urn question without replacement.
An urn contains 30 purple gems, 25 green gems, 20 blue gems, 10 orange gems, and 5 red gems. Randomly picking 3 matching gems, without replacement, wins the game. What is the probability of picking the 3 winning purple, green, blue, orange and red gems respectively?
My method of calculation is not matching my simulation. They way I calculated the problem is as follows. I first listed out all possible winning outcomes by number of gems chosen for each color. There are 405 outcomes total as at least one color must have 3 gems and the pick of the remaining gems can be either 0,1 or 2. 3 to the power of 4 results in 81, multiplied by the 5 different colors (or positions if you will) gives us 405 different unique winning outcomes.
I then calculated the number of "ways" you can pick the order of the winning outcomes. For example there is only 1 way to pick 0 red, 0 blue, 0 green, 0 orange and 3 purple gems. While there is 3 ways to pick 0 purple, 0 green, 0 blue, 1 orange and 3 red gems. (ORRR, RORR, RROR)
Then I calculated the total hits. For example the total hits for picking 1 orange and 3 red is 600, $(5\times <!--\; \times \; -->4\times <!--\; \times \; -->3=60)$ for the red hits multiplied by 10 for the orange hit. I then calculated the sample space by taking the permutation of the total number of gems by the number of gems picked. Dividing the total hits by the sample space and then multiplying by the number of "ways" results in my probability for each unique winning outcome. Summing the wins for each color gave me the following probabilities.
- Purple: 0.4530
- Green: 0.3132
- Blue: 0.1941
- Orange: 0.0355
- Red: 0.0042
I wrote a quick simulation in C# which gives me the following probabilities after 10 million sims (rounded to 4 decimal places).
- Purple: 0.4434
- Green: 0.3109
- Blue: 0.1971
- Orange: 0.0414
- Red: 0.0072

Discrete Math Combinatorics Sets and Subsets
Can someone please explain why the following question's answer is (a)?
Let S be a set of size 37, and let x and y be two distinct elements of S. How many subsets of S are there that contain x but do not contain y?
(a) $2^{35}$
(b) $2^{36}$
(c) $2^{37}-<!--\; -\; -->2^{35}$
(d) $2^{35}+2^{36}$

1, A stamp collector wants to include in her collection exactly one stamp from each country of Africa. If I(s) means that she has stamp s in her collection, F(s,c) means that stamp s was issued by country c, the domain for s is all stamps, and the domain for c is all countries of Africa, express the statement that her collection satisfies her requirement. Do not use the $\mathrm{\exists <!--\; \exists \; -->}!$ symbol.
2.Determine whether $(p⟹<!--\; ⟹\; -->q)\wedge (\neg p⟹<!--\; ⟹\; -->q)\equiv q$

A counting question about pairs of three-digit numbers
the question asks how many pairs of 3 digit numbers exist such that when one is added to the other, we never have to use a "carry-over". For clarification, a carry-over occurs when you add $75+68$, because $5+8=13$, which contributes the "1" to the next round of addition "$7+6$". Note that you need to have another carry-over because $7+6+1=14$. Any thoughts would be appreciated.

Is there a k where $0\le <!--\; \le \; -->k\le <!--\; \le \; -->n$ such that ${\log }_2<!--\; \; -->(\genfrac{}{}{0ex}{}{n}{k})>\frac{1}{2}n$ for large n?
Is there an integer k where $0\le <!--\; \le \; -->k\le <!--\; \le \; -->n$ such that ${\log }_2<!--\; \; -->(\genfrac{}{}{0ex}{}{n}{k})>\frac{1}{2}n$ for large n?
In addition, we require that to find a k such that $(\genfrac{}{}{0ex}{}{n}{k})$ $>$ $2^{(\frac{1}{2}+\mathrm{\alpha <!--\; \alpha \; -->})\times <!--\; \times \; -->n}$ for some $\mathrm{\alpha <!--\; \alpha \; -->}>0$.

With 23 programs queued to run on a quad core processor, any of which that can run on multiple cores, how many different assignments are there?
There are 23 programs queued to run on a quad-core processor (processor with four cores). If each program can only be assigned to at most one core, and each core will have one program running on it, how many different combinations of programs can be run at the same time?
If any of the programs can be run on multiple cores at the same time, how many different assignments are there now?
My solution: For the first question, I got C(23,4) since out of 23 programs, only 4 programs will run at the same time and the order in which the programs are picked does not matter.
For the second question, however, I am unsure what the wording of this question is trying to point me towards. My thought process is that since each core will still have 1 program running on it at a given point in time and that any program can be run on multiple cores at the same time, then there is the possibility that the same program can be reused over multiple cores. Therefore, taking into account the number of program options over the four cores, the answer would have to be (23)(23)(23)(23). Is this how the problem should be done?

How many positive divisors of number 2646000 there? To solve it by multiplication principle. Should i test to divide it by something?

How many ways we can get a 3 cards from a deck (52 card 4 types) that every sequence is sorted ??
i mean get a seqeuences(length 3) that every right number equal/bigger than left one example (1 2 3) (J,Q,K) (7,7,7)
no return cards
i think to do 52C3/3! but in the solve its not right way ?

Proving terms using induction in LC
Let $(F_n^{\prime }{)}_{n\in <!--\; \in \; -->\mathbb{N}}$ be the family of terms defined by induction on $n\in <!--\; \in \; -->\mathbb{N}$ as follows:
$$\begin{array}{rlrl}{F}_0^{\prime }& =m& F_{n+1}^{\prime }& =c\underset{\_<!--\; \_\; -->}{n+1}{F}_n^{\prime }\end{array}$$
where c and m are variables, and $\underset{\_<!--\; \_\; -->}{n}$ is the Church numeral representing $n\in <!--\; \in \; -->\mathbb{N}$.
I'm trying to prove by induction on $n\in <!--\; \in \; -->\mathbb{N}$ that
$$F_n^{\prime }[\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}\mathsf{s}/c,\underset{\_<!--\; \_\; -->}{1}/m]{\to }_{\mathrm{\beta <!--\; \beta \; -->}}^{\ast <!--\; \ast \; -->}\underset{\_<!--\; \_\; -->}{n!}$$
and thus, by setting $F_n=\mathrm{\lambda <!--\; \lambda \; -->}c.\mathrm{\lambda <!--\; \lambda \; -->}m.F_n^{\prime }$,
$$F_n\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}\mathsf{s}\underset{\_<!--\; \_\; -->}{1}{\to }_{\mathrm{\beta <!--\; \beta \; -->}}^{\ast <!--\; \ast \; -->}\underset{\_<!--\; \_\; -->}{n!}$$
where ! is factorial, and times is a term such that timesa––$\mathsf{t}\mathsf{i}\mathsf{m}\mathsf{e}\mathsf{s}\underset{\_<!--\; \_\; -->}{a}\underset{\_<!--\; \_\; -->}{b}{\to <!--\; \to \; -->}_{\mathrm{\beta <!--\; \beta \; -->}}^{\ast <!--\; \ast \; -->}\underset{\_<!--\; \_\; -->}{a\times <!--\; \times \; -->b}$ for any $a,b\in <!--\; \in \; -->\mathbb{N}$. How can I do it?

Let $$A=\{1,2,3,4,5,6,7,8,9\}$$
How many functions $f:A\to A$ are there so that $f(1)=2$?
I believe the best way to solve this problem is to find the total number of functions ($9^9$) and subtract the number of functions such that f(1) does not equal 2. But I am not sure how to find that value. Any help would be appreciated.