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
12 views

Combinatorial Problem: How many ordered pairs of ordered pairs do exist?

Suppose we have a universe of $n$ numbers. How many ordered pairs of ordered pairs, that is, $((a,b), (c,d))$ do exist such that $(a,b)\neq (c,d)$ but $a=c$, or $b=d$, or $a=d$ and $b=c$. I thought ...
1
vote
0answers
15 views

Sum of powers of a number divisible by other?

I need to find the probability that $7^m+7^n$ is divisible by $5$ where $m,n\in[1,100]$. I noticed that if the remainder when m and n are divided by 7 differs by two the last digit is zero. So I did ...
-1
votes
2answers
18 views

consider a class of 9 students. The instructor wants to divide the students into three disctinct study groups

Consider a class of 9 students. The instructior wants to divide the students into three distinct study groups. Count the number of ways the instructor can accomplish this, if there are. a) Exactly ...
2
votes
3answers
52 views

Comparing probabilities of drawing balls of certain color, with and without replacement

Please read carefully how I solved this question: A bag contains 4 white 2 black 3 red balls. A ball is drawn from the bag 1-by-1. (i) Find the probability that $5^{th}$ ball is red. Consider ...
1
vote
1answer
14 views

Can the probability of a trump poverty be calculated without making case distinctions?

The card game Doppelkopf is played with four players. Every player receives 12 of the 48 cards. The 48 cards consist of 26 trump cards and 22 other. A trump poverty is what we call the scenario that a ...
1
vote
2answers
16 views

permutation;discrete structures review

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Consider a group of n people, let ...
3
votes
0answers
34 views

Intersection with even cardinality

For any natural $n \geq 2$ find the smallest integer $k$, such that from any $k$ different subsets of $\lbrace1,2, \dots, n \rbrace$ with even cardinality, exist at least two, with intersection ...
0
votes
0answers
24 views

Find the number of solutions of this inequation

Given any positive integer $n$, is it possible to find the number $N(n)$ of solutions $\{i,j\}$ being $i$ and $j$ positive integers satisfiying the next inequations? $n < i^2+j^2 < n + ...
1
vote
1answer
19 views

Counting Involving Two Different Sets

So I have two sets: C (the set of all capital letters) and D (the set of all single digits). Let's say ...
1
vote
1answer
36 views

Number of $q$-colorings of an $n\times n$ grid graph without adjacencies

Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color? A friend and I have been trying to find a ...
0
votes
2answers
28 views

games in a round-robin tournament

How many games are played in a round-robin tournament held with n tennis players where each of the players will play against every other player exactly once. The answer is $\frac{n(n-1)}{2}$. What ...
0
votes
0answers
36 views

How do I go with proving that the coefficient of each terms of $\prod^{k=n}_{1}{1-x^k}$ is either 1,-1 or 0?

How do I go with proving that the coefficient of each terms of $\prod^{n}_{k=1}({1-x^k})$ is either 1,-1 or 0 for n that is sufficiently large? Also, is there any pattern in terms of the 1,-1 and 0s?
2
votes
0answers
22 views

Arranging identical blue and red bottles such that there are no 2 red bottles next to each other

There are 10 identical blue bottles and 5 identical red bottles. How many ways are there to arrange the 15 bottles in a row such that no two red bottles are next to each other? My approach: If the 2 ...
4
votes
0answers
37 views

Combinatorial Interpretation of a Binomial Identity

The original post due to David Peterson is here. How to establish the following Binomal identity combinatorially: $$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = ...
0
votes
0answers
15 views

Plackett-Burman designs for screening experiments

i am looking for a method to investigate the relations between different factors in a experiment. So basically i am looking for a factorial design which fits my needs. I have 4 different lysing ...
0
votes
3answers
20 views

Number of positive integers between 1 and 2300 inclusive that are relatively prime to 700.

Find the number of positive integers between 1 and 2300 inclusive that are relatively prime to 700. I have no idea how to approach this question, honestly.
1
vote
0answers
14 views

higher moments of a r.v., combinatorical problem

I'm studying the book of Rick Durrett, I want to understand the proof of the Erdös Kac central limit theorem, so I also need to understand the Lindeberg-Feller theorem: for every $n \in \mathbb{N}$ ...
1
vote
1answer
20 views

Number of different arrangements of the letters A,B,C,D,E,F

How many different arrangements are there of the letters A,B,C,D,E,F in which (a) A and B are next to each other and C and D are also next to each other? (b) E is not the last letter? (c) A is before ...
0
votes
0answers
17 views

Solution of the recurrence relation of factorial.

Well, I have seen the Stirling's approximation for the upper bound of the function f(n)=n! but I want toknow the solving process of the recurrence relation T(n)=n*T(n-1) where T(1)=1
1
vote
0answers
16 views

Number of Dyck paths with k returns and b peaks

The number of Dyck paths from the origin to $(2n,0)$ which touch the $x$-axis $k+2$ times ($k$ internal touches) is given by $$\frac{k}{2n-k}{2n-k \choose n}.$$ The number of Dyck paths from the ...
0
votes
1answer
37 views

Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have. What I know: The maximum ...
4
votes
1answer
58 views

Prove $\sum_{k=0}^n k{n\choose k}^2 = {n{2n-1\choose n-1}}$ [duplicate]

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 ...
0
votes
2answers
21 views

Find the number of 17-digit binary sequences with more 0's than 1's.

Find the number of 17-digit binary sequences with more 0's than 1's. What I know: If there are more 0's than 1's, the cases I have to calculate for is 9 0's and 8 1's 10 0's and 7 1's 11 0's and ...
0
votes
1answer
27 views

