Permutations, combinations, bijective proofs, generating functions
3
votes
0answers
12 views
Different Perspectives of Multinomial Theorem & Partitions
There are 2 important interpretations of the multinomial theorem and coefficients.
1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
0
votes
0answers
26 views
What is the probability that, given the smallest of 50 random integers(>0), it will be the smallest of 50 other random integers (one being itself)?
More generally, if an array of random integers (size N), and another array of random integers (size M), "overlap" by R numbers (have them in common):
What is the chance that the smallest of one is the ...
3
votes
2answers
33 views
Probability of selecting correct answer in 15 out of 25 exercises with 0.25 chance
There are 25 exercises, each one consists of answers: a, b, c, d and only one answer is correct. My question is what is the probability of selecting correct answer in 15 out of 25 exercises.
My idea: ...
3
votes
1answer
18 views
How many different 2-regular graphs are there with 5 vertices?
How many different 2-regular (simple) graphs are there with 5 vertices?
I just asked a very similar question, and I actually already understand the answer of this question.
I think there are ...
0
votes
0answers
29 views
Is there a two name Wikipedia pangram? [closed]
Benjamin Franklin Goodrich and François-Xavier Wurth-Paquet are people in Wikipedia with the letters A-O and N-X.
Is there a pair of names in Wikipedia that has all the letters A-Z? I use ...
-4
votes
0answers
33 views
which kind of data related to permutation group and SSYT [closed]
if do not have these books, then just focus on which data related to permutation group and SSYT
page 309 in enumerative combinatorics book volume 2 (old edition)
prepare to apply this chapter, which ...
2
votes
1answer
19 views
Partitioning of subsets
This is a previous exam question.
Let $S$ be a subset of $\{10,11,...,99\}$ containing 10 elements. Show that there will exist two disjoint subsets $A$ and $B$ of $S$ such that sum of the elements of ...
0
votes
0answers
42 views
Counting number of spanning trees in $(3n,n)$-turan graph
I'm working on a problem regarding $(kn,n)$-Turán graphs. The $(2n,n)$-Turán graph, also known as the cocktail party graph, has a closed formula for its number of spanning trees.
I want to know if ...
0
votes
3answers
44 views
About ascending numbers
I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$
How can I find ...
3
votes
2answers
80 views
How does this “combinatorial proof” work?
For any non-integer $n$,
$$(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$$
Let $y_1,\dots,y_n$ be variables and, for any subset $S$ of $\{1,\dots,n\}$, let $y^S$ denote the product of the $y_i$'s for each ...
0
votes
1answer
40 views
Conditional probability Bayes Theorem
I am trying to solve this problem but I am not sure how to obtain the formula given below. Any help would be appreciated.
A boy is selected at random from among the children belonging to families ...
4
votes
1answer
29 views
$\frac{1}{4^n}\binom{1/2}{n} \stackrel{?}{=} \frac{1}{1+2n}\binom{n+1/2}{2n}$ - An identity for fractional binomial coefficients
In trying to write an answer to this question:
calculate the roots of $z = 1 + z^{1/2}$ using Lagrange expansion
I have come across the identity
$$
\frac{1}{4^n}\binom{1/2}{n} = ...
0
votes
1answer
22 views
Select 11 items in decreasing or increasing order from a set of 101
101 people stand in a line, all of them different heights. Show it is possible to find 11 people so that the order of their heights in line (not necessarily next to each other) is increasing or ...
1
vote
0answers
12 views
Finding the fractional vertex-cover number ($\tau ^ \star$) for k-cycle hypergraphs.
Given a hypergraph $H$, we define $\tau (H)$ to be the minimum-vertex-cover number of $H$. That is, the size of the smallest $C \subseteq V(H)$ such that $C$ meets all edges in $E(H)$.
A quite ...
2
votes
2answers
38 views
How many subsets of size at most $\log n$ does a set of size $n$ have?
I was reading this paper on an algorithm for finding a dominating set in a tournament graph. The paper claims that an $n$-element set has $n^{O(\log n)}$ subsets of size at most $\log n$. The paper ...
