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
1answer
292 views

An attempt to prove Tutte's theorem

I'm studying Tutte's theorem. There is a proof in Graph Theory / Diestel. I took a very short glance at it before trying to prove it on my own. I am giving my proof attempt here with a specific ...
1
vote
2answers
157 views

Selecting balls from bags, with color restrictions

Suppose that I have N bags, each containing balls of a unique colour. What is the maximum number of pairs I can form without replacing the balls back in the bags and with the following constraints: ...
0
votes
1answer
454 views

Finding the number of distinct sub-strings in a binary string.

Whilst solving a question, I have come across a problem regarding the maximal number of possible distinct $k$-length binary sub-strings in an $n$-length binary string. My thought process was that if ...
1
vote
2answers
146 views

Analyzing a recurrence relation given by a Toeplitz matrix

Let $p$ be an odd prime, and $M_p$ be the $p\times p$ Toeplitz matrix over $\mathbb{F}_2$ given by $a_0=a_1=1$ and $a_{-p+1}=1$, e.g. for $p=5$ we have $$M_5=\left[\begin{array}{ccccc} 1 & & ...
0
votes
2answers
4k views

Circular Permutation

Can someone please explain how to solve circular permutation sums. I just cannot seem to understand them. eg. $\text{(4)}$ The number of ways in which $6$ men and $5$ women can dine at a ...
2
votes
1answer
205 views

upper bounds for binomial

I'm trying to calculate the upper bound of the binomial coefficient: \begin{equation} \sum\limits_{j=0}^{k} {n\choose j}<\left( \frac{ne}{k} \right)^k \end{equation} Using binomial theorem and ...
7
votes
5answers
16k views

How to know if its permutation or combination?

I have a question, In how many ways can 6 tosses of a coin yield 2 heads and 4 tails? Now, to me the question clearly seems to be of permutation as they have ...
2
votes
3answers
127 views

Formula to calculate the number of possible positions for $x$ numbers

What formula do I use to calculate the number of possible positions for $x$ numbers? Let's say I have $3$ people in a race. What are all the possible combinations of the order they can finish in? ...
2
votes
1answer
84 views

Is there a word to describe the set of permutations of each member of the powerset of a set?

Just what it says on the tin: For a set, X, is there a word to describe the union of sets of permutations of each member of the powerset of X?
3
votes
1answer
3k views

Permuting 15 books about 2 shelves, with at least one book on each shelf.

From Descrete and Combinatorial Mathematics: An Applied Introduction: Pamela has 15 different books. In how many ways can she place her books on two selves so that there is at least one book on ...
2
votes
0answers
215 views

Cauchy-Binet formula for squares

Using the convention of the wikipedia article, Cauchy-Binet formula states that --for $A, \, n\times m$ and $B, \, m\times n$ matrices-- $$ \det(AB) = \sum_{S\in\tbinom{[n]}m} ...
0
votes
2answers
49 views

How many $k+2$ letter groups in a $n$ letter string

Given an $n$ letter string of identical letters, how many $k+2$ letter words can be formed of adjacent letters? By observing data I came up with n-(1+k), but I'm at a loss for a descent ...
3
votes
0answers
249 views

Sums of rows in the Pascal triangle

Assume for simplicity that when $k>n$ we have ${n\choose k}=0$. It is well-known that $\sum_k {n\choose 2k}=\sum_k {n\choose 2k+1}=2^{n-1}$ , i.e. the sum of the odd places in each row in Pascal's ...
4
votes
3answers
330 views

combinatorics of coin tosses

12 tosses of a fair coin result in an outcome of 6 heads and 6 tails. How many sequences of such a result can have at most 4 successive outcomes of one kind ? I have obtained what I believe is the ...
1
vote
3answers
661 views

Dance couples permutation question

Need some help with this question... At a party 6 boys and 6 girls dance together. Assuming that the classical dance is performed, in which one couple (one boy and one girl), how many couples can ...
2
votes
1answer
111 views

How many numbers $\in [1 .. 10^9]$ that are not of the form $ x^2, x^3$ or $x^5$?

We've started with $x^2$, saying that there are $\sqrt{10^9}$ numbers that are not $\in 10^9$ i'm thinking that if we add $\sqrt[3]{10^9}$ and $\sqrt[5]{10^9}$ to $\sqrt{10^9}$ and subtract them from ...
18
votes
0answers
638 views

$f(x)=\sum_{t}{x \choose t}{n-x \choose k-t}$ - even or odd?

The following function popped in my research: $$f(x)=\sum_{\array{0\le t\le k \\ t\equiv_p a}}{x \choose t}{n-x \choose k-t}$$ Where: n,k are natural numbers and $k\le n$. t is taken over all ...
1
vote
2answers
177 views

unique permutations

Let $X$ be a set of permutations with repetitions of numbers from $1$ to $n$ Let $Y \subseteq X$ be unique if for all $\sigma, \pi \in Y$, $1 \leqslant i < j \leqslant n$ the fact that $\pi(i) = ...
4
votes
1answer
71 views

some question of combination

we know that hilbert seris of n- variables polynomial ring is $\Sigma_{i} \binom{n-1+i}{i}t^{i}$ But, I don't know $\Sigma_{i} \binom{n-1+i}{i}t^{i}=(1-t)^{-n}$. I wonder to prove in detail.
4
votes
2answers
424 views

Algebraic proof of a binomial sum identity.

I came across this identity when working with energy partitions of Einstein solids. I have a combinatorial proof, but I'm wondering if there exists an algebraic proof. $$\sum_{q=0}^N\binom{m + q - ...
3
votes
2answers
339 views

how to visualize binomial theorem geometrically?

How does $ \binom{n}{k} $ 'n choose k' get involved with coefficient of $ (a+b)^n $. Is there any intuitive geometrical picture (interpretation) that it seems ...
2
votes
3answers
1k views

Number of $4 $ digit numbers with no repeated digit.

Number of $4$ digit numbers with no repeated digit is $4536$ $3024$ $5040$ $4823$ Well, I am very much weak in combinatorics. Please help.
2
votes
1answer
69 views

Probabilty of one person getting a pair

A dealer is using a standard deck of 52 cards. One extra ace of spades is put into the deck. So now he got 53 cards in the deck with two ace of spades in total. The dealer deals 4 hands with 5 cards ...
2
votes
0answers
158 views

Is Bingo Games Solved?

So we have numbers 5 rows by 5 columns. Different players have the same table. The numbers on each cell of the tables are different. Different players choose which numbers will be marked. We select a ...
0
votes
1answer
78 views

Solution for assigning independent tasks to independent individuals

I have $n$ tasks that I wish to delegate to $m$ independent individuals, where $m$ is a factor or divisor of $n$. Each of the tasks $T_{1} ... T_{n}$ is independent. From the following two extremes, ...
3
votes
1answer
188 views

non existence of $K_{r,r}$ in a given graph on any number of vertices

I need to prove that: for every r>1 there exists $c>0$, s.t for every $n$, there exists some $G$, a graph on $n$ vertices, with average degree $cn^{1-\frac{2}{r}}$ (or above), s.t ...
1
vote
1answer
89 views

Combination of cards

From a deck of 52 cards, how many five card poker hands can be formed if there is a pair (two of the cards are the same number, and none of the other cards are the same number)? I believe you ...
0
votes
1answer
67 views

Formalize as combinatorics problem (get all sets that boolean sum == (1,1,1))

I have such a problem: there are several boolean tupels (properties of some objects) K1 = (0, 1, 0) K2 = (1, 1, 0) K3 = (1, 1, 0) K4 = (0, 0, 1) K5 = (0, 0, 1) I ...
0
votes
1answer
94 views

What is the name of the symmetry of a bracelet transposition?

Take a bracelet with colored beads on it. Normally two bracelets belong to the same equivalence class under rotations and reflections. For an example, consider the bracelet denoted by the word ...
4
votes
0answers
276 views

Combinatorics and graph theory - counting connected graphs

We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...
1
vote
1answer
119 views

Pigeon principle question: Nine points in a diamond

A diamond (a parallelogram with equal sides) is given, and its sides are 2 cm long. The sharp angels are 60 degrees. If there are nine points inside the diamond, prove that there must be two of them ...
2
votes
1answer
878 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
2
votes
2answers
139 views

Understanding Formula for Sampling without Ordering and without Replacement

Alright, so I've been working through a couple combinatorics problems and I'm having trouble understanding the underlying reason for why a formula is written in a certain way. So here's the problem: ...
11
votes
3answers
543 views

Penguin Brainteaser : 321-avoiding permutations

There are $k$ penguins, $k\ge 3$. They are all different heights. How many ways are there to order the penguins in a line, left to right, so that we cannot find any three that are arranged tallest to ...
2
votes
1answer
73 views

Every $2k$-regular contains a 2-factor

I need to prove that given a graph which is $2k$-regular, I can find a 2-factor. Meaning, There is a sub-graph of the above graph, which contains all vertices, and is 2-regular. I must say I have no ...
4
votes
1answer
441 views

Definition of a contractible simplicial complex without appealing to topological realization

Let $\Delta$ be a simplicial complex. I believe the standard definition of $\Delta$ being contarctible is if the topological realization $|\Delta|$ is contractible. However, I am seeking a ...
30
votes
3answers
1k views

Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
3
votes
0answers
211 views

Size of an intersection with a randomly chosen subset

I'm hoping for some help with this excericse in probability. Let $V$ be a set and let $V'$ be a randomly chosen subset of $V$ such that each element belongs to $V'$ with probability $p$. Now, ...
2
votes
3answers
79 views

Combinatorics: endless series

I have the following problem: In an urn, you have 1 blue and 9 white balls. You pull out one ball a time; if it is the blue one, you win. If it it is white, you throw it back in and pull again. ...
7
votes
2answers
332 views

Need help in determining where this pascal's triangle-like sequence comes from.

I have a very interesting problem in that a program that I am running has generated a sequence of numbers that act like the pascal's triangle but have somehow built more structure into it. I have been ...
5
votes
3answers
338 views

combinatorics: The pigeonhole principle

Assume that in every group of 9 people, there are 3 in the same height. Prove that in a group of 25 people there are 7 in the same height. I started by defining: pigeonhole- heights. ...
1
vote
3answers
194 views

Probability of sharing cards drawn from different decks?

I have been struggling with the following problem, which I have been trying to solve combinatorially, but without much success. Suppose n players each have a deck of cards. Each player randomly draws ...
2
votes
1answer
61 views

Computing probabilities involving committees

A committee consisting of 6 members is randomly selected from 25 students, 5 teachers, and 10 parents. I wish to find the following: (i) the probability of having no teacher on the committee (ii) ...
3
votes
2answers
146 views

Counting matrices over $\mathbb{Z}/2\mathbb{Z}$ with conditions on rows and columns

I want to solve the following seemingly combinatorial problem, but I don't know where to start. How many matrices in $\mathrm{Mat}_{M,N}(\mathbb{Z}_2)$ are there such that the sum of entries in each ...
2
votes
1answer
67 views

Figuring out probability in a sequence of coin tosses

I have a question I have worked out and I would like to check my solution. I am told that 4 fair coins are tossed in succession. I am to find the probability of getting 4 tails given that the first 2 ...
2
votes
1answer
318 views

Proving a function satisfies the binomial recurrence relation and that it equals $\binom{n-k+1}{k}$

I have the recurrence relation $g(n,k)=g(n-2,k-1) + g(n-1,k)$ for all $k\geq1$ with the boundary conditions $g(n,k)=0$ if $n<2k-1$ and $g(2k-1,k)=1$ What I'm trying to do is define a new function ...
1
vote
1answer
360 views

How to write a combinations formula for this?

I have 8 distinct elements. Each set has 4 pairs from the 8 elements above. How many such distinct sets are possible? e.g. 8 elements - 1,2,3,4,5,6,7,8 example set - 1,2;3,4;5,6;7,8 the ordering of ...
1
vote
2answers
2k views

how many 5-digit numbers satisfy the following conditions

How many five-digit numbers divisible by 11 have the sum of their digits equal to 30? I am able to get the 5-digit numbers divisible by 11 and I am also able to get the five-digit numbers whose sum ...
2
votes
1answer
101 views

Liouville's theorem via contraction mappings

Let $f$ be a function that maps $\mathbb{Z}^2$ to $\mathbb{R}$ and consider the operator $T$ which replaces the value of $f$ at $(i,j)$ by the average of the values of $f$ at its four neighbors (left, ...
10
votes
3answers
308 views

Nicer expression for the following differential operator

I have the following sequence of differential operators: $$D_n = \underbrace{t \partial_t t \partial_t \dots t \partial_t}_{\text{$n$ times}}.$$ Is there any expression involving a sum of "normal" ...