For 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. Combinatorics is a ...

learn more… | top users | synonyms (4)

1
vote
1answer
43 views

2-transitively, formula [closed]

Let $G$ be a finite group and let $X$ with $|X| \ge 2$ be a set on which $G$ acts. Then $G$ acts on $X \times X$ via $g \cdot (x, y) = (g \cdot x, g \cdot y)$. The action of $G$ on $X$ is called ...
1
vote
1answer
39 views

How to identify which terms are infinite sequences?

I've made this question some time ago. I thought that the term $x$ in $x+e^x$ would be a sequence $a_x=x=\{0,1,2,3,\ldots\}$ and it turns out that it is the sequence $\{0,1,0,0,\ldots\}$. Whenever I ...
4
votes
2answers
30 views

Which solution is correct to this question: find the number of different sequences $(x_1,x_2,x_3,x_4,x_5)$ with following rules

I have two solutions for this problem: find the number of different sequences $(x_1,x_2,x_3,x_4,x_5)$ with following rules $x_i \in \{1,2,3\}$ where $1 \leq i \leq 5 $ and $x_1 \leq x_2 \leq x_3 \leq ...
2
votes
2answers
56 views

Closed form solution and combinatorial proof.

First of all, I would like to figure out a closed form solution for the following summation: $$\sum^{n}_{k=0} C(n,k)\cdot C(2n,n+k)$$ Where C(n,k) means n choose k, or $\frac{n!}{(n-k)!\cdot k!}$ ...
0
votes
1answer
40 views

Multivariate Hypergeometric Cumulative Distribution Function

I think my problem is unique in that it hasn't been posed here. Starting with a simple case to which I think I have an answer: I have 11 cards, 3 of which are bad. These cards are used in a game ...
0
votes
2answers
63 views

Find the sum which is not possible

I have a set having the $N$ numbers starting from $1$ to $N$. I know the maximum sum can be formed from members of this set is $N(N+1)/2$. Now i am giving $K$ numbers that are removed I have to find ...
0
votes
1answer
44 views

Four dice showing 3 values

I have 4 different color dice: blue, red, yellow and green. I need to check how many possibilities we get if the set of the numbers that are on the dices consists of 3 distinct numbers. In other ...
0
votes
1answer
36 views

Number of upward closed subsets

I am looking for an algorithm of some sorts that can produce the total number of upward closed subsets in a partial ordered set. Let $\langle P,\leq\rangle$ be a (finite) partial ordered set, then an ...
2
votes
2answers
32 views

Non-negative integers to form a sum with restrictions? [duplicate]

How do I solve this? Number of non-negative solutions to $x_1 + x_2 + x_3 + x_4 = 4$ where $0 \le x_i \le 3$? What's the general technique? I already know the technique for $j \le x_i$ but have no ...
3
votes
1answer
20 views

Martingales and different definitions

Are there any differences between the following definitions of Martingales and if so what are they? Let $(X_{i})_{i=1}^{n}$ and $(Z_{i})_{i=1}^{n}$ be sequences of random variables then $(X_{i})$ ...
1
vote
2answers
10 views

Probability of identical numbers in two sets $l$ and $n$ where $n$ has been drawn without replacement from $N$?

The problem I am trying to produce a general formula for the problem below. This is not homework. $N$ different balls are inside an urn. The balls have numbers on it and are labelled $1\ldots N$. ...
0
votes
1answer
30 views

How many sequences of five bases are there?

A and G are purines and C and T are pyrimidines. How many sequences of five bases are there that consist of three purines and two pyrimidines? I thought that I could do : 2^3 x 2^2 = 32 my teacher ...
1
vote
0answers
47 views

Can we choose $p$ integers within $2p-1$ arbitrary integers, such that the sum of them is divisible by $p$?

Suppose we have $2p-1$ integers(not necessarily distinct), where $p$ is a prime. Can we always find $p$ integers within it such that the sum of them is divisible by $p$? this can be verified when $p$ ...
10
votes
3answers
620 views

Find the highest power of two in the expression.

What would be the highest power of two in the given expression? $32!+33!+34!+35!+...+87!+88!+89!+90!\ ?$ I know there are 59 terms involved. I also know the powers of two in each term. I found that ...
1
vote
1answer
37 views

Doubt : Prove the number of matches

I was working my way through some problems in Discrete Maths by Rosen, when I came across the following question: There are x players in a singles badminton tournament Show that there are ...
5
votes
0answers
37 views

Number of representatives from states to from a comittee?

