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
21 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$ ?
5
votes
3answers
500 views

Probability of some die face being missed N or more times in a row in M rolls? [Clarified]

2015/01/28 Clarification: Question rewritten to remove ambiguity that elicited (interesting) responses to a different problem (use edit should you wish to view). From Markus' feedback on the earlier ...
0
votes
0answers
4 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 ...
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 ...
2
votes
1answer
56 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 ...
3
votes
0answers
22 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
0answers
13 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
2answers
659 views

How do I find the maximum number of knights on a chess board?

I came across this problem and after thinking a lot I could not get any idea how to calculate it. Please suggest to me the right way to calculate it. Given a position where a knight is placed on ...
2
votes
0answers
41 views

The annihilator numbers of $S/I$

Let $S=K[x_{1},x_{2},...,x_{n}]$ and $I$ be a strongly stable ideal of $S$. Compute the annihilator numbers of $S/I$ with respect to the almost regular sequence $x_{n},x_{n-1},...,x_{1}$. ...
5
votes
1answer
46 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
1answer
26 views

Dividing conference attendees into unique groups

How can I divide 20 people up into groups of 5 for 6 different break out sessions where none of the groups contain the same people. The idea is to get everybody to meet the others and work in ...
0
votes
0answers
36 views

Generalized Mobius Inversion formulae

I am having as problem with inverting a relation of the form $f(i)=\sum_{j=0}^i g(i,j)h(j)$ I would like to have h in terms of f and g. I know that if my formula was of the form $f(i)=∑_j^ih(j)$ I ...
1
vote
0answers
26 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 ...
0
votes
2answers
27 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$ ...
2
votes
1answer
55 views

Separating points on a plane

BdMO 2011 There are $25$ points on a plane, no three of which lie on a line. Find the minimum number of lines needed to separate them from one another. Can we assume that the points lie on a ...
1
vote
2answers
53 views

Probability of $k$ collisions

Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this $n$ times. In the end what is the probability of having at least one bucket with exactly $k$ balls? I have ...
0
votes
3answers
25 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 ...
1
vote
0answers
20 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
vote
1answer
54 views

Maximum of the minimal distance of a set of points in an equilateral triangle

In this question, a closed triangle on a plane is a set of all points in its area and on its boundary, while an open triangle excludes its boundary. Now, the problems: Let $T$ be an equilateral ...
1
vote
1answer
68 views

How to find the number of combinations in which a class of elements always has to be included?

Say I have a set $\{A, B, C, D, E, F\}$ and I have to find how many sets of four elements I can make from these that must include at least any two elements from the set $\{D, E, F\}$? On a similar ...
3
votes
4answers
356 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
-1
votes
0answers
17 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
votes
1answer
22 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
0answers
39 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$ ...
3
votes
0answers
39 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 ...
2
votes
2answers
78 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
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 + ...
1
vote
2answers
33 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 ...
4
votes
0answers
31 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 ...
3
votes
1answer
19 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
32 views

placing couples in a circle combinatorics question

In how many ways you can sit n men and n women so that : a) Every man sits near his wife. b) None of the men can sit next to thier wives. I think the answer for A is 2(n-1)!, not sure if it's true ...
0
votes
1answer
21 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 ...
0
votes
2answers
26 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
28 views

All the combination of cycles of consecutive numbers

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\ \ \ \ ...
13
votes
3answers
778 views

Any ideas on how I can prove this expression?

I don't have a lot of places to turn because i am still in high school. So please bear with me as i had to create some notation. In order to understand my notation you must observe this identity for ...
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 ...
5
votes
1answer
58 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 ...
6
votes
2answers
399 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
0
votes
1answer
4 views

Maximal independent sets in a graph $G$ versus maximal matchings in the line graph $L(G)$

I'm a bit confused because of the answers in Maximum matchings in infinite graphs . I was thinking that an independent set in a graph $G$ corresponds to a matching in the line graph $L(G)$, and vice ...
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
33 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) - ...
4
votes
3answers
41 views

Stirling Numbers Proof

Prove the following: $$\sum\limits_{k=1}^{∞} (−1)^k (k − 1)! S(n,k) = 0$$ Where $S(n,k)$ is the Stirling numbers of the second kind. (Hint: Recurrence Relation) Workings: The recurrence relation ...
0
votes
3answers
45 views

Proving sums of multinomial coefficients

If m and n are positive integers, how do I prove: $$\sum_{k_1+\ldots+k_m=n}\binom{n}{k_1,\ldots,k_m}=m^n\;.$$
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 ...
1
vote
2answers
36 views

Partition of not-so-distinguishable objects into indistinguishable bins

Every textbook on combinatorics seems to deal with either totally indistinguishable objects and bins, or completely distinguishable objects and bins. What I have is something in between: objects are ...
0
votes
1answer
25 views

Prove that a sequence can be enumerated using Catalan numbers

This problem is taken from R.P. Stanley’s Enumerative Combinatorics. Give bijective arguments to show that sequences of $n$ $1$'s and $n$ $-1$'s in which the sum of the first $i$ terms is ...
0
votes
1answer
45 views

A few basic Counting Problems

I don't know if I got these correct. Can someone check for me? How many ways are there to roll a sum of 7 with three standard 6-faced die? There is: 1,1,5 1,2,4 1,3,3 1.4.2 1,5,1 2,1,4 2,2,3 2,3,2 ...
4
votes
0answers
35 views

How many expressions can be formed with two commutative and associative functions?

Suppose we have two binary functions $f,g$ which are commutative and associative, i.e., satisfying $$ f(a,b) = f(b,a) \qquad g(a,b) = g(b,a)$$ $$ f(a,f(b,c)) = f(f(a,b),c) \qquad g(a,g(b,c)) = ...
0
votes
2answers
32 views

Arranging identical balls in a circle

In how many ways can 4 identical red balls and two identical white balls be arranged in a circle? This is an elementary problem, but many tries have not yet yielded results. I tried by taking the ...
1
vote
1answer
23 views

Nearest neighbour algorithm (or so I think).

The algorithm is as follows: Given a graph, we start with some arbitrary vertex, in this vertex the path starts. From a vertex we are at we proceed to a neighbour vertex along some edge, we're keeping ...