The combinatorics tag has no wiki summary.
3
votes
1answer
25 views
Dance couples riddle
Imagine there are $5$ women and $5$ men on a disco. Two of the gals have two brothers within the guys.
(image shows sibling relations)
In how many different ways can female-male couples be ...
1
vote
0answers
13 views
Reference: Qualifiers for defining trees
What is a good authoritative (i.e. has standard usage) reference accessible on the Net for checking the definitions of the multitude of terms used to describe trees in combinatorics?
Examples: ...
3
votes
0answers
26 views
Applications of parity formula on connected planar graph
I've been given the following problem as homework:
A graph is drawn in the plane and has 78 faces, all of them triangles.
Prove the outer face is not a 19-gon.
We're also given a hint to use the ...
3
votes
2answers
37 views
closed form of a simple binomial weighted series
Does it exists a closed form (also approximating) for the following binomial weighted series?
$$
\sum_{k=1}^n {n \choose k} \cdot k
$$
0
votes
1answer
33 views
A Combinatorial Structural Problem
Definition 1 ($MIF(k)$): A maximal intersecting family of k-sets [in short $MIF(k)$] is uniform intersecting family of k-sets such that if a k-set is not a member of family then there is at least a ...
1
vote
3answers
23 views
Choosing squares from a grid so that no two chosen squares are in the same row or column
How many ways can 3 squares be chosen from a 5x5 grid so that no two
chosen squares are in the same row or column?
Why is this not simply $\binom{5}{3}\cdot\binom{5}{3}$?
I figured that there ...
3
votes
1answer
43 views
Sufficient Condition for Tournament Score Sequences
There are $N$ players, and each player plays a match with everyone else exactly once. There is no tie. Each player's score is the number of matches he wins. What constraints can their scores be?
Is ...
0
votes
0answers
26 views
Monochromatic triangles in a two-coloring of the plane
A problem posed to me by a friend:
Show that any two-coloring of $\mathbb{R}^2$ that contains a monochromatic equilateral triangle of side-lengths 1 also contains monochromatic triangles of all side ...
28
votes
4answers
487 views
Strange Patience Game
I read about this game as a kid, but my maths was never up to solving it:
The score starts at zero. Take a shuffled pack of cards and keep dealing face up until you reach the first Ace, at which the ...
4
votes
1answer
62 views
Counting $k$-ary labelled trees
The (full) binary counting tree problems gives the number of binary trees can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = ...
1
vote
1answer
36 views
partition a number N into K tuples
Given an integer $N ≥ 0$ and an integer $K ≥ 0$, how many tuples $(n_1,\ldots,n_k)$ are there such that $n_i ≥0$ and $\Sigma n_i = N$? In other words, how many way can you "partition" $N$ into $K$ ...
1
vote
1answer
38 views
Programming: find the total possible combinations of three variables?
I have three variables in a programming function, and a 4th variable depends on these. I have to test the dependent variable against all combinations of the three variables:
Var A: 2 possible ...
2
votes
0answers
12 views
order of elements in a partition using Maple
I determined this whole partition but I just want to have the finer the partition
for example:
I have this
M[{{1, 2, 3, 4, 5}}]+M[{{1}, {2, 3, 4, 5}}]+M[{{2}, {1, 3, 4, 5}}]+M[{{5}, {1, 2, 3, ...
3
votes
2answers
157 views
Why does $\binom{10}{7} = \frac{10!}{(10-7)!7!}$
We just learned that: $\dbinom{10}{7}= \frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4}{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}$, so that:
If you throw a dice 10 ...
2
votes
3answers
91 views
How many ways to paint a rectangle
So i have the following task:
We have a rectangle 2 by 4 cells and four colors: red, green, blue, black.
How many ways are there to paint each cell, so that no two
cells with a common side ...
0
votes
0answers
37 views
Digits in big numbers?
How to identify digits in number 2 in degree 1000 its project eulers 16th problem, and I cant solve it. so, if it no hard for you, please explain it to me?
1
vote
1answer
18 views
Multiset Combination in Combinatorics
I want to buy a k-combination of doughnuts, where k is any amount less than or equal to the total doughnuts available. At the bakery there are n different types of doughnuts but there are restricted ...
1
vote
2answers
70 views
Multiset Combination in Combinatorics
I want to buy a k-combination of doughnuts, where k is any amount less than or equal to the total doughnuts available. At the bakery there are n different types of doughnuts but there are restricted ...
3
votes
1answer
30 views
permutations of a multiset having symbols with fixed multiplicity
Let $N$ be a multiset of $n$ distinct objects having the same multiplicity $k$. For instance,
$N=\{a,\,a,\,b,\,b\}$
where $n=2$ and $k=2$.
I was looking for the problem of counting the number of ...
0
votes
2answers
64 views
Prove $n+1$ items in $n$ buckets implies some bucket has $2$ items.
How would you formulate and formally prove (from a minimal set of axioms) the following statement is true?
For all positive integers $n$, if $n+1$ items are placed into $n$ buckets, than one of ...
0
votes
0answers
25 views
An optimization involving (random) graphs
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
9
votes
1answer
101 views
Words of Length $n$ over the alphabet $\{1,2,3\}$ with Restrictions
Let $w(n)$ denote the number of words of length $n$ over the alphabet $\{1,2,3\}$ with the restrictions that the number of $1$s present in a word be even and the number of $2$s present be odd.
I ...
2
votes
5answers
113 views
Sum from 0 to n of $ n \choose i $? [closed]
Possible Duplicate:
Algebraic Proof that $\sum\limits_{i=0}^n \binom{n}{i}=2^n$
Evaluation $\sum\limits_{k=0}^n \binom{n}{k}$
Is there a simple proof for this equality:
$$\sum_0^n {n ...
3
votes
2answers
40 views
Number of combinatorial progressions
A $k$-term combinatorial progression of order $2$ is defined as a set of positive integers $A=\{x_1<x_2<\cdots x_k\}$ such that the set $\{x_{i+1}-x_i:1\le i\le k-1\}$ has cardinality at most ...
1
vote
2answers
84 views
What are the basic generating functions?
What are the basic generating functions?
(if there is one's).
And what is the generating function of:
$$1 + 2x^2 + 3x^4 + 4x^6 + \cdots $$
Thanks.
5
votes
0answers
140 views
+50
Combinatorics question in the style of Van der Waerden's theorem
I would really appreciate some help with the following problem.
It resembles Van der Waerden a lot but I don't know how to proceed. I was told an averaging argument might do the trick but I can't see ...
4
votes
4answers
160 views
Combinatorics : Which side is heavier?
n coins are given, among which exactly 3 are bad and heavier than the good ones. A balance is used to identify the bad coins. Assume k coins are picked in both sides of the balance at a time. What is ...
5
votes
2answers
80 views
Probability and permutations
I performed an experiment in which an individual had to order 5 items (i.e. his "response" was something like $(3,2,1,4,5)$ or some other permutation). The correct ordering was $(1,2,3,4,5)$ and I ...
0
votes
0answers
38 views
Variant of the Towers of Hanoi problem
There is an interesting variant of the Towers of Hanoi problem, as found in the arcade game "Ichidant-R: Puzzle and Action". There you have n "valid" disks and m "invalid" disks in the form of frogs ...
5
votes
3answers
147 views
The coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$
I was asked about a simple question that is: "What is the coefficient of $x^{18}$ in $(1+x^5+x^7)^{20}$? Generally, we know that; $$(x+y+z)^n= ...
1
vote
2answers
62 views
Minimum set of US coins to count each prime number less than 100
Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set ...
3
votes
1answer
28 views
Combinatorial progressions and cubes
A k-term combinatorial progression of order d (abbreviated as k-CP(d)) is defined as an integer sequence $x_1<x_2<\cdots x_k$ such that the differences between successive numbers are at most d ...
2
votes
2answers
69 views
How do I accurately count the integers(1-1000) that are not divisible by 3,4,5,6?
I have the general algorithm here that my teacher gave us( see full at http://i.imgur.com/pbzQb.png) )
To count we just divide, correct?
like - 1000/3 = 333 ?
What is the sigma notation used ...
2
votes
1answer
23 views
What is the size of partitions versus subsets?
I know this might be a newbie question, but it's confusing to me.
What is a partition, does it only apply to integers? And how does the size of it compare to the size of subsets?
Also, suppose we ...
2
votes
3answers
78 views
What is the method to compute $\binom{n}{r}$ in a recursive manner?
How do you solve this?
Find out which recurrence relation involving $\dbinom{n}{r}$ is valid, and thus prove that we can compute $\dbinom{n}{r}$ in a recursive manner.
I appreciate any help. ...
4
votes
4answers
95 views
Number of White squares
In how many ways three white square can be selected on a 8 * 8 chessboard such that no two squares are in same row or column.
I am not able to reach on a conclusion for three squares. I have solved ...
5
votes
1answer
93 views
proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$
I'm looking for a proof of this identity:
$$
1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}
$$
I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum ...
4
votes
0answers
60 views
A sequence similar to the Catalan numbers
The $n$-th Catalan number $c_n$ has the closed form $\frac1{n+1}\binom{2n}{n}$ and follows the recursion $c_n = \sum\limits_{i = 0}^{n-1} c_{n-1-i}c_i$
I am interested in the quantity $e_n$ which ...
2
votes
1answer
89 views
Singularity of Generating Function
Given
$E' = (E^2 + E - x)/2xE$
$xF = E^3 E' + 2xE^3 E'' + E^2 - x^2$
where
$E = \sum_{n > 0}{e_n x^n}$
with $e_n = (n-1) \sum^{n-1}_{i = 1}{e_i e_{n-i}}$ for $n > 1$ and $e_1 = 1$
I am ...
0
votes
1answer
38 views
Calculating the number of unordered unique combinations of x cards to make specific hands
I'm currently in the process of writing an application related to poker, and I've been struggling to determine the full formula for a piece of this. I need to determine the number of ways to combine x ...
1
vote
2answers
64 views
Prove identity with Stirling numbers of the first kind
Let $a_n$ is the number of orderly divisions of set $\left\{ 1,2,...,n \right\}$ (which means that the sequence of blocks is important, but not the order of elements in blocks). Prove that: ...
3
votes
2answers
62 views
Number of 3 digit numbers in AP or GP
How many three digit numbers have the property that their digits taken from left to right form an arithmetic or geometric progression?
Please check all the cases.
5
votes
0answers
40 views
Optimal lower bound of $k$-sums for the integers $\{1,2,\ldots,n\}$ arranged around a circle in arbitrary order.
This question is motivated by the following two questions and is a slightly generalized version of them.
Some three consecutive numbers sum to at least $32$
Integers $1, 2, \ldots, 10$ are ...
3
votes
3answers
46 views
Proof of a Binomial Identity using a combinatorial argument
Question
Prove that if $k$ and $l$ are two positive integer with $k ≥ l$, then $\binom{2k}{2} =\binom{k−l}{2}+ \binom{k+l}{2}+ k^2 − l^2$
using a combinatorial argument.
I tried using Vandermonde's ...
2
votes
1answer
43 views
estimation $\cos$ of sum of random variables
Let $a_1\ge a_2\geq\cdots\geq a_n$ be real numbers. And let $r=(r_1,\ldots,r_n)$ be sequence of random variables taking on values
$1$ and $-1$ and such that $\sum_{i=1}^n r_i=0$.
I am wondering if ...
2
votes
1answer
76 views
Sum of every $k$th binomial coefficient.
It is widely known that $$\sum_{m=0}^{n} {n\choose m} = 2^n$$
and that $$\sum_{m=0}^{\lfloor\frac{n}{2}\rfloor}{n\choose 2m} = 2^{n-1}$$ Both results can be proven by exploting the nature of the roots ...
5
votes
1answer
194 views
Counting the number of pairs $(a,b)$ such that $M \mid a+b$ with $a, b \in [N]$
We have been given first $N$ natural numbers and asked to count all distinct pairs $(a,b)$ where, $a < b$ such that $a+b$ is divisible by a given number $M$.
Example: Given $N = 4$, i.e. ...
1
vote
1answer
55 views
Binomial probability
Suppose that the probability of a company supplying a defective product is $a$ and the probability that the supplied product is not defective is $b$. Before each product supplied is released for ...
6
votes
0answers
98 views
Lucky chance or combinatorial cause?
Consider an $n \times 1 - $rectangle where the $n$ squares are numbered $1$ to $n$. Cover this rectangle with white squares $a$, black squares $b$ and dominoes $dd$. To each covering of the rectangle ...
5
votes
0answers
103 views
Points and lines covering them
Let $n$ be a positive integer. A subset $S$ of points in plane satisfies the following conditions:
a) We can't find $n$ lines in plane, such that every element of $S$ belongs to at least one of these ...