Among the three representatives to a conference from each of the fifty states, either none, one, or two of the representatives will be chosen for a large special committee. How many ways can this ...
5
votes
0answers
61 views

Possible squares that a chess piece can move to

Fix four integers $a,b,c,d$ with $\gcd(a,b)=\gcd(c,d)=1$ and with the condition that $abcd<0$ (this ensures that the two moves are of different sign slope). Suppose then we have a chess piece that ...
2
votes
1answer
30 views

Handshake counting problem

This is a problem from Ross' probability book. Problem: Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place? Question: I think the correct ...
9
votes
1answer
101 views

Are injections harder to find than surjections?

Given two finite sets $A$ and $B$ with $|A|<|B|$ There are more functions from $B$ to $A$ than from $A$ to $B$ except when $|A|=1$ or $|A|=2,|B|=3,4$. See here for proof. It is also true there are ...
0
votes
1answer
40 views

Counting 6 letter words containing atleast 4 vowels

Using the letters of the word EDUCATION , how many words using 6 letters can be made so that every word contains at least 4 vowels?
2
votes
0answers
33 views

Questions regarding Martingales

I'm trying to learn about Martingales with specific focus on combinatorial problems. However i'm far from an expert in algebra and am having some trouble understanding the basic idea. I will write the ...
13
votes
2answers
230 views

When $\frac{C(n, k)}{n^{k-1}} > 1$?

I came across this while considering the subset sum problem in relation to another problem. Define the ratio, $$R(n,k) = \frac{C(n, k)}{n^{k-1}} = \frac{\binom n k}{n^{k-1}}$$ and the integer ...
0
votes
1answer
23 views

lines in a plane.

Let there be 'p' lines which are concurrent at a point A and 'q' other are concurrent at a point B. Oh, and no 2 lines are parallel. Case 1: No line out of 'p' passes through B and similarly for 'q' ...
1
vote
2answers
72 views

Question about Binomial Sums [duplicate]

