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
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 ...
2
votes
1answer
21 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
40 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
16 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
20 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
61 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
23 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 ...
1
vote
1answer
28 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
27 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 ...
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 ...
8
votes
3answers
785 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
11 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
25 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
36 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
30 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
21 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
24 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
29 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
68 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
29 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
25 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
28 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
48 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
54 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
26 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
58 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
27 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
35 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
48 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
33 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
44 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
16 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
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\;.$$
0
votes
0answers
39 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
449 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
29 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
105 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 ...
3
votes
2answers
55 views

Number of unit squares that meet a given diagonal line segment in more than one point

Let $l$, $b$ be positive integers. Divide the $l \times b$ rectangle into $lb$ unit squares in the usual manner. Consider one of the two diagonals of this rectangle. How many of these unit squares ...
1
vote
1answer
86 views

let s be a set with N elements and A1,…,A101 be 101 (possibly not disjoint) subsets of S

So the question I'm having problem with is the following: let s be a set with N elements and A1,...,A101 be 101 (possibly not disjoint) subsets of S with the following 5 properties: each elements ...
0
votes
2answers
36 views

What is the minimum number of painted edges in the chessboard?

Some edges of the squares of an 8×8 chessboard are painted red. What is the minimum number of edges that must be painted, so that each square has at least two red edges? What is the meaning of this ...
3
votes
1answer
26 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...
0
votes
2answers
26 views

5 People roll a dice and flip a coin [on hold]

Each of 5 people flip a coin and roll a dice (six sides). I know the total number of possibilities equates to $6 \times 2$ because the dice has 6 options, and the coin has 2 options. As a result we ...