Permutations, combinations, bijective proofs, generating functions
1
vote
1answer
53 views
Ferrers Diagram Partitions
Using Ferrer's diagram, prove that the number of partitions of n in which each part is 1 or 2 is equal to the number of partitions of n+3 which has exactly two distinct parts.
Any help please, all I ...
3
votes
2answers
53 views
Solution gives wrong answer to probability problem
Great Northern Airlines flies small planes in northern Canada and Alaska. Their largest plane can seat 16 passengers seated in 8 rows of 2. On a certain flight flown on this plane, they have 12 ...
1
vote
1answer
28 views
Combinatorial Techniques: Putting two and two together
This is a $3$-part question. I got the first two parts, but could not get the third part (which uses the first two parts):
Pick sequence of $8$ coins from sack of $40$ coins, containing $10$ pennies, ...
0
votes
0answers
106 views
(3n,n)-Turán graph [closed]
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 there ...
12
votes
2answers
184 views
A card game with no decisions
A friend showed me a mindless card game he plays, in which the initial state of the deck completely determines whether he wins or loses. The game is played as follows:
Shuffle a standard $52$ card ...
3
votes
3answers
46 views
Probability/Combinatorics Problem - Old Maid Cards
A special deck of Old Maid cards consist of 25 pairs and a single old maid card. All 51 cards evenly between you and two other players – 17 cards for each player.
(a) how many different ...
1
vote
0answers
42 views
Calculating a probability
Given $m\cdot e$ balls, $b$ of which are black (suppose the rest are white balls). Randomly put the balls into $m$ baskets, with $e$ balls in each basket. What is the probability of the event that ...
1
vote
2answers
53 views
A probability question: a building and an elevator.
Suppose that 7 people waiting for an elevator in a building with 14 flours.
Q: What is the probability that every person get out in different flour?
My attempt:
There is $14 \cdot 13 \cdot 12 \cdot ...
4
votes
0answers
67 views
A combinatorial problem.
Let be $(X, \mathbb{A}, \mu)$ a measure space, a partition of $ X $ is a disjoint family $\xi=\{P_1,\ldots,P_k \}$ of measurable sets such tath $\bigcup P_i=X\pmod0).$
If $\xi=\{P_1,\ldots,P_k ...
1
vote
1answer
67 views
Distributing objects in boxes
In how many way can we distribute: 7 objects in 3 boxes;
provided that:
1) objects are distinct, boxes are distinct and boxes may be empty;
2) objects are distinct, boxes are distinct and boxes may ...
8
votes
3answers
108 views
How can one show $100!=100 \cdot 99!$ by combinatorial arguments
How does one show $100!=100\cdot 99!$ by using combinatorial arguments?
4
votes
0answers
34 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 ...
1
vote
1answer
53 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
38 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: ...
4
votes
2answers
41 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
35 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
35 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
22 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
226 views
Counting number of spanning trees in $(3n,n)$-turan graph [closed]
Moderator Note: This is a current contest question on codechef.com.
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 ...
0
votes
3answers
50 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 ...
9
votes
1answer
188 views
What can we say about the size of $HK\cap KH$ when $HK\neq KH$?
If $G$ is a finite group, and $H$, $K$ are proper subgroups of $G$, then it is not necessary that $HK=KH$. But, these two subsets have same size. The question I would like to ask, then, is
If ...
3
votes
2answers
86 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
67 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
30 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
25 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
41 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
49 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 ...
1
vote
1answer
29 views
Need an algorithm to compute number of elements in sample space
An urn contains $X$ red balls, $Y$ green balls, and $Z$ white balls. $N$ balls
are drawn without replacement from the urn, and the colors are noted in sequence.
$N \leq X+Y+Z$
Trying to come up ...
2
votes
1answer
71 views
Riddle - cover a $62 \times 66$ board using only $341$ straight rows of $12$ squares each
Is it possible to cover a $62 \times 66$ board using only $341$ straight rows of $12$ squares each?
0
votes
1answer
48 views
Find the quantity of such numbers
A six digits number $abcdef$ satisfy:
Each digits is non zero.
$ab+cd+ef$ is even.
Find the number of such six digits numbers.
The answer given is $56^3+3 \cdot 56 \cdot 25^2$, ...
-1
votes
1answer
15 views
How to get permutation group from one dimensional discrete data
when think this question, i search a matrix in a book related to permutation group
however do not know where this matrix come from.
What do A come from in page 318 of Enumerative Combinatorics Volume ...
1
vote
2answers
60 views
Longest antichain of divisors
I Need to find a way to calculate the length of the longest antichain of divisors of a number N (example 720 - 6, or 1450 - 4), with divisibility as operation.
Is there a universally applicable way to ...
0
votes
1answer
34 views
Summing ratio of partial sums of binomial coefficients
I would like to approximate the following when $n \gg k$.
$\sum_{y = k + 1}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m} (y - 1)}{\sum_{m = 0}^k {y - 1 \choose m}}.$
The formula can be re-written ...
2
votes
3answers
66 views
Finding the number of strings which do not contain a certain substring…
I want to know the method of solving the following problem:
"How many binary strings of length 10 are there each of which does not contain the pattern '110' ?
3
votes
2answers
47 views
Combinatorics/Probability Distribution Example Question
At a local fast-food restaurant in Oregon (no sales tax), fries, soda, hamburgers, cherry pie, and sundaes cost \$1 each. Chicken sandwiches cost \$2 each. You have five dollars. How many ...
0
votes
2answers
47 views
A Nim variant: Number of stones
Alice and Bob play the following game. There is one pile of $N$ stones. They take turns to pick stones from the pile, Alice will play first. In each turn, a player can only pick $k$ $(a \le k \le b)$ ...
1
vote
1answer
43 views
Weighted sum of ratio of partial sum of binomial coefficients
I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$,
$$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...
2
votes
1answer
30 views
Probabilistic method Kraft-McMillan inequality
I am trying to solve as many problems as I can but I am a little confused on this one. It is in chapter 1, problem 9 (Probabilistic method, Alon & Spencer). The problem says
Let $F$ be a finite ...
1
vote
1answer
20 views
Count the number of unique equal sized partitions of a set.
Given the integers $[1, ck]$, they will be partitioned into $c$ subsets of size $k$. I want to count the number of unique versions of each subset (where order matters).
Clearly, there are ${ck ...
0
votes
2answers
55 views
How many possible ways to pick 4 items from a collection of 20?
There are 20 students in the high school glee club. They need to pick four students to serve as the student representatives for an upcoming trip. How many ways are there to choose the representatives?
...
2
votes
1answer
30 views
Dirichlet series generating function
I am stuck on how to do this question:
Let d(n) denote the number of divisors of n. Show that the dirichlet series generating function of the sequence {(d(n))^2} equals C^4 (s)/ C(2s).
C(s) ...
2
votes
1answer
49 views
Expanding the power series $\prod_{i\geq 1}(1+x_i+x_i^2)$
How do I expand the power series $$\prod_{i\geq 1}(1+x_i+x_i^2)$$ in terms of the elementary symmetric functions?
Thanks!
0
votes
1answer
77 views
Probability of choosing C out of T students with restrictions
There is a class of $T$ students, consisting of $G$ girls and $(T - G)$ boys. Out of the $T$ students, only $C$ are selected for an examination. What is the probability that there are at least $K$ ...
3
votes
3answers
23 views
Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].
Recursion relation: Number of series length n made of $(0,1,2)$ so that each pair sum is between 1 and 3. [including them].
So what i did was:
Let $a_n$ be the total number of series length n so ...
0
votes
2answers
43 views
Here is a puzzle from Permutations and combinations
How many permutations of 1,2,3,4,5,6 are such that each odd number is next to at least one even number ?
1
vote
1answer
22 views
Dice Roll Permutation Problem
Here is my problem:
You have a standard dice, with possible rolls: $\{1, 2, 3, 4, 5, 6\}$. How many permutations exist in 10 rolls such that no two immediate rolls are the same?
For example:
$\{1, ...
9
votes
7answers
352 views
Why is it important to study combinatorics?
I was having a discussion with my friend Sayan Mukherjee about why we need to study combinatorics which admittedly, is not our favourite subject because we see very less motivation for it(I am not ...
8
votes
1answer
78 views
Finding prime elements in a subset
Consider the set $S= \{1,2,\cdots,2n\}$. Let $\mathscr{B}$ be a subset of $S$ which contains strictly more than $n$ elements.
Prove that we can find elements $m,k$ in $\mathscr{B}$ such that $m+k$ ...
2
votes
2answers
35 views
From Combination to Permutation
I am facing a (probably) basic counting issue.
If $P(n,r)$ the permutations for $r$ objects from $n$ and $C(n,r)$ the combinations, we have : $P(n,r) = r!C(n,r)$.
Yet there are two example in which ...
2
votes
3answers
27 views
Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.
Using recurrence relation: How many n length series using [0,1,2] the sum of each pair is 3 at the most.
Analyzing the question means that the pair (2,2) where-ever it appear is making the problem.
...
