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
2answers
15 views

Proving Combination Sums

I'm having a bit of problems proving the following: $\sum_{k=1}^n$$k$$k \choose n $ $ = n\times 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
8 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\ \ \ \ ...
0
votes
0answers
9 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
32 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 ...
0
votes
2answers
21 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
1answer
44 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
23 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 ...
3
votes
0answers
19 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
1answer
20 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
2answers
26 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 ...
0
votes
1answer
20 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 ...
0
votes
1answer
24 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 ...
1
vote
3answers
42 views

How many $6$ digit numbers have their digits in increasing order?

I can calculate the amount of ways you can choose $6$ digits out of $($1,2,3,4,5,6,7,8,9$)$, but this would include combinations where there are $2$ or more of the same digit.
4
votes
3answers
38 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 ...
2
votes
2answers
63 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 ...
1
vote
2answers
34 views

Find all natural numbers for which $3\binom{2n}{n+1}=2\binom{2n+1}{n-1}$ holds true

I end up getting a quadratic equasion with no natural answers, so I am probably wrong. (Dont know if the tag is right, its part of the combinatorics section in my book)
0
votes
3answers
29 views

Combinatorics question about picking a staff

This is the Question : In a building there are 5 men and 5 women. we need to pick representive for the building so that at least one woman and at least one man has to be there. there are no limitions ...
-1
votes
1answer
26 views

Counting relations question

I have a small question about relation counting, i'm looking for formulas. I know that there is a formula for reflexive and anti reflexive. I'm not sure about the simetric or a-simteric ones, and if ...
0
votes
0answers
33 views

Why the space of all permutations of a vector (n!) is smaller than the space of all possible permutations of a sorting network?

Imagine you have a vector with 2048 entries. The total permutations are 2048! Now you have a sorting network let us say AKS, the total number of possible results with nlog(n) gates is $2^ {n log (n)}$ ...
0
votes
1answer
44 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
3answers
269 views

How to check my answer in combinatorics problems

Combinatorics problems (combinations and permutations) are an absolutely maddening subject for me. I can seem to work my way to the answer, provided I already know the correct answer. However, I can ...
0
votes
0answers
7 views

Explain how lines and points in the 2D plane form an affine plane?

I think I understand the affine transformation, but I just have trouble describing how lines and points in the 2D plane form an affine plane.
1
vote
2answers
22 views

How many four digit numbers divisible by five whose digits add up to 6 exist?

I am just learning the basics of combinatorics and my quick answer to this was 22. Though the approach was a bit rough and I sont know how mathematical in nature.
1
vote
1answer
29 views

Let n>=2, k>=2. The set of all k-element subsets partitioned into 4 classes: (i) class of subsets containing both 1 & 2, how many k-element subsets?

Sorry for the long title, I'm new here & not sure of the appropriate way to post long questions. The full question is: Let n>=2,k>=2. The set of all k-element subsets of [n] may be partitioned ...
1
vote
2answers
24 views

Solving a recuurence relation

How can I solve the following recurrence relation? $f(n+1)=f(n)+f(n-1)+f(n-2), \ f(0)=f(1)=f(2)=1.$ I can use the characteristic equation which is $x^3=x^2+x+1$. It has three distinct roots ...
1
vote
1answer
17 views

Difference of two graphs

Given two graphs $G_{1}$ and $G_{2}$ what exactly is the definition of $G_{1}-G_{2}$ used in the Diestel book? Most operations on graphs are clearly defined apart from this one.
1
vote
2answers
37 views

Multnomial coefficient combinatorics problem

The following problem: Ten diplomatic delegates are seated in a row. There are two specific seating requirements: 1) France and Britain are sat next to each other, and 2) the U.S. and Russia are ...
0
votes
1answer
24 views

How many cases can draw diagonals?

Imagine a n_regular polygon that vertex is named by 1 to n. We know can draw (n)(n+3)/2 diagonals in n_regular polygon,Also know if we want to draw Maximum diagonals that not intersecting each other ...
1
vote
1answer
15 views

Generating Functions and Polynomial Expansions

Give a formula similar to: $\frac{1-x^{m+1}}{1-x} = 1 + x + x^2 + ... + x^m$ For the following (a) $1 + x^4 + x^8 + ... + x^{24}$ (b) $x^{20} + x^{40} + ... + x^{180}$ Workings a. $1 + x^4 + x^8 ...
0
votes
2answers
19 views

How many k-digit numbers ending with zero(s) are there?