Prove that for any $a \in \mathbb{R}$ $$\sum_{k=0}^n (-1)^{k}\binom{n}{k}(a-k)^{n}=n!$$ I rewrote the sum as $$\sum_{k=0}^n \left((-1)^{k}\binom{n}{k} \sum_{i=0}^n (-1)^{i}a^{n-i} k^{i} ...
0
votes
1answer
42 views

Count n-length words containing pattern

I have a class $A$ of words from alphabet of letters {a,b,c}, containing "abbc" and class $B$ which has the same words but with ...
4
votes
2answers
59 views

Minimal number of questions

I am trying to solve the following problem : $49$ distinct numbers are written in a $7\times7$ cell board. You are allowed to pick any $3$ cells on the board and find out the set of numbers written in ...
2
votes
3answers
53 views

in a mountain climbing expeditions 5 men and 7 women are to walk

in a mountain climbing expeditions 5 men and 7 women are to walk single file so that no 2 men are adjacent. How many ways are possible?
-2
votes
2answers
35 views

Counting Principles. Numbers not divisible by $5$

How many numbers between $101$ and $800$ inclusive are not divisible by $5$? Should be done using factorials and nCr.
2
votes
1answer
57 views

The track of the chess knight at $n\times n$ board

Let $ 6 \le n $ and also we have an $n\times n$ board. Prove that for every way of coloring the $n \times n$ board with $n$ colours there will be a track such that a chess knight from the bottom left ...
0
votes
0answers
39 views

Tiling with exactly 2013 different ways

A rectangle with side lengths integers $a$ and $b$ will be covered with tiles, rectangular with a length of one side so that a portion of the rectangular area will be covered with black tiles and the ...
1
vote
1answer
31 views

Elementary question on probability

Villages A,B,C, and D are connected by overhead telephone lines joining AB, AC, BC, BD, and CD. As a result of severe gales, there is a probability p(the same for each link), that any particular link ...
3
votes
1answer
46 views

Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
1
vote
1answer
21 views

Hillman and Hoggat's Binomial Generalization

In proving Gould's "Star of David" conjecture, Hillman and Hoggat generalized the binomial coefficient. First, they demand that $a_n$ be a sequence with the two properties that $$\gcd(a_m, a_n) \mid ...
0
votes
0answers
30 views

increasing partition

Given two natural numbers $m,n$, with $m<n$, is there a way to construct the increasing partition $p_1,\dots,p_m$ of $n$ in $m$ parts such that the choice of $p_m,...,p_1$ (in this reverse order ...
2
votes
2answers
89 views

Proof that $a^b>b^a$ if $a<b$ are integers larger or equal to two and $(a,b)\neq (2,3),(2,4)$ [duplicate]

I would like a proof that if $a<b$ are integers with $2\leq a,b$ we have $a^b>b^a$ unless $a=2,b=3$ or $a=2,b=4$ . I would like to use as little calculus as possible. Here is my current ...
1
vote
1answer
27 views

Exponential GF application [closed]

I have $15$ different books I have $5$ child. I want to give it all to all my child where every my child get at least $1$ book How many way I can distribute it????
5
votes
0answers
80 views

number at the circumference

Determine all natural numbers $n$ such that the numbers $1,2,3, . . . ,n$ can be placed on the circumference of a circle, such that for any natural number $s$ with $1 \le s \le \frac{n(n+1)}{2}$ there ...
1
vote
1answer
55 views

What is the number of elements in the set {(x,y): x|n, y|n, gcd(x,y)=1} ?.

Sloane's OEIS A048691 gives an explicit formula:(2*e(1)+1)*(2*e(2)+1)***(2*e(r)+1) where the e(i)'s are the exponents in the prime factorization of n. It turns out that the same formula counts the ...
0
votes
2answers
36 views

Combinatorics cards question

In a 52 cards deck there are 4 sets with 13 cards each. In how many ways can you choose 5 cards so that every shape (from the 4 sets) is represented on at least one card ? I'm not sure if its 13^4 * ...
4
votes
1answer
80 views

How many ways can you put 8 red, 6 green and 7 blue balls in 4 indistinguishable bins?

Assume all balls with the same color are indistinguishable. The order in which balls are put in a bin does not matter. No bins are allowed to have the same distribution of balls! For example, this ...
0
votes
1answer
20 views

How many permutations of size 5 does the 4 make with 1st five numbers .repetition allowed.

What i want to calculate is suppose if we are having m numbers then how many permutations of size n will be there such that k fixed numbers are always present in those permutations. Example : we ...
1
vote
1answer
13 views

Counting Principles. Selecting, while having constants

A committee of five people is to be selected from a class of 12 boys and 9 girls. How many such committees include at least one girl? Can't find the right method on other forums.
1
vote
1answer
59 views

Coloring a Tree

We numberd nodes from $1$ to $N$ for convinent. We firstly color node $1$. Then we will color $N - 1$ remaining nodes, in any order which satisfied condition: node are chosen to color must be ...
2
votes
1answer
51 views

Counting sequences

Given 2 positive integers $a_1$ and $a_n$, in how many ways can we 'complete' the sequence to form a sequence of integers $a_1,a_{2},\dots,a_n$ such that $\forall i$ with $1 < i \leq n$ we have ...
0
votes
1answer
42 views

Counting total number of Functions

Suppose F be the set of one-to-one functions from the set $1,2,..,n$ to the set $1,2,...,m$ where $m \geq n \geq 1$. Then how many functions f in F satisfy the property $f(i)<f(j)$ for some $1 \leq ...
3
votes
1answer
60 views

How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number?

Question: How many positive integers less than 1000 are multiples of 5 and are equal to 3 times an even number? So Multiples of $5$ and $6$ If a number is a multiple of $5$ and $6$ then it is a ...
0
votes
2answers
59 views

How many routes are there that pass through at most one congested intersection

I am trying to solve the following problem, but i am not quite sure how to attack. Problem Description A taxi drives from the intersection labeled A to the intersection labeled B in the grid of ...
0
votes
4answers
208 views

Let $w, x, y, z$ be natural numbers. Find the correct alternative.

Let $w$, $x$, $y$, $z$ be four natural numbers such that their sum is $8\cdot m+10$, where $m$ is a natural number. Given $m$ which of the following is possible: The max. possible value of ...
3
votes
1answer
53 views

Combinatorial problem about all natural divisors being a perfect square

Let $P_k(n)$ be the product of all natural divisors of n, which are divisible by k. (Empty product is 1) Prove that $P_1(n)...P_n(n)$ is a perfect square. I checked small cases, they are all right? ...
1
vote
2answers
37 views

How Many Permutations of $\{1,\ldots,n\}$ satisfy that $x_i<x_{i+2}$ and $x_i<x_{i+3}$?

Finding number of permutations $(x_1,...,x_n)$ of $\{1,2,3,...,n\}$ fitting these conditions: $x_i\lt x_{i+2}$ for $1\le i\le n-2$ $x_i\lt x_{i+3}$ for $1 \le i \le n-3$ $n\ge 4 $ I went through ...