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 (4)

1
vote
1answer
24 views

Find number of pairs satisfying given absolute difference and product

If I'm given absolute difference of two numbers and their product, how can I determine the number of ordered pairs possible? What I have thought is - Total number of pairs possible may be 4, 2 or 0. ...
0
votes
1answer
33 views

Unfair coin probability (P) that results in 0.5% chance of getting x tails out of y tosses?

For an unfair coin toss that produces heads with probability P, what is the value of P that will result in 0.5% (i.e. 0.005) chance of getting exactly x tails out of y tosses? i.e. is there a general ...
0
votes
0answers
15 views

Can a set of schedules with conflicting times be represented using combinatorics

Suppose I have a set of data from a database that is all class schedules for a given set of four classes that have non-conflicting times. Can I derive an equation that will represent all possible ...
1
vote
1answer
25 views

Number of permutations of m objects taken out of n objects where an object can repeat any number of times.

I'm given $n$ distinct objects. In how many ways can we select and permute $m$ objects out of those $n$ objects. $n$ may be less than $m$ and any object can appear any number of times. For example: ...
1
vote
1answer
68 views

Hypergraph rainbow colouring of $\{1 \dots n\}$ for $A = \{A_1, \dots A_k\} : A_i \subset \{1, \dots n\}$

We are given collection of sets $A = \{A_1, \dots A_k\}$, where each set $A_i \subset \{1,\dots n\}$. Colouring $\{1, \dots n\}$ into $s$ colours would be called 'rainbow' for given $A$, if $\forall ...
5
votes
2answers
92 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
1
vote
0answers
27 views

Find the number of combinations to host 4 teams, with restrictions [closed]

Four teams A, B, C, and D should be allocated rooms in a hostel. Each member will have separate room. Each team has K members. It is entrusted that there are 4K side-by-side rooms in one long corridor ...
-1
votes
1answer
95 views

Digraph with no source vertex [closed]

Show that in every digraph in which there is no source vertex there are two vertices with the same in-degree. I have tried to derive it using the definition and the properties, but I still can't ...
1
vote
0answers
67 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
0
votes
2answers
22 views

There are 14 students: 8 girls and 6 boys. In how many ways can you make a 4-student committee which has at least one boy?

In a group of 14 students there are 8 girls and 6 boys. Determine the number of ways that a committee of 4 students which has at least 1 boy can be chosen from the group. Here is what I have so far: ...
1
vote
3answers
67 views

Find the number of pathways from A to B if you can only travel to the right and down.

I would like to solve the following, using Pascal's Triangle. Since there are shapes withing shapes, I am unsure as to where I should place the values. EDIT 1: Where do I go from here? How do I ...
3
votes
1answer
28 views

How many different paths can the ball take as it falls from top to bottom?

How many different paths can the ball take as it falls from top to bottom? I've shown my work below; I am wanting to make sure that I've applied Pascal's Triangle to this shape correctly. Honestly, ...
0
votes
1answer
55 views

Combinations. x+y+z=12 [closed]

X+y+z=12 x,y,z are all greater or or equal to 0 and are integers No. of combinations of x,y,z are ............. *note-- (12,0,0) and (0,12,0) are treated as same Please solve this by using formulae ...
-1
votes
3answers
73 views

Understanding combinatorics [closed]

1: There are $3$ distinct groups of $8$ people. How many ways can the groups be divided into triples each consisting of $1$ person from each group? Keep in mind I'm literally taking a stab in the ...
1
vote
2answers
37 views

Sum over product of two binomial distributions

