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
33 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
21 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
20 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
24 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
0answers
25 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
259 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
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
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
24 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
14 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
25 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
21 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
57 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
40 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
21 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
11 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
12 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
17 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
24 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
29 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
771 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
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
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 ...
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
66 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
26 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
27 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
46 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
24 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\;.$$