Tagged Questions

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
0answers
4 views

Pruning permutations of a sequence

Given a sequence $S$ with $n > 3$ elements, there will be exactly $2$ subsequences of length $n-1$. For each subsequence $A, B$, take all permutations of each. For example: $S = 1,2,3,4\\ A_p = ...
0
votes
1answer
12 views

Permutation of $n$ women and $m$ men, in a line, where the women are pissed off with each other

So the $n$ women can't sit next to each other. So in a straight line how many ways can they be seated? I know this problem is partitioning distinct balls in $n+1$ partitions, out of which $n-1$ of ...
0
votes
0answers
7 views

Least graph containing every connected graph with $m$ nodes as an induced subgraph

What is the smallest graph that contains every connected graph with $m$ nodes as an induced subgraph ? every connected graph with at most $m$ nodes as an induced subgraph ? If the graph has $n$ ...
4
votes
4answers
40 views

Even Number cards?

There are $15$ cards on a table, marked with an integer $1$ from to $15$ . How many ways can I take cards such that the sum of the numbers on the cards is even? Please help me?
0
votes
1answer
12 views

how to calculate these intersections without having to count all combinations

We have the following sets: $X= {(a,b,c,d) ∈S: b< c < d},$ $Y= {(a,b,c,d) ∈S: a< c < d},$ $Z= {(a,b,c,d) ∈S: a< b < d},$ $F= {(a,b,c,d) ∈S: a< b < c},$ Where each of ...
0
votes
1answer
14 views

Questions about k elements subset of an n elements set.

I need to prove by induction that the number of 2-elements subset of an n elements set is $\frac{n(n-1)}{2}$ I am stuck on where I should start from and how should I solve this. I am guessing that ...
1
vote
2answers
34 views

Why is the arrangement of $n$ things round a circular table is $(n - 1)!$ & not $n!$ ?

Suppose there are $n$ seats round a table . We have to find the number of circular permutations of $n$ different men taken all at a time when clockwise & anti-clockwise orders are different. ...
1
vote
1answer
28 views

How many ways to make a $3$ digits even number

How many ways to make a $3$ digits even number with only $2,3,5,6,7$ . And no repeated use of digit. I think I did something like for the first digit you have $5$ choices, for second digit $4$ ...
2
votes
3answers
39 views

Probability of $2$ boys in a family.

In a family there are 3 children with minimum $1$ boy.What is the probability there are exactly $2$ boys in the family? I think I have to use combinatorics to solve this problem. I have solved some ...
1
vote
1answer
22 views

Find the number of possible 4x4 matrices such that :

Find the number of possible 4x4 matrices such that : 1) each row has two 0's and two 1's 2) each column has two 0's and two 1's example : $$\large \begin{pmatrix} ...
2
votes
0answers
19 views

limit of double binomial sum

Prove that $$\lim_{\max(M,N) \to \infty} \frac{\sum_{i=0}^{M-1} \sum_{j=0}^{N-1} p^{i} (1-p)^{j} {i+j \choose i}}{\min (\frac{M}{p}, \frac{N}{1-p})} = 1 $$ where $0<p<1$ and $M, N$ are ...
2
votes
1answer
25 views

Collection of subsets with adding one element property

Let $\mathcal{F}$ be a collection of subsets of $\{1,2,\ldots,n\}$ such that for any set $A\in\mathcal{F}$, there exists $B\not\in \mathcal{F}$ such that $A\subset B\subseteq\{1,2,\ldots,n\}$ and ...
-3
votes
0answers
25 views

How to write recurrence relations from a verbal description(Question from Oxford math admission test)? [on hold]

Questions are interesting because they only require primary math skill. They have general patterns that developing the problem from specific to general. The 5th and 7th questions in the paper(linked) ...
3
votes
2answers
28 views

Prove that sum $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}$ is zero

I try to prove that $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}=0.$ I calculated in Maple for n=1..100. $\sum_{k=1}^n {(-1)^k {{n-1} \choose {k-1}} (2n-k-1) 2^k}=-2 \sum_{k=0}^{n-1} ...
1
vote
1answer
19 views

A Question about Shuffling a Deck of Cards

Currently I am following Sheldon Ross' A first course in probability. And I got stuck in this question: Consider the following technique for shuffling a deck of $n$ cards: For any initial ordering of ...
0
votes
0answers
50 views

Summation of product of two binomial probabilities