We have a $k$-digit non-negative number in base $B$ (let's treat all k-digit numbers as valid, so that for example if $k=5$ and base $10$ all numbers from $00000$ to $99999$ are perfectly fine). How ...
0
votes
4answers
59 views

2003 Putnam A-1 Help needed about sequences

Okay so for $n=1$ there is only one way. For $n=2$ you have, $1+1, 2 + 0$ for $n=3$ you have: $1+1+1, 1+ 2, 3 + 0$ three ways. So $P(n): n$ ways, we must prove the $P(n+1): n + 1$ statement is ...
1
vote
3answers
42 views

Arranging a word

This is the question : In how many ways you can arrange the word AAABBCDEFG so that the first letter is A or E ? I'm not sure if im doing this right. My plan is to take all the arrangments and ...
0
votes
1answer
29 views

Combinatorial Proof of Identity b_n

Prove that: $$b_n = 1 + \sum\limits_{k=1}^{∞} \binom{n-1}{k}b_k.$$ Workings: The first thing I noticed is that the above equation looks very similar to a Bell Numbers proof: ...
1
vote
2answers
22 views

Combinatorics, surjective functions with conditions

Question: $A=\left\{ 1,2,3,4,5\right\} $ , $B=\left\{ 1,2,3\right\} $ . How many surjective functions are there such that $ f(1)\neq1$ ,$f(2)\neq2$ ,$ f(3)\neq2$ . Solution: Overall we have ...
0
votes
0answers
17 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
14 views

Multiplicity of equation values when taken over all compositions of an integer

I do not work in number theory/combinatorics, so I don't have much of an idea of how difficult, or trivial, this question is. Any suggestion/ideas appreciated. Using the terminology (repeated here) ...
0
votes
1answer
18 views

How many undirected graphs are possible with $4$ labelled vertices such that exactly $1$ edge is present?

I have drawn the graph and the result is $6$ graphs are possible. A simple graph can have a maximum of $\Large\binom{n}{2}$ edges and each edge can exist or not exist. Therefore, ...
0
votes
2answers
26 views

How many 5-element subsets of [10] contain at least one of the members of [3]?

Here [10] denotes the set {1,2,3,4,5,6,7,8,9,10} & in the same manner [3] denotes {1,2,3}. I'm attempting to solve this for my combinatorics course. My method would be to solve 10 permutation 5, ...
0
votes
1answer
26 views

Diving students into teams

So this is the question : Count the number of ways in which you can divide a group of 33 sudents into 3 soccer teams (each team has 11 studends, them have no names). I know that i shouldn't use the ...
1
vote
1answer
19 views

Number of derivatives in a taylor series expansion

I would like to confirm if the number of derivatives we need to calculate in a specific order of a taylor series expansion is the sum of the multinomial coefficient of that order: $$ f:\mathbb{R}^k ...
-2
votes
2answers
36 views

no. of all ordered tuples (x,y,z) such that x,y,z are all positive integers that satisfy the equation x + 2y + 3z = 30? [on hold]

How do I find the number of all ordered tuples (x,y,z) such that x,y,z are all positive integers that satisfy the equation x + 2y + 3z = 30 ? Is there any easy and less time taking method to solve ...
0
votes
2answers
32 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 ...
8
votes
3answers
778 views

Combination Problem: Arranging letters of word DAUGHTER

The number of ways in which we can form a 8 letter word from the letters of the word DAUGHTER such that all vowels are never occur together is My approach: As ...
1
vote
0answers
9 views

difference between a combinatorial map and a rotation system?

Wikipedia has separate articles for combinatorial map and for rotation system, but as far as I can tell, their formal definitions are identical. Am I missing something? Or do these terms have ...
0
votes
1answer
24 views

Prove that $\sum_{n≥0} a_k(n)x^n = \frac{1-x}{1- 2x + x^{k+1}}$

Let k be a fixed positive integer and for all n≥0 let $a_k(n)$ be the number of compositions of n where each part is at most k. Set $a_k(0) = 1$. For instance, if k = 2 then $a_k(1) = 1$, $a_k(2) = ...
0
votes
2answers
32 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
1
vote
1answer
29 views

Permutation to a power $\sigma^{100}$

$\sigma = \left( \begin{array}{cc}1&2&3&4&5&6\\3&1&4&5&6&2\end{array}\right)$ I need to calculate $\sigma^{100}$ $\sigma = (1,2,3,4,5,6)$ has order 6, and ...
0
votes
1answer
20 views

compute $\left|<\tau^2>\right|$ for the given permutation

$\tau = \left( \begin{array}{cc}1&2&3&4&5&6\\2&4&1&3&6&5\end{array}\right)$ I need to compute $|\langle \tau^2\rangle|$ I know $\tau^2 = \left( ...
2
votes
1answer
22 views

Mean or mode of pairwise sum-products over all compositions of an integer

Let $S>3$ be some positive integer, and let $\mathcal{B}_{S}$ be the set consisting of the $2^{S-1}$ compositions of $S$. Consider an arbitrary $b\in \mathcal{B}_{S}$, and write ...