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.

learn more… | top users | synonyms (4)

2
votes
0answers
162 views

Minimum number of stickers required for 3x3 Rubik's Cube

Lately, the stickers on my V-Cube have been peeling off, and I became curious: what is the minimum number of stickers I would actually need in order to represent each unique configuration? I have but ...
0
votes
3answers
108 views

Probability of Permutations/Combinations

How do you set up the formula for the probability of a permutation/combination? Question: If you have a group of candy with $2$ Snickers, $4$ Kit Kats, and $2$ Butterfingers and you take two pieces ...
2
votes
1answer
336 views

Permutations and number of permitted combinations three percentages which must add up to 100%

is there a simple way to find the number of combinations of three percentage values with discrete step sizes which add up to 100%? Example: ...
0
votes
1answer
124 views

permutations indistinguishable objects and groups

There is a group of 10 objects, 2 red, 3 blue and 5 green. If the 5 green objects should always be placed together, in how many ways we can put them on a line. I did this: As 5 places are occupied by ...
0
votes
3answers
84 views

What is the probability that either 1 or 49 is in the winning numbers of a Lotto game?

In a simple Lotto game you have 49 numbers (1, ..., 49). 6 of them get drawn (without multiples, order is not important). What is the probability that either the number 1 or number 49 get drawn (but ...
2
votes
1answer
55 views

counting hands shake

Mr. and Mrs. Brown gave a party for their friends they have not seen for a long time. Three couples came. During the party, some of the people were so happy to see each other again, that they even ...
4
votes
1answer
105 views

Choosing subset of vertices connected to whole graph

Consider a simple graph $G$ with $n$ vertices. For any two vertices, either they are connected by an edge, or there is a third vertex which is connected to both of them by an edge. (It is possible ...
1
vote
2answers
259 views

52-Deck 3 Cards Drawn Possible Combinations Question

I have a HW problem I'm trying to pin down and I think I'm confusing myself... Question: In a card game w/ a standard 52 card deck, a hand is a set of 3 cards. Count the # of hands that are... a) ...
2
votes
2answers
55 views

the least steps to remove all pebbles on table

On the table there are 100 bags of pebbles that contain 1, 2, 3, 4, ...., 100 pebbles respectively. In one step you are allowed to reduce the number of pebbles of any number of the bags as long as you ...
3
votes
1answer
250 views

What is a good combinatorics text for someone studying for the Math GRE Subject Test?

I have NEVER taken a combinatorics course, outside of what one covers in a calculus-based probability course. I would be interested in knowing what would be a suitable combinatorics text for ...
1
vote
0answers
64 views

How do you count the number of solutions to simultaneous boolean equations?

How do you count the number of solution that satisfy the following simultaneous equations ($x_i = \{0,1\}$: $$x_1 \oplus x_2 \oplus x_4 \oplus x_5 = 0$$ $$x_1 \oplus x_3 \oplus x_4 \oplus x_6 = 0$$ $$...
5
votes
1answer
235 views

Proof of Faà di Bruno's formula using a convolution identity for Bell polynomials?

I have noticed there is an identity for Bell polynomials that can apply of Faà di Bruno's formula. This is a convolution identity that states: $$ (x \ast y)_n = \sum_{j=1}^{n-1} {n \choose j} x_j y_{n-...
0
votes
1answer
81 views

Meaning of “Up to isomorphism”

I saw in my graph theory notes this statement "Up to isomorphism, there is one and only one $K_4$". What does the phrase "up to isomorphism" mean?
1
vote
1answer
34 views

Evaluating the boolean sum $\sum_{x_1, x_2, x_3, x_4, x_6, x_7} \neg(x_1 \oplus x_4 \oplus x_3 \oplus x_6) \neg(x_4 \oplus x_3 \oplus x_2 \oplus x_7)$

Say that we have the following boolean function function ($x_{i} \in \{0,1\}$): $$f = \sum_{x_1, x_2, x_3, x_4, x_6, x_7 \in \{0,1\}^6} \neg(x_1 \oplus x_4 \oplus x_3 \oplus x_6) \land \neg(x_4 \...
1
vote
3answers
63 views

Probability Urn Group Problem

my group and I are having trouble figuring out how to do this. For some reason I have an urn that contains 10 coins. 3 of the coins are blue on one side and red on the other, 3 of the coins are blue ...
1
vote
0answers
49 views

combinatoric problem - how many …

There is a box with the numbers from 1 to 60 and another box with the numbers from 1 - 60 too. There are 60 students. Each of these students go to both box and pick up a number. If the product of ...
1
vote
1answer
102 views

$n!$ as a sum of $n$ positive integers

We partition $(n-1)!$ into $n-1$ parts in the following way. Consider a permutation $(a_1,a_2,\ldots,a_n)$ of $(1,2,\ldots,n)$. We say that $a_k$ dominates its predecessors if $a_j<a_k$ for $j<k$...
1
vote
0answers
15 views

Sliding dominoes to transfer empty cell

Let $n\geq 3$ be an odd positive integer. An $n\times n$ board is covered by $1\times 2$ dominoes, so that only one cell remains uncovered, and that cell is at a corner. By sliding dominoes on the ...
13
votes
1answer
284 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
2
votes
3answers
90 views

Proving that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$

I have difficulties understanding the proof given below showing that there exist 2 distinct vertices $u,v$ in $G$ such that $d(u) = d(v)$ where $G$ is a non-trivial graph. Proof: It's clear that $0 \...
0
votes
1answer
35 views

randomly putting 77 balls in 999 numbered boxes

77 balls are distributed randomly to 999 numbered boxes. I want to know the probability that 7 balls total are in the boxes 1-11 in two cases: (1) each box may contain arbitrary numbers of balls and (...
2
votes
0answers
118 views

A hard combinatorial identity

I try to prove the following hypothesis $$\sum_{i=0}^{min\{k, n-1\}}(-1)^i { n+i-1 \choose i}{{n+k-2} \choose k-i} {n+2k-i-1 \choose 2k}= \sum_{i=0}^{\min\{k, n-3\}}{{n-3} \choose i}{{n-2} \choose i} {...
1
vote
0answers
40 views

unique cube arrangments

i have received this math riddle which i cannot solve, the riddle: given a set of cubes, a unique shape is any shape that was created joining cubes sides together and does not match any previously ...
2
votes
1answer
70 views

Problem in understanding division into groups and division among persons.

My book describes these methods as under: The number of ways in which $m.n$ different things can be equally divided into $m$ groups is $$ \frac{(mn)!}{(n!)^{m} . m!}$$ . And the number of ways $...
1
vote
1answer
65 views

Multidimensional multiple knapsack? How to distribute items into containers

I am looking for a problem description which covers the following optimization problem: Given a small finit set of items, each with four dimensions (width, height, length, weight) Given an infinit ...
0
votes
0answers
138 views

Euler Characteristic of the Barycentric Subdivision of an $n$-Simplex.

The Euler Characteristic of a Simplicial Complex is defined to be $\sum (-1)^i\alpha_i$, where $\alpha_1$ is the number of $i$-simplices in the complex. Using this formula, we can see that the Euler ...
1
vote
1answer
307 views

Simplifying combinations with sigma notation

I'm currently working on a recurrence relation question and have it simplified as so $$\sum_{n \geq 0} \binom{n+2}{2}z^{n+1}$$ I'm having difficulty simplifying it further to come up with a solution ...
2
votes
4answers
728 views

Number of length $8$ binary strings with no consecutive $0$'s

How many $8$ bit strings are there with no consecutive $0$'s? I just sat an exam, and the only question I think I got wrong was the above(The decider for a high-distinction or a distinction :SSS) I ...
5
votes
2answers
62 views

Largest subset with no pair summing to power of two

For positive integer $n$, define the set $A_n=\{0,1,\ldots,n\}$. What is the size of the largest subset of $A_n$ such that the sum of any two (not necessarily distinct) elements in it is not a power ...
1
vote
1answer
46 views

Inclusion-exclusion principle (?) in a counting problem

A group of pre-school children is drawing pictures ( one child is making one picture ) using 12-colours pencil set. Given that (i) each pupil employed 5 or more different colours to make his drawing; ...
5
votes
4answers
576 views

Give a combinatorial argument

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$ Not quite where to starting proving this ...
3
votes
1answer
52 views

How many ways are there to assign 5 points into three scores with a range of -1 to 4?

You have 5 points to assign between 3 scores; that is to say, the three scores must total to 5 exactly. A score may go as high as 4 and as low as -1. How many different ways are there to assign these ...
1
vote
1answer
34 views

multicombinations with further requirements

I am trying to find the number of ways to distribute $n$ balls into $k$ boxes. The boxes are distinguishable. The balls are not. $\binom{n+k-1}{k-1}$ is the number of all possible distributions. I am ...
1
vote
3answers
113 views

Determine the Number of Integer Solutions $x_1 + x_2 + x_3 + x_4 = 32$ with restrictions

The Question My Problem Part a is straight forward, just $C(35,32)$. I'm having a little difficulty with the restrictions and understanding what they mean. $x_1 > 0$ means we shouldn't have any ...
0
votes
1answer
45 views

One set dominating another in tournament

Consider a tournament with $799$ contestants. Each contestant plays against all other contestants exactly one; there are no draws. Prove that there exist two disjoint groups $A,B$, of $7$ contestants ...
1
vote
1answer
482 views

Number of Necklaces of Beads in Two Colors

I was reading this paper, and came across an equation which gives an expression for the number of necklaces of beads in two colors, with length n. $Z_n = \dfrac{1}{n} \displaystyle \sum \limits_{d \...
0
votes
0answers
48 views

How many ways are there to go from $A$ to $B$?

How many paths are there to go from $A$ to $B$ in the following figure: Conditions: I'm not able to touch $C$ I can go up, down, left or right I'm not able to pass a line twice I couldn't ...
1
vote
1answer
52 views

Density of the set of the fractional part of sufficiently large irrational numbers in the unit interval $[0,1]$

Is it true that $\forall x \notin \mathbb{Q}: x>1$, the set $A=\{ \operatorname{frac}(x^n): n \in \mathbb{N} \}$ is dense in $[0,1]$?
1
vote
2answers
77 views

How many one to one correspondences are there from $A=\{A_1,A_2,A_3,A_4,A_5\}$ to $B=\{B_1,B_2,B_3,B_4,B_5\}$ such that…

I got this problem: Let $A=\{A_1,A_2,A_3,A_4,A_5\}$ and $B=\{B_1,B_2,B_3,B_4,B_5\}$ be two sets. How many one to one correspondences (one to one and onto functions) from $A$ to $B$ are there that ...
1
vote
1answer
94 views

Number of spanning trees for these 2 figures

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar ...
1
vote
1answer
77 views

Use of model theory in flag algebras

I need to learn about Razborov's "flag algebras" (see http://bit.ly/1u1a1NB) to solve a problem about graphs. Flag algebras are a very general new algebraic tool for studying combinatorial structures. ...
1
vote
1answer
169 views

Number of spanning trees of this graph

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks! Notes: Just in case anyone was ...
1
vote
2answers
1k views

Permutation question on alphabets

Ten different letters of alphabet are given, words with 5 letters are formed from these given letters. Then, the number of words which have at least one letter repeated is Well I do understand some ...
0
votes
1answer
35 views

Enumeration of integers are in increasing order which have gaps

I want to solve the following: Calculate the number of ways of selecting five distinct integers $x_1,x_2,x_3,x_4,x_5$ where $0\leq x_1 \lt x_2 \lt x_3 \lt x_4 \lt x_5 \leq 20$ I think this may ...
2
votes
2answers
62 views

Interesting combinatorics

There is $n*n$ square grid. How many ways to fill it with $1$ and $0$ do we have, in case the sum in every row and every column should be even. The problem seems to be easy, but after some time and ...
1
vote
4answers
51 views

Arithmetic of a combinations formula

I am trying to study, and I'm not quite sure how: $$ \binom{5}{3} \cdot \binom{7}{3} = 350 $$ From my understanding the formula is $$ \binom{n}{r} = \frac{n!}{r!(n-r)!} $$ Therefore: $$ \binom{5}...
0
votes
0answers
33 views

Number of permutations if every element may appear in certain distance from its initial position

Suppose i have an $n-$elements array. I want to count number of permutations for which element $a_i$ allowed to appear in range $i-k, \dots, i+k,$ so $2k+1$ positions available after permutation has ...
1
vote
1answer
42 views

Every binary number coincides in more than half of bits

Let $n\in\mathbb{Z}^+$. We would like to pick some binary numbers of length $2n+2$ so that any binary number of length $2n+2$ coincides with one of the picked numbers in at least $n+2$ positions (that ...
1
vote
1answer
48 views

Сombinatorial identity

I try to prove the following hypothesis $$\sum_{i=0}^k \frac{(-1)^i (n+i-1)(n+k-2)!}{i!(k-1)!(n-1)!}{{n+2k-i-1} \choose {2k}}=\frac {{n+k-1\choose k}{n-2+k\choose k}}{k+1}.$$ In the Maple: gip:=proc (...
0
votes
1answer
69 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...