This tag is for basic 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 (5)

0
votes
1answer
40 views

Covering a $8\times 8$ chessboard with dominoes without placing any domino over another.

In how many ways can $8\times 8$ chessboard be with dominoes without placing any domino over another. I have this problem in my mind since I read colouring proofs. This question has been ...
0
votes
2answers
31 views

Partioning/Enumeration

How many ways can one distribute A) 15 Balls into 3 bags. Both bag and balls are distinct (labelled) and each bag must contain at least one ball. B) 10 balls into 3 bags. again both bag and balls ...
0
votes
1answer
37 views

Number of k-permutations that have odd number of an element

I want to find a recurrence relation $h_k$ for the number of k-permutations of $\{\infty a,\infty b, \infty c, \infty d \}$ that have an odd number of a's. I let $h_0=0$ because there is no odd ...
1
vote
0answers
20 views

On Special Deviations of a Score Sequence

Can anyone help me to my problem? First of all, I will introduce the definition of deviation sequence, and special deviations. Let $<S_1,...,S_n>$ be any sequence of integers. The ...
2
votes
2answers
46 views

$S_n=Z_n$? Arithmetic progression.

$S_n$ is the sum of the first "n" numbers of the arithmetic progression "9,16,23..."; $Z_n$ is the sum of the first "n" numbers of the arithmetic progression "4035,4038,4041..." For what values ...
2
votes
2answers
293 views

Is there a way to simulate any $n$-sided die using a fixed set of die types for all $n$?

I am assuming that we can increase the number of dice based on $n$, but they have to be $k$-sided, $k\ge3$. When I say die types, I mean that we are allowed to use non-standard dice such as ...
1
vote
2answers
121 views

Pizza Topping combinations

I run a pizza joint in Seattle, USA, and would love to know how many different combinations of pie we can create. We have: 23 toppings 12 "house" pizzas 2 sizes (medium and large) two different ...
1
vote
1answer
149 views

If $|A| > \frac{|G|}{2} $ then $AA = G $

I'v found this proposition. If $G$ is a finite group , $ A \subset G $ a subset and $|A| > \frac{|G|}{2} $ then $AA = G $. Why this is true ?
1
vote
1answer
31 views

Arrangements and Selections with Repetitions

How many positive integer solutions are there to the equation $x+y+z = 17$? Can someone give me a hint ?
1
vote
1answer
284 views

Find total perfect combinations

Suppose we are given N numbers and a value K. Now we can interchange the positions of numbers to form different combinations, where if there are two same numbers then their arrangments will be ...
1
vote
1answer
36 views

Pigeon hole principle question with square area

A square one inch wide and one inch in length can be cut into 3 equal parts. Show that there is one of the three parts which contains 2 points at a distance of a least one. I know the square has an ...
0
votes
1answer
117 views

need help on simple probability question

I am trying to understand the question: An urn contains $n$ red and $m$ blue balls. They are withdrawn one at a time until a total of $r$($r \leq n$) red balls have been withdrawn. Find the ...
3
votes
4answers
255 views

Choosing books on a bookshelf where no two are consecutive

I'm going through Cohen's Basic Techniques of Combinatorial Theory and I am stuck on this problem: There are 24 volumes of an Encyclopedia on a bookshelf. In how many ways can 5 of these books be ...
5
votes
1answer
115 views

Intersection of lines on a plane

Suppose we have n lines on a plane such that there are $k_2$ points where two lines intersect, $k_3$ points where three lines intersect, ... , $k_n$ points where n lines intersect. How many segments ...
0
votes
0answers
23 views

Let $W_1(r,m,n)$ denote the number of partitions of n into m parts ,each larger than 1, with exactly r odd parts,each distinct.

Let $W_1(r,m,n)$ denote the number of partitions of n into m parts ,each larger than 1, with exactly r odd parts,each distinct. Let $W_2(r,m,n)$ denote the number of partitions of n with $2m$ as ...
2
votes
1answer
32 views

A relation between two enumeration problems

It's easy to see the number of non-negative solution of the equation $\sum_{k=1}^nx_k=r$ (each $x_k$ is an integer) and the number of sequence $1\leq u_1\leq\cdots\leq u_r\leq n$ are equal: both equal ...
0
votes
1answer
25 views

