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
0answers
9 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( ...
1
vote
1answer
9 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
12 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
2answers
44 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
10 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
23 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$ ...
-1
votes
0answers
11 views

Increase or Decrease in Cardinality [on hold]

Just a quick question i have a test coming up and this is a concept I still dont get if I were to have 2 varibles that countable) x and y, and I combine 2 seperate set such as (XY)^i and (X&Y)^i ...
0
votes
1answer
18 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
28 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 2^k/2 but I don't know how ...
1
vote
1answer
18 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
23 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
45 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
21 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
29 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
0answers
14 views

What is the solution to the equation …? [on hold]

I want to know how many solutions to the equation |x1| + x2 + x3 = 16 ? while x1 in Z. and x2,x3 in N
0
votes
1answer
20 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 ...
3
votes
0answers
35 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
13 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
36 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
35 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.
1
vote
2answers
426 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
97 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 ...
2
votes
2answers
48 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
51 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
35 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
25 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
23 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 ...
1
vote
1answer
33 views

pairwise balanced design has block size related to the number of elements.

A pairwise balanced design is a set of elements $X$ and set of blocks $A$ such that each pair of elements of $X$ occurs in exactly $\lambda$ blocks. I am trying to solve the following problem: Given ...
1
vote
1answer
25 views

Generating Functions for Multinomials

Find a generating function $(x_1, x_2, ... , x_m)$ whose coefficients of $x_1^{r_1}x_2^{r_2} ... x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ candies of type $1$, $r_2$ ...
3
votes
0answers
46 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
1
vote
1answer
18 views

Find nth integer composition

I am processing compositions of integer N in K groups in a loop - for bigger K, N, number of compositions is enormous (1,731,030,945,644 for N = 100, K = 10). I would like to split my loop into more ...
0
votes
0answers
22 views

$10$ people out of a population of $n$ people take a slice of $10$ different cakes. They are not allowed to share. In how many ways can this occur?

For those confused by the title: There are 10 different cake slices available, 10 people chosen from a population of size n are allowed to pick one slice that has not already been chosen and eat it. ...
2
votes
3answers
63 views

n distinguishable balls into n boxes

We have n distinguishable balls (say they have different labels or colours). If these balls are dropped at random in n boxes, what is the probability that: 1- No box is empty? 2- Exactly one box is ...
2
votes
1answer
30 views

Remove minimal number of elements

Given the numbers $ 1,2,..,2n + 1 $ , $ n > 0$ , remove as few numbers as possible so that among the remaining numbers no number is equal to the sum of two other numbers. After removal of first ...
0
votes
1answer
48 views

How many 10 digit numbers are there so the sum of the digits is $2$?

How many 10 digit numbers are there so the sum of the digits is $2$? $abcdefghij$ is the 10 digit number. By default, $a=1$ is a must. $= 1bcdefghij$ Now we need: $bcdefghij = 1$ How can I solve ...
0
votes
2answers
27 views

Histogram of duplication in n choose k

Imagine having 17 balls to distribute to 4 people. One algorithm for distributing these balls is to give each ball to one out of the four randomly. This means, in an extreme case, it is possible for 1 ...
0
votes
1answer
39 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
0answers
19 views

Generalized Mobius Inversion formulae

I am having as problem with inverting a relation of the form $f(i)=∑_{j=0}^ig(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 could ...
1
vote
1answer
21 views

Split n balls to k boxes

I have $n$ different balls $(1,2,..., n)$ and $k$ different boxes $(1,2,...,k)$. I want to put all balls to boxes, but if ball i has smaller nuber than j (i < j) than ith ball must be put to box ...
1
vote
3answers
41 views

How many ways there are?

I cant solve the following problem. In how many ways we can divide 6 balls between 3 children if every children must receive at least 1 ball. I don't understand the problem. Is it permutations or ...
0
votes
0answers
17 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
1
vote
0answers
20 views

Question regarding a proof of the Combinatorial Nullstellensatz

N. Vishnoi has provided a slick proof of the combinatorial nullsetellensatz at http://research.microsoft.com/en-us/um/people/nvishno/site/publications_files/valon.pdf . The part that I am not ...
2
votes
2answers
48 views

Determine the number of integer solutions of $x_{1}+x_{2}+x_{3}+x_{4}=32$ where $x_{1},x_{2},x_{3}>0, \space\space 0<x_{4}\leq25$.

Determine the number of integer solutions of $$x_{1}+x_{2}+x_{3}+x_{4}=32,$$ where $x_{1},x_{2},x_{3}>0, \space\space 0<x_{4}\leq25$. My approach is in finding all the solutions with the ...
7
votes
3answers
642 views

Is every arrangement reachable by shuffling this way?

Suppose we have a vertical stack of $n$ distinguishable coins, each of which is either heads-up or tails-up. Let a shuffle be the following procedure: divide the stack at will into a top- and ...
3
votes
0answers
35 views

Points Distributed evenly around a circle: how many points are in each region?

A circle of circumference $2$ is split into three arcs of length $\frac{2}{3}$ (so the regions are $[0,\frac{2}{3})$, $[ \frac{2}{3},\frac{4}{3})$, $[\frac{4}{3},2)$, $2$ identifies with $0$) and ...
0
votes
1answer
51 views

Generating function $D(x) = (1 + x)(1+x^2)(1+x^3)\cdots$ [on hold]

Let $$D(x) = (1 + x)(1+x^2)(1+x^3)\cdots $$ 1) What is the inverse function of $D(x)$? 2) What sequence is generated by $D(x) $ Please don't vote down, the subject is complicated for me. Sorry ...
0
votes
1answer
25 views

Partitioning elements into sets

How many ways are there to partition $n$ unique elements into $2$ sets? What about for $k$ sets? I am specifically interested in how to calculate this for varying values of $n$. Moreover, what if ...
1
vote
0answers
18 views

Given a specific rational number, is there a way to find an n and k for the binomial coefficient that will evaluate to it? [duplicate]

Looking at Pascal's triangle, it looks as though all rational numbers can also be expressed as binomial coefficients. Given a rational integer, is it possible to calculate n & k for the binomial ...
1
vote
2answers
32 views

Factorial formula problem [duplicate]

Prove that $(n-r)!(r!)$ divides $ n! $ i know its a factorial formula and it might be easy but i stuck .I tried induction to $n$ or analyzing the factorials but im missing something