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)

2
votes
0answers
23 views

Proving a tricky combinatorial identity

How to attack this kinds of problem? I am hoping that there will some kind of shortcuts to calculate this. EDIT: As i see the numerator is $n \choose k$ and the denominator is ${2n-1} \choose ...
3
votes
0answers
24 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
2answers
25 views

Possible 4 character passwords involving a letter and a digit.

A password consists of 4 characters, each of which is either a digit or a letter of the alphabet. Each password must contain at least ONE digit and AT LEAST ONE letter. How many different such ...
0
votes
2answers
21 views

Probability of an event happening while another doesn't

Say you have a bag with $5$ numbers $(1,2,3,4,5)$. What is the probability that I will draw a $1$ if I draw $3$ times (no replacement)? What is the probability that I will draw a $1$ if I draw 3 ...
0
votes
0answers
12 views

dimension of vector space $\frac{\langle e_{ab_1\ldots b_p}\rangle}{\langle \sum_{1\leq i\leq p}e_{ab_1\ldots \widehat{b_i}\ldots b_pc}\rangle}$

Let $p$ be a prime and $n\!\in\!\mathbb{N}$. What is the dimension of the $\mathbb{Z}_p$-module $$V_{p,n}=\frac{\langle e_{ab_1\ldots b_p};\: 1\leq a<b_1<\ldots<b_p\leq n\rangle}{\langle ...
0
votes
0answers
20 views

Presentation of 2 images in a random but counterbalanced way

Problem: For 18 trials randomly a ‘left’ labeled image or ‘right’ labeled image is shown. The first 9 trials should contain the opposite number of left images as the last 9 (a.k.a. counterbalance). ...
0
votes
1answer
23 views

How many different teams can be created between two groups?

If a company has 8 painters and 12 electricians. How many different teams can be created with 1 painter and 1 electrician? I know that the number of ways a team can be made is: $ {8 \choose 1} * ...
2
votes
3answers
211 views

Probability of no ace in a 6 card hand, given 4 are not aces.

A player is dealt six cards out of a normal deck of cards. He looks at the first four and notices there is no ace among them. What is the probability that he does not have an ace at all. This sounds ...
1
vote
1answer
32 views

Find the chance that $a^3 + b^3 \equiv 0 (\mod 3)$

We are given set of integer numbers $\{1,2, \dots N\}$. $N \ge 3$ Then perform a drawing with replacement of two elements $a$ and $b$. Problem is to find the probability of following statement holding ...
-2
votes
1answer
18 views

number of possible outcomes in a license plate with conditions [on hold]

howmany license plates can me made when a) first two letters are different and the rest different digits e.g. DA3457 b) two letters in alphabetical order and the digits increasing e.g. CD1234
0
votes
2answers
17 views

Story proof for choosing a committee

Give a story proof that $\sum_{k=0}^n k{n\choose k}^2 = {n{2n-1\choose n-1}}$ Consider choosing a committee of size n from two groups of size n each , where only one of the two groups has people ...
4
votes
3answers
48 views

possible pizza orders

You are ordering two pizzas. A pizza can be small, medium, large, or extra large, with any combination of 8 possible toppings (getting no toppings is allowed, as is gettting all 8). How many ...
1
vote
1answer
22 views

Choosing schedule for courses

To fulfill the requirements for a certain degree, a student can choose to take any 8 out of a list of 20 courses, with the constraint that at least 1 of the 8 courses must be a statistics ...
2
votes
1answer
35 views

A problem on distributing indistinguishable balls into 10 different groups such that…

I got this problem which I am stuck at for an hour and half: Suppose that we have an infinite number of indistinguishable balls and we need to distribute them into 10 different groups such that $ ...
0
votes
2answers
13 views

How many different pairs can I have from two groups?

