Permutations, combinations, bijective proofs, generating functions
2
votes
3answers
65 views
Weird $3^n$ in an identity to be combinatorially proved
Give a combinatorial proof of the following identity:
$$3^n=\sum_{i=0}^{n}\binom{n}{i}2^{n-i}$$
I can't see any counting argument that would yield $3^n$, and the right hand side is also pretty ...
1
vote
1answer
37 views
Proving an identity with a combinatorial proof
For any integers $n$, $k$, $r$ where $n\geq k\geq r \geq 0$, give a combinatorial proof of the following identity:
$$\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$$
The problem is that I ...
5
votes
2answers
56 views
Subgroup transitive on the subset with same cardinality
Maybe there is some very obvious insight that i miss here, but i've asked this question also to other people and nothing meaningful came out:
If you have a subgroup G of $S_n$(the symmetric group on ...
1
vote
1answer
41 views
A permutation problem
Consider all the permutations of the digits $1, 2, \dots, 9$. Find the number
of permutations each of which satis fies all of the following:
1) the sum of the digits lying between 1 and 2 (including ...
9
votes
1answer
197 views
How to find the smallest number with just $0$ and $1$ which is divided by a given number?
Every positive integer divide some number whose representation (base $10$) contains only zeroes and ones. One can easily prove that using pigeonhole principle.
...
3
votes
1answer
48 views
Distinguishable balls in distinguishable boxes
I wish to improve on my combinatorial reasoning skills and my step-father gave me this problem that has left me quite confused. It seems to me that because the balls are colored similar to the boxes, ...
-1
votes
3answers
105 views
Good books on combinatorics
I have a math Ph.D. but my knowledge of combinatorics sucks and I simply don't know how to compute anything more complicated, i.e. what happens when we put restrictions on the allowed configurations ...
-1
votes
0answers
39 views
A question about hyperplanes in affine geometries [closed]
List all hyperplanes in
$\operatorname{AG}_3(2)$
$\operatorname{AG}_4(2)$
What is the main idea while listing?
Can you explain please?
1
vote
1answer
51 views
Weight enumerator of the Hamming code
Let $H_r$ be the usual Hamming code of length $2^r-1$. What is the weight enumerator of $H_r^\perp$? Using this find an expression for the weight enumerator of $H_r$. (we are in binary case)
1
vote
1answer
68 views
Math Behind the Game “Quoridor”
I'm going to write an article for middle school students to introduce them to the game "quoridor".
Tha game certainly is interesting, but it will be great to add to the article some serious "math ...
3
votes
1answer
88 views
Determining probability of certain combinations
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?
I now know the ...
4
votes
0answers
30 views
Proving that the set of $\lfloor n/3 \rfloor+1$ partial Latin squares given by Pebody is unavoidable?
Introduction
Cutler and Öhman (2006) attribute to Pebody (via personal communication) a construction of a set of $k:=\lfloor n/3 \rfloor+1$ partial Latin squares which are unavoidable (i.e., any ...
1
vote
2answers
32 views
Choosing elements from sets
OK, so I've always been terrible at combinatorics and I'm trying to generalize some combinatorial problems and I can't figure out where I'm going wrong. Take the following problem:
Assume we are ...
3
votes
1answer
55 views
Finding number of functions in set A [duplicate]
Let $A = \{1, 2, 3, 4, \ldots, n\}$ (it follows that: $|A| = n$).
My objective is to count the number of functions: $f: A \rightarrow A$, that are monotonically increasing, i.e. $f(x) \leq f(x + 1)$, ...
1
vote
3answers
57 views
About the Pigeonhole principle
The principle says that: Let $k$ and $n$ be any two positive integers. If at least $kn+1$ objects are distributed among $n$ boxes, then one of the boxes must containat least $k+1$ objects. In ...
7
votes
1answer
71 views
Topology of Forum Posts
Okay, so here's an interesting question regarding web forums. Let's say you have a typical forum, such as the comments section on a blog, or whatnot. Viewers can post comments in response to either ...
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
46 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
142 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
66 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
3answers
162 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
91 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
148 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
35 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
155 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
1answer
311 views
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
54 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
131 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
73 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
26 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
50 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
36 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
121 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
42 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
26 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
67 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
70 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
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
188 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 ...
11
votes
0answers
63 views
Closed form for $\sum_{n=1}^\infty\frac{\psi(n+\frac{5}{4})}{(1+2n)(1+4n)^2}$
This question came up in the process of finding solution to another problem. Eventually, the problem was solved avoiding calculation of this sum, but it looks quite interesting on its own. Is there a ...