Number of positive integer solutions

How many positive integer solutions of the equation: $x_1 + x_2 + \cdots + x_p = n$ where $x_1$ and $x_2$ are odd numbers and other $x_i$'s are even numbers ? Is there any theorm about such equation? ...
0
votes
1answer
9 views

prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6. My proof: By induction. For n=7, the number of edges is 21=$2 ...
0
votes
1answer
18 views

Approximating a binomial coefficient using Stirling's formula

I am working on a problem of modelling a rubber molecule as a one-dimensional chain consisting of $N=N_{+}+N_{-}$ links, where $N_{+}$ points in the positive $x$-direction a distance $a$ and $N_{-}$ ...
1
vote
3answers
19 views

Probability of rolling doubles from 5 dice

If I roll five dice, what is the probability that there is a matching pair among them? This is the way I thought about the problem. Let $X$ be the random variable describing the number of occurrences ...
0
votes
2answers
29 views

fibonnaci and lucas series technique

Well i have the following two problems involving fibonnaci sequences and lucas numbers, i know that they share the same technique, but i don't have clear the procedure: $$f_n = f_{n-1} + f_{n-2}: f_0 ...
4
votes
0answers
70 views

How to prove that a double sum is always an integer?

I have verified the following double sum is always an integer for $s$ up to $1000$ via Maple. But I can not prove it. Proofs, hints, or references are all welcome. Thanks! ...
3
votes
2answers
23 views

How many sequential partitions (defined inside) are there of numbers 1…n?

So, suppose $[n] = \{1,\cdots,n\}$. A partition of $[n]$ is just any division of $[n]$ into non-overlapping sets. Suppose instead of partition $[n]$ into sets I partitioned it into sequences. So ...
0
votes
2answers
33 views

Subsets of a power set.

How many subsets T of the power set of A contain at most 2 elements if the cardinality of A is n where n is a natural number ? The number of elements in power set A = 2^n. But i dont know how to ...
0
votes
1answer
26 views

Circular permutations problem with putting objects into circle

How many options do I have if I want to put red boxes and black boxes into circle so that no two black boxes are next to each other? I have 12 red boxes and 4 black boxes. Also all two red and black ...
0
votes
1answer
15 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
2answers
54 views

Computing $C_0^2+C_1^2+C_2^2+C_3^2+ \cdots +C_n^2$

If $C_k$ denotes binomial coefficient of choosing $k$ objects from a set of $n$ objects how to calculate this: $$C_0^2+C_1^2+C_2^2+C_3^2+\cdots +C_n^2$$
0
votes
1answer
35 views

Problem Solving Involving Permutation

Find the number of 6-digits number with no 3 consecutive number with same digits. Note that 0 might be the first number. I have tried to find the number with no pairs, 1 pairs, 2 pairs and 3 pairs. ...
2
votes
1answer
21 views

Counting Review; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
18 views

Counting Problem; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
0answers
18 views

How should i go about proving an expression of this kind?

Lets say i have a complete bell polynomial that is equal to a summation such that $$ B_n(d_1,d_2,\cdots,d_n) = \sum_{k=0}^{n}[g(x)^{-k} h(k)] $$ Where $d_n = \frac{d^n}{dx^n}[f(x)\ln(g(x)]$ and ...
0
votes
1answer
32 views

Counting Question; Discrete Structure

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
22 views

Please explain counting; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
41 views

Combinatorics- monotonic subsequence

For each natural number $n$, find a sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms. I've been stuck on this for a while. Can somebody please point me ...
-3
votes
0answers
11 views

Problem in Kernerl of Digraphs [on hold]

Prove that every digraph that is not kernel perfect contains a critical kernel perfect digraph. Where: A kernel K of a digraph D is a subset of D that satisfies: (1) Every pair of vertex in this ...
1
vote
1answer
19 views

Find the chance that subset $B$ is distributed evenly between $(A_1,A_2,A_3)$

We are given set $A$ which is divided to the 3 parts ($A_1$,$A_2$, $A_3$). $|A| = n = 9k$. For $i,j = 1,2,3;\space \forall i \ne j : A_i \cap A_j = \emptyset; \space\space |A_i| = \frac n 3$. ...
2
votes
1answer
35 views

Combinatorics, dividing objects into groups.

Assuming we have got 5 horses, that are competing in a race, and assuming 2 different horses can arrive at the exact same time. How many possibilities there are for outcomes? for 3 horses for example ...
6
votes
1answer
100 views

Are there non-equivalent cardinal arithmetics?

‎Generalizing a concept in mathematics is always a problematic situation. In most cases there are several ways to generalize a notion and it is not easy to decide if a particular generalization is ...
0
votes
0answers
30 views

Multi-ruled combinatorics problem (need this for my lab)

I need to know this for practical purposes and not homework, learning etc.. Say I have 3 electrodes A,B and C. Say I also have 3 electrolytes A,B and C. If electrode A has to be in electrolyte A, ...
-2
votes
2answers
61 views

Combinatorics homework problem [on hold]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
23
votes
6answers
2k views

A beautiful game of gold and silver coins

A stack of silver coins is on the table. For each step we can either remove a silver coin and write the number of gold coins on a piece of paper, or we can add a gold coin and write the number of ...
3
votes
1answer
470 views

Diameter of a Connected Graph

Problem Prove that if $G$ is connected and $\text{ diam}(G) \geq 3$, then $\overline{G}$ is connected. Prove that if $\text{ diam}(G) \geq 3$, then $\text{ diam}(\overline{G}) \leq 3.$ Prove that if ...
48
votes
2answers
3k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is ...