A company has 8 painters and 12 electricians, and teams can be created of one painter and one electrician. How many different teams can be created? My best guess is: $ {8 \choose 1} * {12 ...
1
vote
3answers
54 views

Olympic elementary combinatorics problem

This is a problem taken from the regional selections of the Italian mathematical olympiads: A knight is placed on the bottom left corner of a $ 3\times3 $ chess board. In how many ways can you move ...
1
vote
4answers
33 views

Select one or zero elements from a set

I am far from a mathematician. Still. I want to formally express that only 0 or 1 element of a series of sets (1...n) is selectet to form a new set. Example: I have three sets $S_1 = \{1,2,3\}$, $S_2 ...
2
votes
0answers
57 views

Why does $n$ always divide this sum?

If we assume $m=p_1^{a_1}\cdots p_s^{a_s}, n=p_1^{b_1}\cdots p_s^{b_s}p_{s+1}^{b_{s+1}}\cdots p_t^{b_t}$, where $0<a_i<b_j$, $p_j$ are different primes($i=1,\cdots,s; j=1,\cdots, t$). Then ...
3
votes
0answers
37 views

In how many ways 3 persons can solve N problems.

There are $3$ friends $(A,B,C)$ preparing for math exam. There are $N$ problems to solve in $N$ minutes. It is given that: Each problem will take $1$ minute to solve. So all $N$ problems will be ...
2
votes
3answers
30 views

question on morse code

The morse code is made up of marks called dots and dashes."Q", for example is (--,--).Is it possible to make up such a code so that every letter of the alphabet is represented by at most three marks? ...
1
vote
0answers
34 views

Proving that elementary row operations are preserved after multiplication

If $E$ is an elementary $n \times n$-matrix, show that if $A$ is any $n\times n$-matrix, then $EA$ is a matrix obtained by carrying out a single elementary row operation on $A$, and that $AE$ is a ...
1
vote
0answers
13 views

In a best-of-7 match possibilities for 7th game win

In a best-of-7 match A vs B, where the match will end as soon as either player has 4 points. How many possible outcomes for the individual games are there, such that the match lasts for 7 games and A ...
1
vote
2answers
26 views

pairing possibilities in chess game

There are 20 people at a chess club on a certain day. They each find opponents and start playing. How many possibilities are there for how they are matched up, assuming that in each game it does ...
1
vote
1answer
23 views

Number of arrangements of the word “MAMMAL” where M is not together

This is in reference to this question. Letter Arrangement with Permutations _A_A_L_ IF M is not together, then M can go into 4 distinct places (denoted by the underscores above). So the number of ...
-3
votes
1answer
39 views

Probability that a monkey at a type writer types “hamlet” [duplicate]

A monkey types each of the 26 letters of the alphabet exactly one time. What is the probability that the world "hamlet" appears somewhere in the string of letters?
0
votes
1answer
14 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
1
vote
1answer
24 views

What is the probability of not rolling any given number on 10 rolls of a die?

In other words, ALL combinations which don't contain at least one of the number from 1-6 would count. So for example... 5, 2, 3, 3, 4, 1, 5, 5, 3, 1 would be counted because there is no 6 Also 5, ...
-3
votes
1answer
63 views

Better Explanation for an already posted question [duplicate]

Can anyone explain why in this question the answer is 5! * 2! * 10P3? I understand the 5! and 2! but for 10P3 the first thing I thought of was 3! Thanks.
0
votes
0answers
8 views

Upper bound for graphs with no k-cliques

We know that for random graphs $G(n,p)$ we have: $P[X=0]\leq e^{-\Theta(E[X])}$ where $X$ denotes the number of k-cliques in the random graph. Can this fact be used to say anything about the number of ...
-2
votes
1answer
33 views

Combinatorial Argument Proof

Prove: $c(40,5) = c(17,5) + c(17,4) + c(23,1) +...+ c(23,5)$ where c is the binomial coefficient. Can I use a combinatorial argument to prove?
1
vote
1answer
13 views

Distributing dimes to 2 groups of people such that each member of one group gets at least one

I have a study question that I have the answer for, but I just can't understand how or why it is the answer. The question is: $n$ dimes are distributed to $y$ young people and $o$ old people. Every ...
0
votes
0answers
21 views

Point of most theoretical potential moves in a game of Scrabble

I was recently playing a game of scrabble with a friend and the point difference all but ensured that I was going to lose (100+ points with one rack of tiles left, and no more in the "pot" and I ...
1
vote
1answer
17 views

Power set ordered by sum and Dijkstra shortest path

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing ...
0
votes
1answer
15 views

Number of graphs with M edges that does not contain K-clique

If we consider the space of graphs $G(n,M)$ with $n$ vertices and $M$ denotes the number of edges. Is there any way of upper bounding the number of graphs in this space that does not contain any ...
1
vote
1answer
18 views

Number of integer coefficient multilinear polynomials

I am looking for an expression for number of multilinear polynomials of degree atmost $t$ in $n$ variables with integer coefficients having coefficient size atmost $|B|$. Is ...
1
vote
1answer
17 views

possible outcomes for round-robin tennis tournament

A round-robin tournament is being held with n tennis players; this means that every player will play against every other player exactly once. How many possible outcomes are there for the tournament? ...
0
votes
1answer
14 views

Counting - possible schedules for dinner

Fred is planning to go out to dinner each night of a certain week, Monday through Friday, with each dinner being at one of his ten favorite restaurants. How many possibilities are there for Fred's ...
0
votes
2answers
20 views

Find a probability of $L_\sigma(A) = F_\sigma(B)$

We are given set $\{1, 2, \dots n\}$ and some random permutation $\sigma$ of that set. Sets $A, B \subseteq \{1, 2, \dots n\}$ and |$A \cap B| = 1$ and $|A| = |B| = k$ We define $L_\sigma(A)$ as the ...
1
vote
1answer
41 views

Maximal number of colours in a palette that allows for fewer than 500 mixtures

An artist is planning on mixing together any number of different colours from her palette. A mixture results as long as the artist combines at least two colours. If the number of possible mixtures is ...
0
votes
0answers
45 views

how to prove the expression $\sum_{k=0}^n \binom{m}{k} \binom{n+k}{m}$? [on hold]

(m,n) is a dot with x=m, y=n. d(m,n) is the number of different paths from (0,0) to that dot. how to prove that d(m,n) = $\sum_{k=0}^n \binom{m}{k} \binom{n+k}{m}$ if you have a combination story or ...
0
votes
0answers
20 views

Number of sock combinations with limited information

Suppose in your sock drawer of 14 socks there are 5 different colors and 3 different lengths present. One day, you decide you want to wear two socks that have both different colors and different ...
0
votes
0answers
25 views

questions related to derangement

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...
0
votes
2answers
28 views

Combinatorics (discrete math course) help

problem 1: you have 4 balls with different weights and 6 drawers stacked on top of each other. how many ways are there to organize the balls such that the top drawer will have exactly 1 ball and the ...
1
vote
0answers
46 views

Binomial coefficient in closed form problem

Is anybody to give a insight, please? $8.9$. Let $\ell$ be an even positive integer. Express $$\sum_{k=0}^n\sum_{i=0}^\ell(-1)^i\binom{n}k^2\binom{2k}i\binom{2n-2k}{\ell-i}$$ in closed form. ...
-1
votes
2answers
22 views

How many groups consisting of 4 members can be made with b,c,d if they can be repeated?

How many groups of b,c and d can I make if they can be repeated? Eg. {bbcd},{bbcc},{cdcc},{cccc} etc. Pls specify the no.of b's in a specific kind of group such as {bbdc} has two b's
5
votes
2answers
905 views

Placing 5 pieces on a 5x5 grid with no main diagonal

A 5x5 grid is missing one of its main diagonals. In how many ways can we place 5 pieces on the grid such that no two pieces share a row or column?
0
votes
1answer
24 views

How prove this $n$ smaller cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube

Question: Show that: for any postive integer $n(n\ge 2)$, there are $n$ cubes ( length is $1,2,3,\cdots,n$) can't Mosaic a big cube This is answer it is clear when $n=2,3$. .But I can't ...
0
votes
1answer
16 views

Please help. (SDR) [on hold]

Let A=(A1,A2,......,An) be a family of sets with an SDR. Let x be an element of A1. Prove that there is an SDR containing x, but show by example that it may not be possible to find an SDR in which x ...
0
votes
2answers
39 views

How to find sum of $n$ terms of $3C_1+7C_2+11C_3+\cdots$

let $n\in \mathbb N$ be fixed and let $0\leq k\leq n$ Let $C_k$ denote number of ways of choosing $k$ objects from n distinct objects. How to find sum of $n$ terms of $$3C_1+7C_2+11C_3+\cdots$$ I ...
0
votes
1answer
20 views

How to determine whether the following sets are countable:

How to determine whether the following sets are countable: i.collection of all finite subsets of $\mathbb N$ ii.the collection of all functions from $\mathbb N$ to $\mathbb R$ iii.collection of all ...