Permutations, combinations, bijective proofs, generating functions
5
votes
2answers
57 views
Binomial probability with summation
Show that
$$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$
Attempt:
It becomes:
$$\sum_{k=0}^{m } \frac{\binom{m}{k}}{\binom{n}{k}}$$
Telescoping, pairing, binomial theorem don't ...
0
votes
2answers
45 views
$a_{k+1}-a_k = a_2 - a_1$,$\sum \limits_{k=1}^{n}{a_k}$=?
I need to find an explicit formula for the sum $\sum
\limits_{k=1}^{n}{a_k}$ where $(a_k)_{k∈ℕ}∈ℚ^ℕ$ with $a_{k+1}-a_k = a_2 - a_1$ for all k∈ℕ
I would love to start with by collecting the values of ...
1
vote
1answer
140 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i ...
1
vote
2answers
59 views
Permutations of a queue of interlaced boys and girls.
Suppose $5$ boys and $4$ girls are to be arranged in a queue such that between any
two boys there is at least one girl. Find the number of such arrangements possible.
What i think is $5$ boys ...
8
votes
4answers
145 views
Find a ternary $4\times 39$ matrix satisfying the conditions below
Can you find a matrix $A_{4\times39}$ with elements from $\{-1,0,1\}$ so that
No column is all zero.
All columns are different.
No column is $-1$ times another column.
Each row consists of $13$ of ...
0
votes
1answer
42 views
total number of different mixes
Patient Age Avg Visits / Year
<1 year 7.5
1-4 years 3.0
5-14 years 1.8
15-24 years 1.7
25-44 years 2.6
45-64 years ...
14
votes
0answers
140 views
Possible Playable Chords on a Guitar
Fingerstyle Guitar Chord Diversity Check
Considering a $20$-fret $6$-string acoustic guitar and supposing that the fretting range (inclusive of the fingered notes) for an average hand is $4$ frets in ...
0
votes
1answer
33 views
how often does a value appear in a combination
Say I have a set of numbers 1,2,3,4,5,6,7,8,9,10 and I say 10 C 4 I know that equals 210. But lets say I want to know how often 3 appears in those combinations how do I determine that?
10
votes
2answers
154 views
Choosing a linear map $(\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ which is nonzero on half of a sequence of vectors
Let $v_1,\ldots,v_m \in (\mathbb{Z}/2\mathbb{Z})^n$ be nonzero vectors. Is it always possible to choose a linear map $f : (\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ such that $f$ ...
3
votes
0answers
211 views
+500
Conjecture regarding trapping rational numbers in some special intervals
Conjecture:
Let $b\in\mathbb{N}_{\geq3}$ and $\{x_i\}$ be a collection of $b−2$ rational numbers greater than $1$. Does there always exist a natural number $a$ such that for all $i$ there exists some ...
3
votes
6answers
60 views
How to prove a limit with a recurrence?
$s_1 = 1$ and $s_{n+1} = \dfrac{s_n + 1}{3}$ for $n \in \Bbb N$.
How do you find $\displaystyle \lim_{x\to \infty} s_n$?
Then how do you prove that the value is the limit using the definition of the ...
3
votes
1answer
52 views
Counting 0-1 matrices up to symmetry
I'm interested in counting the number of n×n 0-1 matrices with a given number of 1s up to rotation and reflection. What is the best way to do this if n is not too small?
For example, consider ...
2
votes
1answer
35 views
Proof of bipartite graphs with $k$ edges
Let $b_k(n)$ be the number of bipartite graphs (without multiple edges) with $k$ edges on the vertex set $[n]$. Show that: $$\sum_{n\geq 0}\sum_{k\geq 0}b_k(n)q^k\frac{x^n}{n!}=\sqrt{\sum_{n\geq ...
1
vote
3answers
121 views
Evaluate a sum with binomial coefficients
$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$
I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$
...
3
votes
1answer
71 views
65-card deck consisting of 13 ranks and 5 suits
** I FIGURED OUT 15 out of 16 cases. I don't understand the last case of RUNT. Anyone helps?
I recently went to a math event and one person presented a weird card deck, consisting of 13 ranks and 5 ...
1
vote
0answers
25 views
Probability question using PIE
Five people check identical suitcases before boarding an airplane. At the baggage claim, each person takes one of the five suitcases at random. What is the probability that every person ends up with ...
2
votes
6answers
48 views
calculate the number of possible number of words
If one word can be at most 63 characters long. It can be combination of :
letters from a to z
numbers from 0 to 9
hyphen - but only if not in the first or the last character of the word
I'm trying ...
1
vote
2answers
33 views
Combinatorics/Probability - Multiple Groups Example Problem
Joe, an avid and properly licensed sportsman, is in his hunting blind when he locates 20 Canada geese, 25 Mallard ducks, 40 Bald Eagles, 10 Whopping Cranes, and 5 Flamingos. Joe randomly selects ...
4
votes
2answers
119 views
Derivative of Schur function
In his answer to http://mathoverflow.net/questions/129854, R. Stanley says that the partial derivative (over the relevant x[i]) of the Schur function of a partition lambda of n equals the sum the ...
4
votes
1answer
17 views
Prove that $h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$
How do I show that
$$h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$$
Can anyone just give me like a hint or "headstart"? Thanks!
5
votes
1answer
41 views
Growth rate of formula
I have formula: $\frac{(m+n)!}{m!n!}$
I am wondering what is growth rate of it. Can I say that it grows exponentially with m and n? Or maybe this is different growth rate?
Greetings,
Rnd
0
votes
0answers
25 views
Sets of numbers satisfying a simple additive property
There are four sets of size $N$ in the integers, say $A_1,A_2,A_3,A_4$. And for at least $\epsilon N^3$ of the tuples $(a_1,a_2,a_3,a_4) \in A_1 \times A_2 \times A_3 \times A_4$ it is true that $a_1 ...
2
votes
3answers
65 views
Factorial Equality Problem
I'm stuck on this problem, any help would be appreciated.
Find all $n \in \mathbb{Z}$ which satisfy the following equation:
$${12 \choose n} = \binom{12}{n-2}$$
I have tried to put each of them ...
1
vote
1answer
44 views
binary circle - difficult question
I ran into this question and I'm not really sure how to start.
we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$,
we'll define $n_{w}$ as the number of times ...
2
votes
1answer
66 views
Probability to complete a sequence with two attempts
Imagine a slot machine with $N$ reels.
I want to calculate the probability $P$ that a player hits a certain sequence $A$, if the player has given the possibility to spin again (and only once again), ...
0
votes
0answers
57 views
Ball and holder problem [duplicate]
I am trying to solve this but having a tough time deriving the formula.
There are $X$ ball and $Y$ holders $Y \leq X$. Out of the $X$ balls, $N$ are red and $X-N$ are blue.
What is the probability ...
1
vote
1answer
50 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
52 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
179 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
2answers
38 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
66 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
58 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
107 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
32 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
37 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
39 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
34 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
225 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
187 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
85 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} = ...
