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)

2
votes
3answers
32 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
9 views

Independence number of Cayley graph

Pick a prime number $P$. Denote $M=\Big\lfloor (P-1)^{\frac{r-1}{r}}\Big\rfloor$. Pick $M$ numbers $g_1,\dots,g_M$ each less than $P-1$. Denote $G_{P}[S]$ to be Cayley graph on $P$ vertices ...
0
votes
0answers
5 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
19 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
20 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
22 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
12 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
1answer
23 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
0answers
13 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
55 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
36 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
28 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
20 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
10 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
11 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
16 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
22 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
28 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
760 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
8 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
23 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
28 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 ...
1
vote
1answer
20 views

Generating function with a given weight function using 3 variables

So I'm given a set: [10] x [2] x $\mathbb N$ with a weight function: $w(a, b, c) = 4a + 2b + c$ And i'm asked to determine the generating series of this, but I'm confused due to the 3 variables.. I ...
4
votes
3answers
65 views

Outline for high school combinatorics class?

I am a high school student and I have taken all the math classes that my school provides (through calculus AB). I have been looking at a possible independent study for next year and I have landed on ...
1
vote
0answers
24 views

Expected size of largest weakly connected component?

Given an undirected graph of n vertices and n randomly assigned edges, one edge from each vertex, what is the expected size of the largest connected component? For example, with four vertices, there ...
0
votes
1answer
24 views

Generating Functions for Fruits

Find a generating function $(x_1, x_2, ..., x_m)$ whose coefficients of $x_1^{r_1} x_2^{r_2}\ldots x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ fruits of type $1$, $r_2$ ...
0
votes
1answer
23 views

How many ways can you choose 4 non empty subsets from q 10 element set

How many ways can you divide the set $A=\{1,2,3,4,5,6,7,8,9,10\}$ into a 4 non empty subsets? Hint: there's a formula states that the number of all the functions from $A \to \{1,2,3,4\}$ that are ...
1
vote
1answer
44 views

How many bit strings oft length k have more than one 1?

The question seems rather simple, but I am not able to get a closed formula. e.g. for k=2 it is 1 (11), for k=3 it is 4 (111,101,110,011) I thought that it maybe could be $\frac{1}{2} \cdot 2^k $ ...
1
vote
1answer
24 views

Difference between lines dividing planes and planes dividing space

Let a(n) represent the number of regions that the plane R2 is broken into by n lines (no 2 of which are parallel, and no 3 of which intersect in a single point). Let b(n) represent the number of ...
0
votes
1answer
25 views

simple diving question in combinatorics

So the Discrete Math exam is on friday and i am still very confused with which formula should i was in cases that looks very simillar, there are these 4 question : a) Divide 30 students to 6 ...
1
vote
1answer
49 views

Computing a strange integral

Prove that $(-1)^n \int_{-1}^1 (x^2 - 1)^ndx = \frac{2^{2n+1}(n!)^2}{(2n+1)!}$ This one has me stumped. I've tried the obvious (using binomial theorem and then integrating termwise, or computing the ...
0
votes
0answers
26 views

Different methods used to show the existence of integer solutions

Let $A_{n},B_{n},C_{n}$ be three sequences of positive integers. I want to know the different methods used to show the existence of integer solutions $x$ and $y$ for the equation: ...
0
votes
2answers
32 views

Probability of getting 6 letters right

A secretary writes letters to 8 different people and addresses 8 envelopes with the people's addresses. He randomly puts the letters in the envelopes. What is the probability that he gets exactly 6 ...
-2
votes
1answer
44 views

How many solutions to $|x_1| + x_2 + x_3 = 16$?

I want to know how many solutions there are to the equation $|x_1| + x_2 + x_3 = 16$ with $x_1$ in $\mathbb{Z}$ and $x_2,x_3$ in $\mathbb{N}$. My two attempts to solve this question were: solve ...
0
votes
1answer
22 views

Formula to determine total coin combinations problem?

This question was asked in an aptitude test and was meant to be solved within 2-3 minutes.I know how to solve it by Bruteforce method, but its time-consuming.So, is there any strategic way/shortcut to ...
4
votes
0answers
40 views

Placing $4n$ non-attaking queens of in a $4n \times 4n$ chessboard.

Is it possible to place $4n$ non-attaking queens of in a $4n \times 4n$ chessboard?? I have found that it can be done for $4 \times 4$ chess board and trying to extend it to $8 \times 8$ chessboard ...
0
votes
0answers
15 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
0
votes
2answers
39 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\;.$$
0
votes
0answers
38 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
2
votes
2answers
441 views

To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. [on hold]

I have a question and got strucked on this.. To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. Please guide me ...
2
votes
1answer
28 views

How to prove this result using Permutations? [on hold]

Let A be the set of all $3*3$ skew symmetric matrices whose entries are either -1, 0 or 1. If there are exactly 3 zeroes, three 1's and three (-1)'s, then prove that only 8 such matrices can exist.
1
vote
1answer
98 views

Integral solutions to $x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 210$

Find how many integral solutions and there to the given condition for $x_1 , x_2 , x_3$ and $x_4$ $$x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 210$$ I factored it to $2 \cdot 7 \cdot 5 \cdot 3$, Then how ...