I am trying to find the closed form solution for this formula but got stuck: $\displaystyle\sum_{k=m}^{\infty}{\binom{k}{m}\cdot2^{-k}}$ Actually I try to compute the values of summation of product ...
6
votes
2answers
59 views

Every $3\times 3$ square has even number of painted cells

Given a $1000\times 1000$ board. We paint some cells (at least one) so that in every $3\times 3$ square, an even number of cells are painted. What is the minimum number of painted cells? One way to ...
2
votes
2answers
35 views

Binomial theorem - a special case. Calculate sums.

I have just started my first course in discrete math and have some reflections. If I want to calculate the sum ${n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+...+{n \choose n-1}x^{n-1}+{n \choose ...
0
votes
2answers
41 views

Is there a simple graph with an odd number of automorphisms (except $1$ and $3$)?

The simple graphs upto $11$ vertices do not have $5,7,9,...$ automorphisms, in other words, the only odd numbers appearing are $1$ and $3$. Is this true for all graphs ? Formulated as an ...
7
votes
0answers
110 views

Math puzzle: 10 digit strings generations

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how ...
0
votes
0answers
25 views

Probability that two doubletons are distinct in random graph

Let $G$ be a random graph with $K$ left nodes and $M$ right nodes. We have the following definition Definition: Two right nodes are called distinct if they are not connected to the same two left ...
2
votes
2answers
37 views

Probability of a drawing a specific suit and a specific color

After drawing 5 cards from a standard 52 card deck, what is the probability that the hand will contain: 1 diamond 1 spade Any other red card (diamond or heart) My first approach was to use a ...
0
votes
1answer
28 views

Number of ways of choosing identical balls

Suppose we are given a bag of $n$ identical red balls, what is the number of ways of choosing $3$ red balls from the bag? I know the answer is $$ \binom n3 $$ but isn't there just one way of choosing ...
0
votes
2answers
33 views

How many $6$-lentgh increasing sequence are there from $1$ to $49$?

I have to figure out a way to count how many sequences are there s.t: My alphabet is $1$ up to $49$. Each number that is chosen, is chosen only once. The sequence is $6$ digits long. The sequence is ...
1
vote
1answer
17 views

Explicit probability for vertical 2D percolation

We have a $n \times n$ array of open and blocked sites. Some fluid falls from the top. We call a site "full" if it has fluid. Then the sites in the top row will be full as long as they are open. ...
2
votes
2answers
20 views

Palindromic Hypotenuses?

What is the largest seven-digit palindrome which can be expressed as the sum of two perfect squares? I tried Java but couldn't get the right answer, and unfortunately OEIS ends at around 5 digits in. ...
-5
votes
0answers
34 views

coefficient $x^{10}$ in expansion of $(1 + x^5 + x^{10} + x^{15} +· · · )^3$ [on hold]

How to find the coefficient of $x^{10}$ in expansion of following expression $$(1 + x^5 + x^{10} + x^{15} +· · · )^3$$
2
votes
3answers
57 views

Posible combinations of available rooms

I have $x$ people to divide over different type of rooms. Possible rooms: $1$ person bedroom normal view; $1$ person bedroom sea view; $2$ person bedroom For $x = 4$ Possible combinations are ...
3
votes
4answers
132 views

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? ...
1
vote
2answers
37 views

Combinatorial proof of an identity related to Derangements

Consider the following identity regarding derangements: $d(n) = n*d(n-1)+(-1)^n$, where d(n) denotes the number of derangements of the numbers 1..n. It's easy to prove the identity using this fact ...
1
vote
0answers
19 views

How to calculate the number of solutions for the vehicle routing problem (VRP)?

The vehicle routing problem is a combinatorical optimization problem, looking for the optimal solution to serve a number of customers by a number of vehicles, starting from a central depot. Each ...
0
votes
2answers
57 views

Can we express the following ordinary generating function?

I wish to express the following power series $$ \sum_{k \ge 0} \binom{n-k}{m} x^k$$ where $n,m$ are positive integer such that $0< m \le n$
1
vote
0answers
10 views

Cumulants in diagrammatics (without physics or probability theory)

Formal cumulants ($\kappa_n$) and the associated moments ($\mu_n^{'}$) are related through log and exp transformations of exponential generating functions (e.g.f.): $$\exp \left [ \sum_{n=1}^{\infty ...
7
votes
3answers
630 views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...
1
vote
2answers
31 views

finding numbers to make both sides equal

Call a triple-x number an integer $k$ such that $k=x(x+1)(x+2)$ where $x \in Z$. How many triple-x numbers are there between 0 and 100,000? I thought by doing $8!$ and $9!$ would work to see how ...
1
vote
1answer
36 views

Probability of Game Series

A world series is a best of $7$ series between team $A$ and team $B.$ It takes $4$ wins to win the series. How many ways can a team win the World Series? I said: Suppose that a World Series is ...
0
votes
2answers
31 views

Palindromes less than a number

How many positive palindromes are less than $1,000,000,000$? I think one way to do this is to count palindromes with a fixed number of digits, and take the sum of these values from $1$ digit to ...
4
votes
2answers
58 views

Least possible number of squares with odd side length

An $n\times(n+3)$ rectangular grid ($n>10$) is cut into some squares, with all cuts being along the grid lines. What is the least possible number of squares with odd side length? [Source: Russian ...
5
votes
1answer
65 views

permutations of $\{1,2,\cdots , n \}$ with some restriction

Problem: I am trying to calculate the number of permutations $f(n)$ of $\{1,2,\cdots , n \}$ such that there aren't any adjacent digits in which the right one is greater than the left one by exactly 1 ...
3
votes
2answers
68 views

Who is the last person?

twenty five people are standing in a circle. starting with person 1, they count off from 1 to 7 and then start over with 1. each person who says "7" drops out of the circle. who is the last person ...
0
votes
1answer
23 views

Prove that $d_n>(n-1)!$ for all $n\geq4$.

Problem: Prove that $d_n>(n-1)!$ for all $n\geq4$. $d_n$comes from the derangement where $$d_n=(n-1)(d_{n-1}+d_{n-2})=n!\sum_{m=0}^{n}\dfrac{(-1)^m}{m!}=n!\Bigg(1-\frac{1}{1!}+\frac{1}{2!}-\cdots ...
0
votes
1answer
12 views

Ways of forming a committee so that a particular man is always included

In how many ways can a committee of 4 be selected from nine men so as to always include a particular man? I thought 9 nCr3. as we only calculate to choose for 3 men out of the nine total. How am I ...
-1
votes
1answer
64 views

Knowing People Proof [on hold]

If I choose any four students among a class, at least one of the four knows all of the other three. Prove that there must be a student who knows everybody in the class.
1
vote
2answers
31 views

Combinations Question regarding placement in multiple teams with restrictions?

I've been having trouble with the following question: Nine players are to be divided into two teams of four, and one umpire. If two particular people cannot be on the same team, how many different ...
-1
votes
1answer
39 views

Advanced Counting [on hold]

1) 16 kids. How many ways to distribute toys: 8 dolls, 4 cars, 3 balls, 1 horse 2)Player 1 is playing 4 games of tic-tac-toe against two other players. He is tracking his record. How many different ...
2
votes
1answer
23 views

Summing up and Dirichlet's principle.

We are given $n$ integers. Using Dirichlet principle to prove that among them there is a number divisible by $n$ or there are numbers whose sum is divisible by $n$. I think that we should consider ...
0
votes
1answer
21 views

Parity of number of $0-1$ matrices with no zero rows

Let $k$ be a positive integer. What is the formula for the number of $0-1$ matrices of size $k\times k$ such that no rows of the matrices are all $0$s (note columns can be all $0$s)? When is this ...
1
vote
0answers
13 views

Expressing an arbitrary natural number as the difference of squarefree ones [duplicate]

Is it true that $\forall n \in \mathbb{N}, \exists x, y \in \mathbb{N}: x,y$ are squarefree, & $n = x-y$? I think so, but I am not sure that I am quite proving it. Here is my line of thought: ...
0
votes
1answer
29 views

Use induction and Pascal’s identity to prove that if $n > 1$, then $C(n, 1) = C(n, n-1) = n$

So, I did the base case and I get: BASE CASE $C(2, 1) = C(2,1) = 2$. $2 = 2 = 2$. Base case holds true. Inductive Step This is where I'm not exactly sure what to do, using Pascal's rule. I have ...
0
votes
1answer
16 views

Does order matter in multinomial distribution?

I am confused if order matters in multinomial distribution.. As far as I understand order does matter and if we want to eliminate matter of an order we need to multiply $\frac {n!}{r_1! \cdot r_2! ...