Let $P_1(r;n)$ denote the number of partitions of n into parts that are either even and not congruent to 4r-2(mod 4r)

Let $P_1(r;n)$ denote the number of partitions of n into parts that are either even and not congruent to 4r-2(mod 4r) or odd and congruent to 2r-1 or 4r-1(mod 4r). Let $P_2(r;n)$ denote the number of ...
1
vote
1answer
60 views

Finding Required Permutation

I have numbers from $1$..$n$. I want to find number of permutation from all $n!$ permutation where the numbers have following arrangement. $L$ $G$ $L$ $G$ $L$ or $G$ $L$ $G$ $L$ $G$. Where L means ...
1
vote
1answer
100 views

Delete Some Numbers

Given an array that consist of $n$ integers $a_1, a_2,\ldots, a_n$. Now I want to delete some(possible none, but not all) elements from the array, such that arithmetical mean of all remaining numbers ...
1
vote
1answer
50 views

If no circuit then unique vertex basis

Show the vertex basis in a directed graph is unique if there is no sequence of directed edges that forms a circuit in the graph. Is this right? Or I should provide more explanation Let A and B be ...
1
vote
1answer
42 views

Intuition for this explicit formula for the number of ways of putting N labeled balls in K unlabeled boxes?

In its article on "Stirling numbers of the second kind", Wikipedia gives this formula for $S(n, k)$ -- the number of ways of putting $n$ distinct balls into $k$ boxes (where the boxes aren't ...
1
vote
1answer
24 views

Recurrence Relations for Password question

I'm having a problem with figuring out a recurrence relation for the following question: Passwords are strings of upper case letters and can only contain even number of "X" with 0 being an even ...
6
votes
5answers
138 views

Combination proof for $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}$

How can I show that let $n$ and $k$ be integers. $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}$ It seems a bit confusing to me on the left hand side. You have a set of $n$ people on a team and you ...
3
votes
3answers
343 views

Give a combinatorial proof

I came across the following problem in a book: Give a combinatorial proof of $$ {n \choose 0} + {n \choose 2} + {n \choose 4} + \, \, ... \, = {n \choose 1} + {n \choose 3} + {n \choose 5} + \, \, ...
5
votes
1answer
83 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
2
votes
1answer
74 views

Combinatorics on letters

How many "words" of length n is it possible to create from {a,b,c,d} such that a and b are never next to each other?
4
votes
1answer
131 views

Math and chess question!

Given a $6\times6$ chess board with $13$ marked squares, can you always place three mutually non-attacking rooks on the marked squares? If so, how can this be proven?
1
vote
2answers
66 views

Permutation/Combination Question

A three digit number is to be formed by using the digit from 1 to 9 without repetition, find the number of three digit numbers that can be formed if the units digit is an odd number, the hundreds ...
1
vote
1answer
139 views

Calculate Number of ways to make the grid

We wish to tile a grid of size Nx2 with rectangles (dominoes) of 2x1 (in either orientation).For given N I need to find the number of different ways to tile the grid. EXAMPLE : For N=1 answer is 1 ...
0
votes
0answers
35 views

A bijective function