The problem is that of a two-stage "binomial experiment", where first a number $k$ out of $n$ is drawn (each element with probability $p_1$) and later a number $m$ out of those $k$ is drawn (each ...
1
vote
2answers
37 views

In how many ways can I merge $m$ and $n$ items without disturbing the order in each group?

I have two lists having all distinct elements. One contains $m$ elements and other contains $n$ elements. We need to arrange them such that the order of elements of individual lists is not disturbed. ...
1
vote
3answers
52 views

Taylor Series of a Complex Function

Consider the function $$ \exp\left(\frac{z}{1-z}\right). $$ Since this is holomorphic for $|z|<1$, then it has a Taylor Series valid for $|z|<1$, i.e., $$ ...
1
vote
1answer
32 views

How many ways are possible to place k items in n spots such that order of k items is not disturbed

I have k items, need to place them in n spots(n>k). In how many ways can this be done? Example - for k=2 and n=4, these are the possibilities assuming items to be like this [1,2] 12-- 1-2- 1--2 -12- ...
0
votes
0answers
19 views

Orbit closure is uncountable, unless there is a periodic element.

Let $a = (a_i)_{i \in \mathbb N}$ be a sequnece over some finite alphabet $\Sigma$. We may define on the space $X = \Sigma^{\mathbb N}$ a shift operation by $(Sx)_i = x_{i+1}$. Let $A$ be the orbit ...
1
vote
1answer
39 views

Calculate number of solutions

Count number of integral solutions of the equations $\sqrt{K-x^2} \geq 0$ where $x$ Is any variable and $K$ is any positive integer?(also the value of $\sqrt{K-x^2}$ should be an integer).
4
votes
1answer
89 views

Proper Bernoulli Function Generating Function

Consider the function $$\frac{t}{e^t - 1} = \sum_{i=0}^{\infty}\frac{B_i}{i!}t^i$$ This has been one of the famous generating functions for the bernoulli numbers. What about the function associated ...
0
votes
2answers
93 views

In a unique Soccer series between Earthlings and Martians …

Suppose in a unique Soccer series between Earthlings and Martians, the tournament will continue till a team wins 5 matches. Then the number of ways the series can be won by Earthlings, if no match ...
-1
votes
0answers
31 views

A new proof for Combinatorial Nullstellensatz

Can somebody check the "new" proof? Or has the proof appeared before?
1
vote
1answer
82 views

How to prove this Catalan number identity

Catalan number is $\displaystyle C_n= \frac{1}{n+1}\binom{2n}{n}$. How to prove that $$C_{2n-1} = \sum_{k=0}^{n-1}\left(\binom{2n-1}{n-k-1}-\binom{2n-1}{n-k-2}\right)^2$$ for $n\geq 1$. Thank you.
4
votes
3answers
122 views

How to prove combinatorial identity $\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose s}{s\choose m-s}$?

