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)

0
votes
0answers
6 views

A combinatorial proof by tesselation of the plane.

Some days ago the following problem was posed in the site: given a set of $N$ points in the plane such that for each pair of points $p,q$ we have $\lVert p-q\rVert >1$, prove there is a subset of ...
1
vote
0answers
11 views

What is the number of set partitions of {1,1,2,2,3,3}

It must be less than B_6 (where B_6 is the Bell number of 6) since the elements are "duplicated". I would most appreciate a generating function that gives the number of set partitions of {1,1,2,2, ...
1
vote
1answer
28 views

Counting number of bijections

The question is: Let $S = \{a,b,c,d\}$ and let $X : = \{f\colon S \to S | f \, \, \text{is bijective and } f(x) \ne x \, \, \text{for each}\, \, x \in S \}$. What is $|X|$? Is there a simple ...
2
votes
0answers
22 views

An easy (or not?) collection of proper sets .

Let $S$ be a finite set. We are given $k$ rows and in each row we have two subsets of $S$ which we call them $A_i$, $B_i$ (for the $i$th row, with $i\leq k$). $A_1$ and $B_1$ $A_2$ and $B_2$ . . ...
0
votes
2answers
35 views

Can we obtain the pair $(1,50)$ with these following operations?

It's a problem from some russian competition: We're given a card with two positive integers $(a,b)$ and we have tree machines which generate another card from the one we insert on it(I assume we ...
1
vote
2answers
50 views

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the ...
-1
votes
1answer
19 views

How many structurally different latin squares of order 5 do exist?

I know the number of latin squares order 5 which start with 1 2 3 4 5 in the 1st row or column, that is 1344, but the greater part of that number consists of structural duplicates of each other. So, I ...
5
votes
0answers
22 views

Partition Of Graph's edges Into 3 Groups

Let $G = (V, E)$ be a bipartite graph. Prove that there is a partition of the set of edges $E$ into 3 disjoint parts: $E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, so that for ...
2
votes
1answer
36 views

How many 3 letter words can you form from 'EEAAP' [duplicate]

How many 3 letter words can you form from 'EEAAP' I think the answer is ${3\choose 3} * 3! + {2\choose 1} * 3 + {2\choose 1} *3=18$. Is this right? ${3\choose 3} * 3!$ = You pick all ...
2
votes
0answers
38 views

How many ways can you choose team of 5 people out of 7 men and 6 women in which there are at least 3 men?

I am confused by this question. I solved it by selecting 3 men first out of 7 men and then selecting 2 people out of 10 remaining person ( 4 men and 6 women ) . So my answer is C(7,3) * C(10,2) = ...
3
votes
1answer
27 views

Probability of the card following first ace being ace of spades or two of clubs

I am learning probability from Scheldon Ross' book. The question reads like this: A deck of 52 playing cards is shuffled, and the cards are turned up one at a time until the first ace appears. Is ...
0
votes
2answers
35 views

Probability and Combinatorics

I am trying to solve example 4.15 here but think the total number of outcomes in the solution is incorrect. This is my reasoning. We have 3 that qualify as best three, say BBB, and 2 as bad say OO. ...
0
votes
1answer
16 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
0
votes
1answer
35 views

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$?

Why is $^nC_r$ not equal to $ ^{n-k}C_{r-k}\times ^nC_k$ ? I know that by simplifying, we can obviously see that they are unequal. But consider this: Where am I going wrong?
2
votes
0answers
30 views

Probability of a run of *k* or more of a subset of categories in *m* multinoulli trials?

Given a multinoulli distribution of categories $(C_1,C_2,...,C_n)$ with associated probabilities $\left\{p_1,p_2,\ldots ,p_n\right\}$ with $\sum _{i=1}^n p_i=1$, is there a tractable way to get the ...
3
votes
2answers
50 views

Permutations minus Transpositions

I want a formula that allows me to find all the permutations in $S_n$ (which is the set of all the integers from 1 to $n$) which don't contain a transposition. Attempt: Lets call $g(n)$ the ...
3
votes
2answers
41 views

Permutation count of AABBC

Given a string: $AABBC=A^2B^2C^1$ I am trying to find the Total Permutations (this may be incorrect): $\dfrac{5!}{2!\cdot2!}=30$ My question is how would I find the partial sums (perhaps the ...
1
vote
0answers
30 views

Number of different keyboard layouts?

Pretty really stupid question probably, but if I would have a keyboard with the 30 main keys (A-Z,. shift) in how many different keyboard arrangements could I put them provided their possible ...
1
vote
0answers
15 views

Representing numbers by quasilexicographic ordered strings, formula for size of conversion between different alphabets

Let $X_r = \{ 0, 1, \ldots, r-1 \}$ and $X_b = \{ 0, 1, \ldots, b-1 \}$ be two finite alphabets with order's given by their numerical value. Consider the quasilexicographic (or shortlex) order on ...
1
vote
2answers
54 views

How many two letter words can be formed from 26 English letters?

There are 26 English letters. From layman approach, How can one calculate the possible two letter words from these 26 English letters?
1
vote
1answer
27 views

Diagonalizing a matrix arising in a simple combinatorial situation

Maybe I'll return to this question a few hours from now and possibly even post an answer then. This concerns a matrix that I described in this answer. Start with a $\dbinom n2\times n$ matrix $B$ ...
0
votes
0answers
58 views

Zero-Sum Partitions of Nonzero Elements of a Ring

In this question, rings are not necessarily finite nor do they need to be unital (i.e., the multiplicative identity may not exist). Although I shall exclusively discuss finite commutative unital ...
3
votes
2answers
77 views

Combinatoric Birthday Paradox

There is likely a closed form solution for this problem but it's had me puzzled for days. This is about a variant on the classic birthday paradox. To recap, the birthday paradox is where given only 23 ...
0
votes
2answers
28 views

Why is this counting function finite? (It is used Probability)

Why is this counting function finite? I don't understand this interpretation of the author. Can you explain more about this? Please.
0
votes
3answers
52 views

Evaluate: binomial theorem

Show: $$(x+1)^m=\sum_{k=1}^{m}\binom{m}{k}x^k$$ Can somebody help me in showing the above stated problem?
1
vote
0answers
54 views

Is it possible to solve sudoku without backtracking?

I occasionally solve sudoku puzzles on smartphone in spare time. My approach is based on the belief that at each stage in solving a sudoku puzzle there is at least one cell where there in only one ...
0
votes
2answers
54 views

How many permutations of the word TOMORROW can be made if the O's can't be together?

I'm trying to answer this question. This is my attempt of solution: First we distiguish the O's and R's, then we have the word: $TO_1MO_2R_1R_2O_3W$. We have $8!-7!\cdot3!-6!\cdot 3!$ different ...
4
votes
0answers
63 views

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\Delta$ on the vertex set $\{x_1,\dots,x_n\}$ is shellable if the facets of $\Delta$ can be ordered, say $F_ 1 , . . . , F _s$, such that for all $1 \leq i < j ...
2
votes
1answer
30 views

Reference for a combinatorial theorem

Is there a reference for this theorem https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics? I am unable to locate a reference. Google search does not spot this particular theorem well.
2
votes
5answers
1k views

Hot dog combinatorics

A hot dog stand has 12 different toppings available. How many different kinds of hot dogs can be made, assuming the order of the toppings does not make a difference. I believe the correct answer is ...
1
vote
1answer
31 views

A question on arithmetic progressions

Is it true that for every $n \in \mathbb N$ , $\exists N \in \mathbb N$ such that for any subset $A \subseteq \{1,2,...,N\}$ , either $A$ or $\{1,2,..,N\} \setminus A$ contains an arithmetic ...
3
votes
3answers
35 views

Combinatorics Question - Permutations and Supersets

I had a question that seems pretty straightforward, but I can't seem to wrap my mind around it. Let's say I have a bunch of elements in a set. {A, B, C, D, E}. How many permutations are there of ...
1
vote
1answer
22 views

How many option are there to divide n people into any number of groups of any size?

I found only something like this: $$f(0) = 1$$ $$ f(n) = \sum_{i=0}^{n-1} \binom{n-1}{i} * f(i) $$ Now I wonder if there are other (faster) ways to calculate this.
2
votes
2answers
50 views

Count all possible combinations

I want to check how many combinations of $2$ numbers I can generate from $20$ different numbers when the same number can be picked twice. I calculated it like this and answer is $20 \cdot 20 =400$. Is ...
1
vote
0answers
61 views

Find the number of “p-safe numbers”

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is ...
1
vote
0answers
51 views

Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any ...
1
vote
0answers
33 views

Number of triangles possible in android lock patterns?

I recently starting using the patternlock on my android phone and i play around with it a lot, just drawing lines until im locked out for 30 secs. I thought i'd make it into a pointless game of ...
0
votes
3answers
38 views

Why is it true that $(a_1, a_2, \dots, a_r) = (a_1, a_r)(a_1, a_{r-1})\dots(a_1, a_3)(a_1, a_2)$?

In the theory of permutation, a $r$-cycle $(a_1,a_2,...,a_r)$ is defined in the following way: Start from $a_i$, a permutation function $f$ sends $a_i$ to $a_{i+1}$. When $i=r, a_i \text{ will be ...
0
votes
0answers
29 views

Let $T$ be the set of all positive integer divisors of $2004^{100}$. Size of largest subset $S$ of $T$ such that no element in $S$ divides another?

I am getting an answer slightly over $100^2$. Is this right (working below), or is there a better way of selecting elements of S? The following question appeared on the 2004 Canada National Olympiad: ...
9
votes
1answer
169 views
+100

Help with binomial identity

In my work, I was led to the following identity. I would be grateful if someone could provide an easy proof. Suppose $n, d, k \in \mathbb{Z}$, and $d \geq 0$. $$ \sum_{j = 0}^d (-1)^{d-j} \cdot ...
0
votes
1answer
43 views

Probability problem 1

I just wanted to double check to see if I'm doing this problem correctly. 3 kids (Alice, Bob, and Carol) have to divide 15 different toys among themselves in a way that each kid gets 5 toys. How many ...
6
votes
5answers
137 views

Show that $(1+p/n)^n$ is a Cauchy sequence for arbitrary $p$

It is a generalization of this question. I am looking for a similar derivation as in here. Can we prove that $(1+p/n)^n$ is a Cauchy sequence for any $p \in [a, b]$ by showing that $$ \Bigg| \left( ...
0
votes
0answers
34 views

How many distinct non-negative integer solutions to $x+y+z=S$ are there, without variable naming?

How many distinct non-negative integer solutions to $x+y+z=S$ are there, without variable naming? Any two solutions $(x_0,y_0,z_0)$ and $(x_1,y_1,z_1)$ are considered equivalent if $x_0,y_0,z_0$ can ...
1
vote
1answer
53 views

Block of integers: Divisibility

Let a < b be natural numbers. Prove that every block of b consecutive natural numbers contains two distinct elements whose product is divisible by ab. (I've proved this) Suppose now a < b < ...
1
vote
2answers
35 views

How to show that this interesting difference of products is $O \left( \frac{1}{n^2} \right) $

Let $k \leq n$. Consider the following difference of products: $$ \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n+1} \right) - \prod_{i=1}^{k-1} \left( 1 - \frac{i}{n} \right)$$ For $n=1,2,3$, this is ...
1
vote
2answers
71 views

How to derive the Taylor expansion form of a polynomial expression?

I want to change this polynomial into the form $\sum_{k=0}^m a_k x^k$ $$q_m(x)=\sum_{k=0}^m(-1)^k\binom{2m+1}{2k+1}x^k(1-x)^{m-k}$$ I see no way to do this as I fear one might need intricate binomial ...
-2
votes
0answers
17 views

combination problem in coding [on hold]

consider we have K input symbol of length 1 bit and also from this K input symbols we can produce symbols which are XOR of 2 input symbols, chosen uniformly from these K input symbols which gives us ...
0
votes
0answers
43 views

Can you verify the combinatoric recurrence?

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical. ...
0
votes
1answer
20 views

Closed solution to double recursion

I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, ...
1
vote
1answer
19 views

Amount of match combinations of creating a 5 v 5 team from a pool

This question is inspired by the popular games: Dota 2, Heroes of the Storm and League of Legends; where players have to create two teams of 5 from a pool of "Heroes" in each match. How many ...