Consider $D_2 = \{(0,0), (0,1), (0,2), (1,0), (1,1), (2,0) \}$ and the bijective function $f_2:D_2 \rightarrow D_2$ defined by \begin{equation*} \left\{ \begin{array}{l} (0,0) \rightarrow (2,0) \\ ...
5
votes
2answers
178 views

Probability that 2 appears at an earlier position than any other even number in a permutation of 1-20

Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1,2,3,...,20. What is the probability that 2 appears at an earlier position than any other even number in the ...
2
votes
1answer
42 views

Relabelling players in a tournament

BdMO 2014 $n$ players take part in a chess tournament where each player plays with all others only once and the only outcomes of the games are win and loss.Prove that it is possible,after the ...
2
votes
2answers
55 views

What is the correct way to think about this yet another balls/boxes problem?

How would you do the following problem: Suppose that $n$ balls are placed at random into $n$ boxes. Find the probability that there is exactly one empty box. I mentally pictured $n$ boxes being ...
4
votes
1answer
179 views

combinatorial optimization? What is the name of this problem and where can I find material for studying it?

I'm looking for material to study the following problem, Suppose I have $N$ numbers, and I know that the sum of $M$ of those number equals $k$. The goal is to find all combinations of cardinality (is ...
1
vote
1answer
130 views

Yahtzee Bar Game

A bar near where I work has a game where you pay $5$ dollars which gets you two chances of rolling $5$ dice and if roll results in all of the dice having the same number you win the running pot, ...
1
vote
1answer
82 views

Clique Theorem from Graph Theory

I am trying to determine an interesting problem here. I want to determine if I have a graph of N vertices, for different subgraphs of k vertices (where k <= N), how many edges can I add before the ...
5
votes
4answers
119 views

Phone number algorithm

If a phone number were turned into an equation, how difficult would it be to reverse engineer the original phone number ? How many potential (10 digit, North American) phone numbers could a solution ...
0
votes
0answers
55 views

Number of monotone functions between finite partially ordered sets

How many monotone functions are there between the set $P(E)$ (the set of all subsets of $E$) and $P(F)$ if $\operatorname{card}(E)=n$ and $\operatorname{card}(F)=m$?
0
votes
1answer
24 views

Probability of duplicate selections across sets (Combinatorics)?

Suppose you have 100 distinct video games and you have 50 distinct friends, each of which you must offer 3 video games from your collection of 100. Each of your 50 friends must select one of the three ...
1
vote
2answers
91 views

Discrete Math: Counting Problem with balls

A bowl contains 10 red balls and 10 blue balls.A woman selects balls at random without looking at them. a) How many balls must she select to be sure of having at least three balls of the same ...
0
votes
0answers
58 views

Matheletics '13 challenges

I was trying to solve the challenges proposed on Matheletics '13. I'm having trouble solving Hockey Classics, Special Arrangement and Permutation. Can anyone point out the idea I can't see, pls?
0
votes
2answers
162 views

Combination proof $\sum_{k=1}^nk\binom{n}{k}^2=n\binom{2n-1}{n-1}$

How can I show that k and n being integers $\sum_{k=1}^nk\dbinom{n}{k}^2=n\dbinom{2n-1}{n-1}$ the following is true using a combination proof. I am not sure how to do this. on the right hand side ...
2
votes
0answers
85 views

Number of permutations when combining two sets?

I have two sets $\{a_{1},\ldots,a_{K}\}$ and $\{b_{1},\ldots,b_{L}\}$, where I know that $a_{1} \leq a_{2} \leq \cdots \leq a_{K}$ and $b_{1} \leq b_{2} \leq \cdots \leq b_{L}$, but do not know the ...
3
votes
1answer
95 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
2
votes
1answer
50 views

Counting rstricted perfect matchings

It is known that counting perfect matchings in bipartite graphs is $\#P$-hard. Given complete bipartite graph $G(U \cup V, E)$ where $|U|=|V|=n$ and a perfect matching $M \subset E$, what is the ...
2
votes
2answers
54 views

Number of ways to pass balls such that whoever starts with the ball ends with the ball

$4$ basketball players play a game of ball passing, with either one of them holding the ball at the start. In each turn, the ball is passed from whoever is currently holding the ball to either of the ...
0
votes
1answer
86 views

Number of permutations for n elements with different probabilities

I'm studying the paper Database-friendly random projections: Johnson-Lindenstrauss with binary coins by D. Achlioptas and can't manage to work out the total number of permutations with repetitions in ...
0
votes
1answer
84 views

How can I show that this equation is true?

Is it possible to show that for $m \ge 1$, I can always find two positive integers $n$ and $c$ to satisfy the following formula? $$\frac{{n+c\choose 2}}{{n\choose 2}+n{c+1\choose ...
2
votes
0answers
93 views

How to prove this combinatorial identity

I am wondering how to prove the following identity: $$\sum_{k=0}^r {r-k \choose m} {s \choose k-t} (-1)^{k-t} = {r-t-s \choose r-t-m}$$ It seems that I can negating the upper index of ${s \choose k-t} ...
2
votes
1answer
79 views

Are these combinations and permutations correct?

I wanted to know if I did these 3 questions correctly: There are 100 distinct people in line. How many arrangements are there? Ans: Combination - 100! There are 30 distinct objects. How many ...