The following combinatorial identity have been verified via maple, but I can not prove it. Who can prove it without WZ mehtod? $$\sum_{k=0}^s{s\choose k}{m\choose k}{k\choose m-s}={2s\choose ...
1
vote
2answers
102 views

How prove this identity$\sum_{k=0}^{n}\binom{2k}{k}\binom{n+k}{2k}(s-t)^{n-k}t^k=\sum_{k=0}^{n}\binom{n}{k}^2s^{n-k}t^k$

Today I see a paper,and this author say it is easy to have this identity.But I take sometimes to prove it,and I can't prove it. show this following identity holds for any real $s$ and $t$ and any ...
4
votes
3answers
365 views

pidgeonhole problem need assistance

Suppose you have a sequence 2014, 20142014, 201420142014, . . . Show that there is an element in this sequence such that it is divisible by 2013. This is a problem I had on an exam and I know that ...
3
votes
3answers
136 views

AHSME 1981 #22 - Number of lines that pass through four distinct points

How many lines in a three dimensional rectangular coordinate system pass through four distinct points of the form $(i, j, k)$ where $i$, $j$, and $k$ are positive integers not exceeding four? ...
1
vote
2answers
32 views

Unique combinations of strings

If I have the string Delaware and I want to figure out how many unique strings can be made from the letters in this word, I know that the answer is 8!/(2!)(2!) and that the reason we divide by 2! and ...
-1
votes
3answers
38 views

No. of different possible arrangements.

How can I find no. of different possible arrangements with the factor of the term $a^2b^4c^5$ written at full length.
1
vote
1answer
16 views

Birthday problem: Let X be number of people needed for a match. Find the PMF of X.

(Introduction to Probability, Blitzstein and Nwang, p.128) People are arriving at a party one at a time. While waiting for more people to arrive they entertain themselves by comparing their ...
0
votes
3answers
36 views

Probability question - arranging 20 pupils in a row - 8 boys and 12 girls

We have 20 pupils in class, 12 girls and 8 boys. We arrange the pupils in a row, and now need to calculate the following probability: a. The probability that Jana, one of the girls, will not stand ...
0
votes
0answers
56 views

Approach name - Ross Millikan's answer

I want to know the name of an approach (formula) in the first comment of this question (@Ross Millikan's answer) Counting arrays with gcd 1 Thanks
4
votes
2answers
76 views

Arranging numbers $1,2,3,\dots,n$

In how many ways numbers $1,2,3,\dots,n$ can be arranged in a row such that $1$ cannot be on the first place, $2$ cannot be on the second place, $3$ cannot be on the third place, etc? I tried this ...
1
vote
0answers
25 views

Tool for construction of graph with specified properties

Is there a tool (class of algorithms for graph generation) that can construct graph with specified properties. E.g. construct graph who is homeomorphic with both to K5 and K3,3. Construct planar graph ...
1
vote
1answer
40 views

$4 $ balls selected at random from $ 15$

$15$ balls $ 4$ selected $1$ blue, $2 $ green, $3$ red, $4$ white, $5$ yellow What is the probability that $2$ are red and at least $1$ is white? Now the way this question is worded makes it ...
2
votes
1answer
98 views

Select k no.s from 1 to N with replacement to have a set with at least one co-prime pair

Given $1$ to $N$ numbers. You have to make array of $k$ no.s using those no.s, where repetition of same no. is also allowed, such that at least one pair in that chosen array is co-prime. Find no. of ...
15
votes
1answer
556 views

The 'Unlock All Digits' Game

I challenged myself and thought of a new problem I tried to solve. Here are the rules : The goal is to 'unlock' all the numbers $0,1,2,3,4,5,6,7,8$ and $9$ When you start the game, the only number ...
0
votes
1answer
29 views

How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

Say I have a set of 3-CNF clauses $$\mathcal{S} = \{ x_1 \vee x_2 \vee \bar{x_3}, ~~x_4 \vee x_5 \vee x_6\}$$ where $\bar{x}$ is the negation of $x$. Each variable range over $\mathbb{Z}^2$. How ...
11
votes
2answers
103 views

Students who see ears of another student

A student is standing in each cell of an $n\times n$ grid, looking at one of the four directions: up, down, left, right. It turns out that no student is at the border and looking out of the grid, and ...
2
votes
2answers
36 views

Number of winning tern in a deck of cards and other 3 related questions

There is a deck made of $81$ different card. On each card there are $4$ seeds and each seeds can have $3$ different colors, hence generating the $ 3\cdot3\cdot3\cdot3 = 81 $ card in the deck. A tern ...
3
votes
0answers
76 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
0
votes
1answer
36 views

Positive integers NOT divisible by 3 or more primes

How many positive integers $<200$ are NOT divisible by 3 or more primes ? My answer: \begin{eqnarray*} &=&\text{Number of positive integers less than }200-\text{ Number of composite ...
2
votes
1answer
41 views

How many different cubes can be obtained if four colours are used?

I would like a confirmation to my answer. In this question, faces sharing a common edge cannot be of the same colour. My way of reasoning started by choosing the colours Red (R), Yellow (Y), Green ...
3
votes
2answers
63 views

Calculate $\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$

Knowing that: $${2k\choose k}=\sum_{j=0}^k{k\choose j}^2.$$ calculate the sums: $$\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$$ Any sugestions please? Thanks in advance.
2
votes
1answer
35 views

A question about different pairs that are formed from a set of 16 different poeple such that…

I got the following problem: Given a set of 16 different people. We partition the people into pairs of two. Each pair needs to accomplish a task. And the probability that a pair accomplishes ...
2
votes
1answer
30 views

groups with equal sums [duplicate]

Suppose we have $2n+1 $ real numbers.if we remove any of these numbers we can seperate the remaining $ 2n $ numbers in two groups of $ n $ numbers with equal sums.show that all these numbers are ...
2
votes
1answer
42 views

Counting permutations of a multiset restricted by nearness condition

I've been scratching the noggin on this for a bit, and have come up blank so far. Given a multiset $S$ with $Z$ zeros and $O$ ones, how many permutations are there where there is at least one pair of ...
3
votes
1answer
36 views

Finite abelian groups (application of structure theorem)

Problem Find all finite abelian groups that simultaneously have exactly $7$ elements of order $2$, exactly8 elements of order $3$, exactly $8$ elements of order $4$, at least an element of order ...
2
votes
0answers
48 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...