For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
2answers
202 views

Stuck with two questions.

Hello i had new 6 questions but i cant solve this two any help will be appreciated thanks Question 4 (15%) A-) Give an one-line proof for $ n^r \ge C(n+r-1,r) $ [Hint: direct proof] B-) ...
0
votes
2answers
62 views

combinatorics problem : How many different choice are there So that exactly 3 candidate get most vote.

I need to solve this problem about combination : How many different choice are there in choice representative student group with five candidate and 40 students.(every student should be choose one ...
2
votes
1answer
94 views

probability convolution problem

Suppose $X,Y$ are uniformly distributed independent random variable on $\{1,...,N\}$ , compute the density of $X+Y$. So the density of $X$ or $Y$ is $f_X (x) = \frac{1}{N}$ (so if we sum the terms, ...
3
votes
1answer
320 views

Showing that the infinite grid is Eulerian

In a post to usenet in 2004, I wrote: I'm currently remembering learning [sic] some (long forgotten) things about Graph Theory via Robin J. Wilson's "Introduction to Graph Theory", 2nd. ed., ...
0
votes
2answers
199 views

3 Homework Question. Counting, Induction and Pigeonhole principle

First hello all. i have a homework with 10 question but im stuck with 3 i searched about them everywhere read other colleges lectures but i couldnt solved them finally i desired to ask here ...
1
vote
3answers
760 views

Three fair six-sided dice are tossed and the numbers showing on top are recorded.

I don't know if they are correct, these are my attempts Three fair six-sided dice are tossed and the numbers showing on top are recorded. How many different record sequences are possible? How many ...
3
votes
2answers
206 views

How to solve $2{x_{1}}+2{x_{2}}+{x_{3}}+{x_{4}}={12}$

How many solutions possible for the equation$$2{x_{1}}+2{x_{2}}+{x_{3}}+{x_{4}}={12}$$ all x are non-negative integer. I see these links but I don't know how to solve this problem.(I know how to ...
20
votes
1answer
1k views

The $n$ Immortals problem.

I saw this riddle posted on reddit a long time ago, called the "Seven Immortals." In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and ...
2
votes
1answer
115 views

interesting matrix

Let be $a(k,m),k,m\geq 0$ an infinite matrix then the set $$T_k=\{(a(k,0),a(k,1),...,a(k,i),...),(a(k,0),a(k+1,1),...,a(k+i,i),...)\}$$is called angle of matrix $a(k,0)$ is edge of $T_k$ ...
2
votes
1answer
48 views

Number of permutations without constants [duplicate]

Possible Duplicate: I have a problem understanding the proof of Rencontres numbers (Derangements) Given a vector of n elements, how can I calculate the number of "true" permutations, i.e. ...
4
votes
2answers
2k views

Summation of combinations [duplicate]

Possible Duplicate: simple binomial theorem proof Why is $${6\choose 0} + {7\choose 1} + \ldots + {n+6 \choose n} = {n+7 \choose n}\;?$$
1
vote
2answers
449 views

With n a positive integer, evaluate the sum

With $n$ a positive integer, evaluate the sum $$\binom{n}{0}-3\binom{n}{1}+3^2\binom{n}{2}+\cdots+(-1)^n3^n\displaystyle\binom{n}{n}=\sum_{k=0}^n(-3)^k\binom{n}{k}$$ Anyone know how to approach this ...
2
votes
3answers
399 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 ...
1
vote
0answers
98 views

Number of integer solutions

Suppose I want to find the number of solutions in the natural numbers to solve $ax + by + cz = N$ where $a, b, c, N \in \mathbb{Z}$ (not necessarily all positive). How would I set this problem up ...
0
votes
1answer
52 views

Number of ways to choose k people from an alphabetized list of n people, with “gap” g

Suppose I have an alphabetized list of n people, and I want to choose k from the list such that any two people are at least g away from each other on the list (E.g if g=2, then none of the k people ...
1
vote
2answers
97 views

Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$.Prove that multiplication two number of these numbers are complete square

Given 33 natural number so that their prime divisor just with $ 7,5,2,3,11$ is formed. Prove that multiplication two number of these numbers are complete square. Thank you.
0
votes
1answer
45 views

There is one set with 6 member(A). if we subsets $A_1 ,A_2, …,A_k$ choosed from $A$ so that $(i \ne j)$ and has hold $A_i \ne A_j \cup\{x\}$.

How to solve this problem? There is a set $A$ with 6 members. Suppose we choose $k$ subsets $A_1 ,A_2, ...,A_k$ of $A$ so that $A_i \ne A_j \cup\{x\}$ whenever $i\ne j$. What is maximum value of ...
1
vote
0answers
62 views

Simon Newcomb's problem

I am looking for an answer to the following problem. Let $S$ be the multiset $\{1^{d_1},2^{d_2},\dots,m^{d_m}$ $A_{S,k}$ is the number of permutations of $S$ with $k-1$ descents and no descent at the ...
1
vote
2answers
142 views

Some Questions About Chess

I have to questions about the chess game: please help me to understand it. 1- How can a computer program know if this move or that move is better? It calculates all possbile continuation and examine? ...
3
votes
1answer
57 views

Connective constant of the honeycomb lattice - detail of calculation

I am having a little difficulty with a calculation in "The connective constant of the honeycomb lattice equals $\sqrt{2+\sqrt2}$", Hugo Duminil-Copin, Stanislav Smirnov, (arXiv:1007.0575). On page 4 ...
5
votes
3answers
315 views

Binomial Theorem Question..

Just studying for my combinatorics exam. My prof said there would be a question similar to this one on the exam, so I'm trying to sort this one out. $$\sum^{20}_{k=0} \binom{41}{k}$$ I know if I ...
6
votes
1answer
443 views

Probability in Rock Paper Scissors competitions

My professor gave the following question as a bonus, if two brothers Pat and Steve enter a rock paper scissors competition with $2^n$ players. In this competition players are randomly paired and then ...
6
votes
1answer
225 views

Combinatorial proof that $\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}$

This recent question contains two proofs that $$\sum_{k=0}^n \binom{n}{k} \frac{(-1)^k}{(k+1)^2} = \frac{H_{n+1}}{n+1}.$$ One, by Antonio Vargas, uses a double integral. The other, by me, uses the ...
3
votes
2answers
181 views

No of n-digit numbers with no adjacent 1s.

Suppose there are {1,2,3} in a set. How many n digit numbers can you form such that there are no adjacent 1s. I tried randomly and tried to induce. I do not know how far I am correct. For n=2, it is ...
1
vote
1answer
50 views

Combinatorics with repetitons

I have read that in combinations with repetitions, the number of ways of selecting r objects out of n is: $$\binom{n+r-1}{r}$$ I have also read that this is the number of positive solutions for the ...
37
votes
15answers
10k views

Good Book On Combinatorics

What is your recommendation for an in-depth introductory combinatoric book? A book that doesn't just tell you about the multiplication principle, but rather shows the whole logic behind the questions ...
1
vote
0answers
40 views

About rotations of sets of vertices of a regular $p$-gon.

This is something I've been thinking about lately, and I don't seem to understand the problem well enough. There is a motivation to this problem, but I don't think giving it would be productive since ...
2
votes
1answer
125 views

Bijection Between Binary Rooted Trees and Planar Planted Trees

I was wondering if anyone could describe (or point me too) a description of a bijection between binary rooted trees and planar planted trees. My professor told me that this might be useful to know for ...
0
votes
2answers
104 views

Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7. So i'm not completely sure how to use strong induction, but the base case is ...
2
votes
2answers
294 views

Question about an 8 sided die

I have a question about an 8 sided die problem. I will put up my work what I have if someone can tell me how to proceed I will appreciate it. We roll an 8 sided die numbered 1 to 8 six times and ...
0
votes
2answers
146 views

Latin squares of even order-sub squares

Consider Latin squares of even order that is not of form $2^x$, where every cell is involved in a $2\times 2$ sub square. Here is one such square for order 6: ...
2
votes
1answer
258 views

Use a chinese abacus to translate hex and decimal numbers?

I read that the Chinese abacus is well suited to hex numbers as well as decimal, because its columns have 5 beads in the lower part, and 2 in the upper. Is there any efficient algorithm for ...
0
votes
2answers
132 views

$k$ hands in $n$'s hair

Moderator Message: this question is from an ongoing competition. Define a prime $p$ as having $k$ hands in $n$'s hair if $p^k|n$ and $n|2^n+1$ . Does there exist an integer $n$ with $2012$ hands ...
1
vote
1answer
229 views

Number of ways in which result of games can be predicted correctly

I have found this question: Suppose in a competition $11$ matches are to be played, each having one of $3$ distinct outcomes as possibilities. What is the number of ways one can predict the outcomes ...
0
votes
1answer
42 views

Combinations of various items

How many different combinations of $3$ can you make with $11$ items? I would think the answer to be $11\cdot10\cdot9$ but this is incorrect. Thanks.
1
vote
1answer
1k views

Proof that computing composition of permutations is in P

Consider the following problem: A permutation on the set ${1,…,k}$ is a one-to-one, onto function on this set. When $p$ is a permutation, $p^t$ means the composition of $p$ with itself $t$ times. ...
0
votes
1answer
162 views

In how many ways can the faces of a rectangular box can be painted so that the color changes occur only at each corner?

With three differently colored paints, in how many ways can the faces of a rectangular box can be painted so that the color changes occur only at each corner? I was trying to solve this by ...
2
votes
3answers
291 views

Algebraic manipulation of binomial theorem

Prove, by algebraic manipulation, that: \[ {{2n} \choose {n}} + {{2n} \choose {n+1}}={1\over2} {{2n+2} \choose {n+1}} \]
0
votes
1answer
206 views

$n=\{1,2,3,\dots,n\}$, How many subsets of cardinality $k$ containing element 1 are in $n$? [duplicate]

Possible Duplicate: Combinatorics: Number of subsets with cardinality k with 1 element. A set n has elements $\{1,2,3,\dots,n\}$. How many subsets does it have of cardinality $k$ and that ...
3
votes
2answers
214 views

Prove summation formula for binomial coefficients [duplicate]

Possible Duplicate: simple binomial theorem proof Prove that: \begin{equation} \sum_{k=0}^n \binom{k+a}{k}=\frac{(n+a+1)!}{n! (a+1)!}, \end{equation} where $a$ is a constant, without ...
9
votes
3answers
225 views

How to transform this infinite sum

How to transform this infinite sum $$\sum_{i\geq0}\frac{x^i}{(1-x)(1-x^2)\cdots(1-x^i)}$$ to an infinite product $$\prod_{i\geq1}\frac{1}{1-x^i}$$
4
votes
1answer
189 views

A variant of assignment problem (different sizes of sets)

I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always ...
3
votes
3answers
178 views

Connected subsets in a grid

Moderator Note: This question is from a contest which ended on 22 Oct 2012. Consider the above badly drawn diagram. Consider all subsets of $\left\{{1,2,3,4}\right\}$ if we were to place them ...
6
votes
2answers
1k views

Exploring Properties of Pascal's Triangle $\pmod 2$

Moderator Note: This question is from a contest which ended 1 Dec 2012. Consider Pascal's Triangle taken $\pmod 2$: For simplicity, we will call a finite string of 0's and 1's proper if it ...
1
vote
2answers
90 views

Making a $1,0,-1$ linear commbination of primes a multiple of $1000$

Prove that with every given 10 primes $p_1,p_ 2,\ldots,p_{10}$,there always exist 10 number which are not simultaneously equal to $0$, get one of three values: $-1$, $0$, $1$ satisfied that: ...
8
votes
1answer
156 views

Does there always exist such a convex hull?

Suppose that $v_{1}$, $v_{2}$, $\ldots$,, $v_{2k}$ are $2k$ points in the plane. Is is true that there is always a convex hull of a subset of the $2k$ points such that at least $k$ of the $2k$ points ...
3
votes
1answer
296 views

probabilities in Random Graphs

I am trying to find the probability of a bernoulli random graph on $n=10$ vertices with probability that an edge connects any pair of vertices is $p=\frac{1}{6}$ as $n\to \infty$. This is what I ...
4
votes
4answers
293 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
2
votes
1answer
198 views

Combinatoric Selection of Passwords

Give that a password can be 8-12 characters long and each character in the password can be ether composed of upper case letters, lower case letters, numeric digits, or one of the six special ...
0
votes
2answers
353 views

Different recurrence relations that model the same problem

I'm trying to solve the following counting problem, but my answer is different from the textbook's: Find a recurrence relation for the number of n-digit ternary sequences that have the pattern "012" ...