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)

0
votes
1answer
16 views

Estimating sums by integrals

Estimating sums by integrals. Let $f : \mathbb{N}→\mathbb{N}$ be an increasing function. Show that $$\sum \limits_{i=1}^n \frac1{f(i)}<\frac1{f(1)}+\int \limits_{1}^{n}\frac1{f(x)}dx$$ I really ...
-1
votes
1answer
19 views

counting the no. of equivalent words

2 word are considered to be equivalent of they have the same order of vowels and the same alphabets and the same number of alphabets as in the original word. then find the number of equivalent words ...
1
vote
2answers
21 views

Probability involving chess board

if 2 cells are chosen at random on a chess board what is the probability that they will have a common side i tried solving the question by considering different cases for the cells on: 1. corner 2. ...
2
votes
1answer
14 views

Polynomials and difference operator

Let's consider a difference operator $\triangle f(n)= f(n+1)-f(n)$. How to prove that $f$ is a polynomial so that $deg(f) \leq d$ if and only if $\triangle f ^{d+1} =0$. First step of the solution ...
1
vote
0answers
11 views

How to find the number of permutations with offset restriction

First question. Okay I have this problem that I've been trying to figure out for a while. I'm writing a computer program I need to quickly calculate the permutations of a set with 'n' elements with a ...
0
votes
1answer
22 views

Circular permutation, sitting 6 people in a round table

6 people sit down a round table. 4 of them belong to group X and 2 of them belong to group Y. How many ways are there for the 6 people to sit down by taking into account that the 2 people in group Y ...
0
votes
0answers
8 views

What Boolean matrices are reachable from the NXN identity only by adding columns mod 2?

This problem arose from work on a Boolean software problem. Starting from an $NxN$ identity matrix, the only operation allowed is to add some column i to another column j (mod 2) - i.e. for all $k$, ...
4
votes
2answers
273 views

How many 0's are in the end of this expansion?

How many $0's$ are in the end of: $$1^1 \cdot 2^2 \cdot 3^3 \cdot 4^4.... 99^{99}$$ The answer is supposed to be $1100$ but I have absolutely NO clue how to get there. Any advice?
0
votes
0answers
10 views

How many closed paths of length n are circling 0 on the square lattice?

The context is that i am studying a course on percolation and we use a very large bound which is $n * 3^n$. Is there a better one? Thanks
0
votes
1answer
38 views

How to find number of subsets

Find the number of all unordered pairs $\{A,B \}$ of subsets of an $8$-element set, such that $A\cap B \neq \emptyset$ and $\left |A \right | \neq \left |B \right |$
0
votes
1answer
12 views

Combinatorial Surjection Proof

Let $S(n,k)$ be the number of surjections from an $n$-set to a $k$-set. Prove use a combinatorial proof that: $S(n+1,k) = kS(n,k) + kS(n,k-1)$, where $n \geq k$ Workings: this equation counts the ...
0
votes
1answer
23 views

Flipping an unfair coin n times

I’m flipping an unfair coin $n$ times. $\mathbb{P}[X=head]=p$ where $p \neq \frac{1}{2}$. What is the probability “head” appears an even number of times? Thank you in advance for your time an ...
0
votes
0answers
15 views

a way to compute energy of a flow on transient trees

