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)

1
vote
0answers
24 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
17 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
29 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
13 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
0answers
23 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
29 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
47 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 ...
2
votes
2answers
36 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
29 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
14 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
51 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
54 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
75 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
27 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
50 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
51 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
52 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 ...
3
votes
0answers
37 views

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

A simplicial complex $\triangle$ is shellable on the vertex set $\{x_1,\ldots,x_n\}$, if the facets of $\triangle$ can be ordered, say $F_ 1 , . . . , F _s$ , such that for all $1 ...
2
votes
1answer
29 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
30 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
49 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
59 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
32 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
37 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
28 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
0answers
133 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. $$ \sum_{j = 0}^d (-1)^{d-j} \cdot \binom{d}{k} \cdot \binom{n-j-1}{n-d-1} \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
136 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
51 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
34 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
42 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 ...
0
votes
0answers
16 views

Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? [duplicate]

Question: Which partitions $P$ of $n$ give the row and column sums of some $|P| \times |P|$ $(0,1)$-matrix? Someone comes along and gives us the partition $P=\{2,2,3,3,4\}$ of $14$. How can we ...
0
votes
1answer
28 views

Simplify the formula for the number of distributions leaving none of the $n$ cells empty

I'd like to help with the following problem: $$ \binom{x}{r-1} + \binom{x}{r} = \binom{x+1}{r} \tag{8.6}\label{8.6} $$ 7. Let $A(r, n)$ be the number of distributions leaving none of the n cells ...
0
votes
1answer
29 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
1
vote
1answer
28 views

Functions that are “balanced” on the support of a permutation

Let $F = GF(2^n)$. Let $P(x), Q(x) \in F[x]$ be such that $P(x)$ is a permutation, while $Q(x)$ is not a permutation. For $\lambda \in F^*$ define the function $g_\lambda(x) = Tr(\lambda Q(x))$. Let ...
0
votes
1answer
29 views

combination of 5 digit numbers

looking at 5-digit number when digits can be $1,2,...,9$ and with repetition, $|\Omega|=9^5$ the event of $5$ distinct digits is $9\times 8\times 7\times 6\times 5$? and the event 2 digits the same ...
0
votes
0answers
34 views

A residue question in integers

Given $N\in\Bbb N$, is it possible to find $9$ positive integers $A_j,N_i$ with $j\in\{1,2,3\}$, $i\in\{1,2,3,4,5,6\}$ such that following holds? $(1)$ $N\log N < A_j < cN\log N$ at every $j$ ...
0
votes
1answer
33 views

Prove that $\sum_{t \vert n} d^3(t) = (\sum_{t \vert n}d(t))^2$ for all $n \in \mathbb{N}$ [duplicate]

here $d(n)$ counts the number of positive divisors of $n$. I've tried 2 things: Using Bell series. But then again it just showed me that the bell series of the square of a function is not the ...
10
votes
1answer
86 views

Asymptotic Behavior of a Sum with Binomial Coefficients

The Problem: Find the asymptotic behavior (with respect to $n$) of the following sum $$\sum\limits_{j = 3}^n \binom{n}{j} \frac{(j - 1)!}{2\cdot n^j}. $$ Where the Problem Comes From: If we ...
1
vote
3answers
54 views

Right answer, wrong explanation, probability of grids?

Two unit squares are selected at random without replacement from an $n\times n$ grid of unit squares. Find the least positive integer $n$ such that the probability that the two selected squares are ...