Let $T$ be a rooted tree that is also a transient electrical network (so effective resistance from root to infinity is finite) but with recurrent rays. (So effective resistance root to infinity along ...
2
votes
3answers
56 views

How many 20-digit numbers are there which are formed using only the digits 5 and 7 and divisible by both 5 and 7.

now i realised last digit has to be $5$ and position of $7$ wont affect divisibility. ...
0
votes
1answer
15 views

Computing Average Number of Successes When Randomness is Involved

I am attempting to write a program that will compute the average amount of a particular product produced when randomness is involved. Let's say that I am trying to produce some widget. Whenever the ...
2
votes
1answer
9 views

How to figure out how many possible sequences contain a specific criteria

If a 6-sided die is rolled 5 times and each roll is recorded as an element of set A (|A| will be 5 after all rolls), How many results out of all the possible results will have exactly two 4's as ...
0
votes
1answer
30 views

$5$ green dyes, $4$ blue dyes, $3$ red dyes. Number of combination of dyes, which can be chosen taking at least one green and blue dye? [on hold]

$5$ different green dyes, $4$ different blue dyes, $3$ different red dyes. The number of combination of dyes, which can be chosen taking at least one green and blue dye ?
0
votes
0answers
23 views

Monotone subsequence in a random permutation

I wish to compute the probability of having a log(n) length consecutive monotone subsequence in a random permutation of {1,...,n} (log with base 2). I'm trying to show it's $\leq1/n$, does it make ...
1
vote
1answer
23 views

combinatorics digraph question

A digraph $G = G(V,E)$ on the set of vertices $V$ is a graph where every edge $e ∈ E$ is directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on $n$ vertices are there? ...
0
votes
0answers
7 views

Bound from distinct integer summation

We want to find $r$ positive integers $\{a_i\}_{i=1}^r$ such that of atmost $(s+1)^r$ values obtained from $$\sum_{i=1}s_ia_i$$ where $s_i\in\{0,\dots,s-1,s\}$, we insist on some combination of ...
1
vote
2answers
45 views

Not-increasing sequence. How to count.

From digits $\in \{1,2,3,4,5,6,7,8,9 \} $ create sequence not-increasing of length $ 5 $. How many are there such sequences ? I have no idea how to deal with it. Please help.
1
vote
4answers
45 views

Inclusion and exclusion in combinatorics

You have 15 identical balls and must divide them into 4 drawers stacked on top of each other with the following limitations: You have at least 2 balls in each drawer There will be no more than 5 ...
0
votes
2answers
25 views

Rolling dice probability by solving inequlity

I was trying to solve a problem where I have to find the probability of the sum of $\mathcal 3$ rolls of a die being less than or equal to $\mathcal 9$. In order to solve the problem I try first to ...
0
votes
0answers
23 views

Probability of a sequence of urn draws having some pair of draws with a minium number of “matches”?

I have $U$ urns. Each urn contains some sequentially numbered balls (not necessarily the same count between urns) $1, 2, 3,... N_u$. I draw one ball from each urn $1, 2, 3,...U$ in turn, and note ...
3
votes
1answer
33 views

Basic question on appication of Sunflower lemma

A sunflower or $\Delta$-system is a collection of sets $\mathscr{F}$ whose pairwise intersections are all the same set $S$, possibly empty. Elements of the collection of sets $\mathscr{F}$ are called ...
2
votes
1answer
73 views

Sum over subsets of $\{1,2,\ldots,n\}$ of terms involving a product over that subset

I'm attempting to perform a sum, using products, using all possible combinations, in a function. How would I go about doing this? (I really need to find something that works.) For example, say I ...
1
vote
1answer
41 views

Simplest proof about number of arithmetic sequences in set

Given a set $A = \lbrace1,2,3,\ldots,n\rbrace$, where $n \leq 2^{k}$. What is the simplest way to proof that number of arithmetic sequences with lenght $k$ from set $A$ is $< n^2/2$ ?
1
vote
0answers
34 views

Benefits of combinatorial reasoning?

What I usually do instead of counting something, I form a polynomial whose coefficients count it and go from there. If you had to convince someone why they should learn combinatorial reasoning what ...
2
votes
0answers
17 views

A bound on number of elements less than $n$ of a $B_2[g]$ sequence

Let $S \subset \mathbb{N}$. We say $S$ is of type $B_2(g)$ if the number of representation of the form $n = s_1 + s_2 \ (s_1 \leq s_2)$ is bounded by $g$ for every $n \in \mathbb{N}$. Let $S(n)$ be ...
0
votes
1answer
24 views

Ramsey Numbers and edge coloring

Show that for every $k \in\mathbb{N}$ there exists an $n \in\mathbb{N}$, where $n ≤ 3k!$ such that if $K_n$ is coloured in $k$ colours then we can find in $K_n$ a triangle whose edges are of the same ...
0
votes
4answers
38 views

Permutations - selection

Give the total number of possible arrangements of 3 letters chosen from the word CALCULUS. The answer is 96, but all I can get is 5P3=60 (permutations of 3 from 5 different elements), or 8P3 adjusted ...
5
votes
1answer
53 views

Combinatorics - Without order

You have 10 different types balls to choose from. How many different ways are there to choose 5 balls such that no type of ball appears more than twice. My attempt: Case 1 (selecting different ...
0
votes
0answers
19 views

Discrete Mathematics; Counting, Summations [duplicate]

Let n ≥ 1 be an integer. Prove that: $$ \sum\limits_{i=1}^n i(\frac{n}{i}) = n \bullet 2^{n-1} $$ I am not sure how to prove this, I think I need to use the derivative of $$(1 + x)^ n$$ any help ...
1
vote
0answers
22 views

How many permutations of a linear equation

How many strictly positive integer solutions does the equation $x_1+x_2+···+x_n = k$ have? (Hint: Consider the equation $y_1+y_2+· · ·+y_n = k−n$ with variables $y_i \ge 0$.) I believe the ...
-1
votes
1answer
31 views

Find the total number of functions. [on hold]

Consider the two sets $A=\{1,2,3\}$ and $B=\{1,2,3,4,5\}$. Then find the total number of functions from $A$ to $B$ and also find total number of one to one functions from $A$ to $B$.
0
votes
2answers
40 views

A digraph is a graph where every edge is directed. How many digraphs on $n$ vertices are there?

So far I have that between any two vertices (say $j$ and $k$) there are 3 options. there is no edge between $j$ and $k$ there is an edge directed from $j$ to $k$ there is an edge directed from $k$ ...
3
votes
0answers
47 views

How to count the number of substrings in this combinatorics problem?

Let's say I'm making a string of $A$s and $B$s, where the number of $A$s and $B$s are $a$ and $b$ respectively. A total of $a+b \choose a$ such strings are possible. Now, I wish to know the total ...
0
votes
0answers
44 views

Eliminating the duplicate counts

Consider a set of $k$ objects and assume that $n$ length strings are to be constructed, where $n \geq k$. I want to count a set of $n$ length strings, with the following restrictions 1. all $k$ ...
0
votes
1answer
20 views

compositions of $n$ with $k$ odd parts where all $k$ parts are odd

Here's what i've done so far: $S = N^k$ where $N = \{1,3,5,7,9,\ldots\}$ and $N^k = N \times N \times N\times\cdots$ $k$ times $$\Phi_S(x) = \Phi_{}N_\text{odd}^k(x)$$ $$\Phi_S(x) = (x + x^3 + x^5 + ...
5
votes
0answers
36 views

Max possible number of sets that have 1 and only 1 member in common

I have a set of 25 things that I want to group into sets of 6, with the following conditions: Every set shares one, and only one, member in common with every other set No object can appear twice in ...
1
vote
2answers
35 views

Proving Pascal's identity

So I came across Pascal's identity: Prove that for any fixed $r\geq 1$, and all $n\geq r$, $$ \binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}. $$ I know you can use basic algebra or even an inductive ...
3
votes
1answer
21 views

A starting lineup consists of 2 forwards, 2 guards and 1 center. How many different starting lineups..

A certain school has $4$ forwards, $4$ guards, $3$ centers and $1$ person who can play as either a forward or a guard. How many different starting lineups can be made? I came up with 2 answers to ...
0
votes
2answers
27 views

Binomial coefficient identity $\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$ [duplicate]

I'm having a bit of problems proving the following: $$\sum_{k=1}^n k {n \choose k } = n\cdot 2^{n-1}$$ I always seem to get to the line: $2^{n-1} + 1 = 2^n$ which I know is untrue. Could anyone ...
1
vote
1answer
33 views

All the combination of cycles of consecutive numbers [on hold]

Let say that we have $N$ consecutive number $1,2,...,N$ and we want to find all the possible consecutive number cycles of length $2n+1$. For example: $$\begin{align}&N = 5\\&n = 3\ \ \ \ ...
0
votes
1answer
22 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
1
vote
4answers
35 views

Prove using Newton's Binomial Theorem

Let $n≥1$ be an integer. Prove that $$\sum_{k=0}^n k{n \choose k} = n 2^{n-1}$$ Hint: take the derivative of $(1+x)^n$ . I'm assuming that I need to use Newton's Binomial Theorem here somehow. By ...
0
votes
1answer
10 views

Equivalence Classes and Relations of Hexagons

Suppose there is a hexagon in the plane. Consider two colorings of the edges of the hexagon equivalent if you can rotate the hexagon so that edges of the same color map to each other. Suppose you ...
1
vote
2answers
34 views

Why Can I divide generating function by $x$

In many books on generating functions author performs following operation to shift coefficients of $F(x) = \sum_i f_ix^i$ to the left $${F(x) - f_0} \over x$$ which in can be written as $$(F(x) - ...
5
votes
1answer
60 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
1answer
25 views

Show that given $N$ iid variates $X_i$ uniform on (0,1), $P(\max(\{x_i\} > \frac{1}{2}\sum x_i)$ is $\frac{1}{( N-1)!}$

Given an ensemble of $N$ random uniform variates on $(0,1)$, the probability that the greatest variate exceeds the sum of all the other variates is $\frac{1}{(N-1)!}$. Is there any nice way to prove ...